Autor:	Vorel, Vojtěch
Rok vydání:	2014
Předmět:	Computer Science - Formal Languages and Automata Theory
Druh dokumentu:	Working Paper
Popis:	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). Comment: Extended version of a paper presented at LATA 2014
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1409.2003 Zobrazit plný text záznamu View this record from Arxiv