A deterministic finite-state automaton A is said to be synchronizing if there is a synchronizing word, i.e. a word that takes all the states of the automaton A to a particular one. We consider synchronizing automata whose language of synchronizing words is finitely generated as a two-sided ideal in Σ*. Answering a question stated in [1], here we prove that recognizing such automata is a PSPACE-complete problem. © 2011 Springer-Verlag.
Recognizing synchronizing automata with finitely many minimal synchronizing words is PSPACE-complete
Rodaro E.
2011-01-01
Abstract
A deterministic finite-state automaton A is said to be synchronizing if there is a synchronizing word, i.e. a word that takes all the states of the automaton A to a particular one. We consider synchronizing automata whose language of synchronizing words is finitely generated as a two-sided ideal in Σ*. Answering a question stated in [1], here we prove that recognizing such automata is a PSPACE-complete problem. © 2011 Springer-Verlag.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.
