Computational Complexity of Certain Problems Related to Carefully Synchronizing Words for Partial Automata and Directing Words for Nondeterministic Automata |
| |
| Authors: | Pavel Martyugin |
| |
| Affiliation: | 1. Institute of Mathematics and Computer Science, Ural Federal University, 620000, Ekaterinburg, Russia
|
| |
| 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. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
