| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4950656 | Information and Computation | 2017 | 13 Pages |
Abstract
A word is called a reset word for a deterministic finite automaton if it maps all the states of the automaton to a unique state. Deciding about the existence of a reset word of a given length for a given automaton is known to be an NP-complete problem. We prove that it remains NP-complete even if restricted to Eulerian automata with binary alphabets as it has been conjectured by Martyugin (2011).
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
VojtÄch Vorel,