Recognizing Synchronizing Automata with Finitely Many Minimal Synchronizing Words is PSPACE-Complete

摘要

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.