Finitely Generated Synchronizing Automata

摘要

A synchronizing word w for a given synchronizing DFA is called minimal if no proper prefix or suffix of w is synchronizing. We characterize the class of synchronizing automata having finite language of minimal synchronizing words (such automata are called finitely generated). Using this characterization we prove that any such automaton possesses a synchronizing word of length at most 3n - 5. We also prove that checking whether a given DFA A is finitely generated is co-NP-hard, and provide an algorithm for this problem which is exponential in the number of states A.