The syntactic graph of a sofic shift

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

1 LIGM - Laboratoire d'Informatique Gaspard-Monge

We define a new invariant for the conjugacy of irreductible so fic shifts. This invariant, that we call the syntactic graph of a so fic shift, is the directed acyclic graph of characteristic groups of the non null regular D-classes of the syntactic semigroup of the shift.

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

Marie-Pierre Béal, Francesca Fiorenzi, Dominique Perrin. The syntactic graph of a sofic shift. 21st International Symposium on Theoretical Aspects of Computer Science (STACS 2004), Mar 2004, Montpellier, France. pp.282-293. ⟨hal-00619853⟩