Paper Info
Title
Recognizing synchronizing automata with finitely many minimal synchronizing words is PSPACE-complete
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.
Year
DOI
Venue
2011
10.1007/978-3-642-21875-0_24
CiE
Keywords
Field
DocType
synchronizing automaton,automaton a,synchronizing word,two-sided ideal,minimal synchronizing word,pspace-complete problem,deterministic finite-state automaton
Discrete mathematics,Finitely-generated abelian group,Deterministic automaton,Computer science,Synchronizing automaton,Synchronizing,PSPACE-complete,Automaton,Theoretical computer science,Synchronizing word
Conference
Citations 
PageRank 
References 
7
0.71
6
Authors
2
Name
Order
Citations
PageRank
Elena V. Pribavkina1529.22
Emanuele Rodaro25515.63