The syntactic graph of a sofic shift is invariant under shift equivalence

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

1 LIGM - Laboratoire d'Informatique Gaspard-Monge

We de ne a new invariant for shift equivalence of 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 is invariant under shift equivalence. International Journal of Algebra and Computation, 2006, 16 (3), pp.443-460. ⟨hal-00619735⟩