An Extremal Series of Eulerian Synchronizing Automata

Abstract

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.

The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-662-53132-7_31

References in corpus (3)

• Primitive digraphs with large exponents and slowly synchronizing automata
• Synchronizing Automata with Extremal Properties
• Experiments with Synchronizing Automata