A hierarchy of irreducible sofic shifts

Marie-Pierre Béal (1) , Francesca Fiorenzi (1) , Dominique Perrin (1)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge

We define new subclasses of the class of irreducible sofic shifts. These classes form an infinite hierarchy where the lowest class is the class of almost finite type shifts introduced by B. Marcus. We give effective characterizations of these classes with the syntactic semigroups of the shifts.

Domaines: Algorithme et structure de données [cs.DS]

Marie-Pierre Béal, Francesca Fiorenzi, Dominique Perrin. A hierarchy of irreducible sofic shifts. 29th International Symposium on Mathematical Foundations of Computer Science 2004, 2004, Czech Republic. pp.611-622. ⟨hal-00619854⟩