A bound for the shortest reset words for semisimple synchronizing automata via the packing number

Abstract

We show that if a semisimple synchronizing automaton with $n$ states has a minimal reachable non-unary subset of cardinality $r\ge 2$, then there is a reset word of length at most $(n-1)D(2,r,n)$, where $D(2,r,n)$ is the $2$-packing number for families of $r$-subsets of $[1,n]$.

References in corpus (1)

• Improving the upper bound on the length of the shortest reset words