We show that if a semisimple synchronizing automaton with n states has a minimal reachable non-unary subset of cardinality r≥ 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].
A bound for the length of the shortest reset words for semisimple synchronizing automata via the packing number
Rodaro, Emanuele
2018-01-01
Abstract
We show that if a semisimple synchronizing automaton with n states has a minimal reachable non-unary subset of cardinality r≥ 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].File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
A bound for the length of the shortest reset words.pdf
Accesso riservato
:
Publisher’s version
Dimensione
651.85 kB
Formato
Adobe PDF
|
651.85 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
