Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata

P Martyugin - Theory of Computing Systems, 2014 - Springer
P Martyugin
Theory of Computing Systems, 2014•Springer
We show that the problem of checking careful synchronizability of partial finite automata is
PSPACE-complete. Also the problems of checking D 1-, D 2-, and D 3-directability of
nondeterministic finite automata are PSPACE-complete; moreover, the restrictions of all
these problems to automata with two input letters remain PSPACE-complete.
Abstract
We show that the problem of checking careful synchronizability of partial finite automata is PSPACE-complete. Also the problems of checking D 1-, D 2-, and D 3-directability of nondeterministic finite automata are PSPACE-complete; moreover, the restrictions of all these problems to automata with two input letters remain PSPACE-complete.
Springer
Show moreShow less
Save Cite Cited by 43 Related articles All 8 versions