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

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.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11311/1078159
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact