Independent sets of words and the synchronization problem

https://doi.org/10.1016/j.aam.2012.07.003Get rights and content
Under an Elsevier user license
open archive

Abstract

The synchronization problem is investigated for the class of locally strongly transitive automata introduced in Carpi and DʼAlessandro (2009) [9]. Some extensions of this problem related to the notions of stable set and word of minimal rank of an automaton are studied. An application to synchronizing colorings of aperiodic graphs with a Hamiltonian path is also considered.

MSC

68Q45
05C15
05C45

Keywords

Černý conjecture
Road coloring problem
Synchronizing automaton

Cited by (0)

This work was partially supported by MIUR project “Aspetti matematici e applicazioni emergenti degli automi e dei linguaggi formali” and by fundings “Facoltà di Scienze MM. FF. NN. 2008” of the University of Rome “La Sapienza”.