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-NPhard, and provide an algorithm for this problem which is exponential in the number of states A. © Springer-Verlag Berlin Heidelberg 2009.

Finitely generated synchronizing automata

Rodaro E.
2009

Abstract

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-NPhard, and provide an algorithm for this problem which is exponential in the number of states A. © Springer-Verlag Berlin Heidelberg 2009.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
978-3-642-00981-5
978-3-642-00982-2
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11311/1142784
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 3
social impact