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

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.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
978-3-642-21874-3
978-3-642-21875-0
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/1141918
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? ND
social impact