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 states of the automaton to one state. Deciding about the existence of a reset word of given length for a given automaton is known to be a NP-complete problem.

We prove that it remains NP-complete even if restricted on Eulerian automata over the binary alphabet, as it has been conjectured by Martyugin (2011).

Keywords

• Synchronizing Automata
• Reset Word
• Synchronizing Word
• Directing Word
• Computational Complexity
• Černý Conjecture