A finite deterministic (semi) automaton A = (Q, Sigma, delta) is k-compressible if there is some word w is an element of Sigma(+) such that the image of its state set Q under the natural action of w is reduced by at least k states. Such word w, if it exists, is called a k-compressing word for A and A is said to be k-compressed by w. A word is k-collapsing if it is k-compressing for each k-compressible automaton, and it is k-synchronizing if it is k-compressing for all k-compressible automata with k + 1 states. We compute a set W of short words such that each 3-compressible automaton on a two-letter alphabet is 3-compressed at least by a word in W. Then we construct a shortest common superstring of the words in W and, with a further refinement, we obtain a 3-collapsing word of length 53. Moreover, as previously announced, we show that the shortest 3-synchronizing word is not 3-collapsing, illustrating the new bounds 34 <= c(3, 2) <= 53 for the length c (3, 2) of the shortest 3-collapsing word on a two-letter alphabet.

Composing short 3-compressing words on a 2-letter alphabet

A. Cherubini;A. Frigeri;
2017-01-01

Abstract

A finite deterministic (semi) automaton A = (Q, Sigma, delta) is k-compressible if there is some word w is an element of Sigma(+) such that the image of its state set Q under the natural action of w is reduced by at least k states. Such word w, if it exists, is called a k-compressing word for A and A is said to be k-compressed by w. A word is k-collapsing if it is k-compressing for each k-compressible automaton, and it is k-synchronizing if it is k-compressing for all k-compressible automata with k + 1 states. We compute a set W of short words such that each 3-compressible automaton on a two-letter alphabet is 3-compressed at least by a word in W. Then we construct a shortest common superstring of the words in W and, with a further refinement, we obtain a 3-collapsing word of length 53. Moreover, as previously announced, we show that the shortest 3-synchronizing word is not 3-collapsing, illustrating the new bounds 34 <= c(3, 2) <= 53 for the length c (3, 2) of the shortest 3-collapsing word on a two-letter alphabet.
deterministic finite automaton; collapsing word; synchronizing word, COLLAPSING WORDS; 2-COLLAPSING WORDS; CERNY CONJECTURE; ALGORITHMS; AUTOMATA
File in questo prodotto:
File Dimensione Formato  
11311-1063505_Cherubini.pdf

accesso aperto

: Publisher’s version
Dimensione 375.26 kB
Formato Adobe PDF
375.26 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: https://hdl.handle.net/11311/1063505
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact