Complexity of a Problem Concerning Reset Words for Eulerian Binary Automata
classification
💻 cs.FL
keywords
automatonresetwordautomatabinaryeuleriangivennp-complete
read the original 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 maximum 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).
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.