Autor:	Szykuła, Marek, Vorel, Vojtěch
Rok vydání:	2016
Předmět:	Computer Science - Formal Languages and Automata Theory
Zdroj:	Developments in Language Theory (DLT 2016), volume 9840 of LNCS, pages 380--392, 2016
Druh dokumentu:	Working Paper
DOI:	10.1007/978-3-662-53132-7_31
Popis:	We present an infinite series of $n$-state Eulerian automata whose reset words have length at least $(n^2-3)/2$. This improves the current lower bound on the length of shortest reset words in Eulerian automata. We conjecture that $(n^2-3)/2$ also forms an upper bound for this class and we experimentally verify it for small automata by an exhaustive computation. Comment: The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-662-53132-7_31
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1604.02879 Zobrazit plný text záznamu View this record from Arxiv