An Extremal Series of Eulerian Synchronizing Automata

Abstrakt

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.

Klíčová slova

• Eulerian automaton
• Reset threshold
• Reset word
• Synchronizing automaton