Codes, unambiguous automata and sofic systems

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

1 LIGM - Laboratoire d'Informatique Gaspard-Monge

We study the relationship between codes and unambiguous automata inside a sofic system. We show that a recognizable set is a code in a sofic system if and only if a particular automaton associated to the set and the shift is unambiguous. We discuss an example of a finite complete code in a sofic system in connection with the factorization conjecture.

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

Marie-Pierre Béal, Dominique Perrin. Codes, unambiguous automata and sofic systems. Theoretical Computer Science, 2006, 356 (1-2), pp.6-13. ⟨hal-00619226⟩