Complexity of problems concerning reset words for cyclic and Eulerian automata

Abstract

A word is called a reset word for a deterministic finite automaton if it maps all states of this automaton to one state. We consider two classes of automata: cyclic automata and Eulerian automata. For these classes we study the computational complexity of the following problems: does there exist a reset word of given length for a given automaton? what is the minimal length of the reset words for a given automaton? © 2012 Elsevier B.V. All rights reserved.