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

Elena V. Pribavkina Emanuele Rodaro

Published in: CiE (2011)

Keyphrases

pspace complete
np complete
model checking
tree automata
decision problems
satisfiability problem
cellular automata
coalition logic