Complexity of a Problem Concerning Reset Words for Eulerian Binary Automata

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).

Keywords

• Reset word
• Deterinistic finite automaton
• NP-Completeness