The Complexity of Finding Reset Words in Finite Automata
Jörg Olschewski, Michael Ummels, Mathematische Grundlagen der Informatik · 2010
Abstract. We study several problems related to finding reset words in deter-ministic finite automata. In particular, we establish that the problem of deciding whether a shortest reset word has length k is complete for the complexity class DP. This result answers a question posed by Volkov. For the search problems of finding a shortest reset word and the length of a shortest reset word, we es-tablish membership in the complexity classes FPNP and FPNP[log], respectively. Moreover, we show that both these problems are hard for FPNP[log]. Finally, we observe that computing a reset word of a given length is FNP-complete. 1