episciences.org_1280_1669553443
1669553443
episciences.org
raphael.tournoy+crossrefapi@ccsd.cnrs.fr
episciences.org
Discrete Mathematics & Theoretical Computer Science
13658050
06
20
2017
Vol. 19 no. 1
Automata, Logic and Semantics
Composing short 3compressing words on a 2letter alphabet
Alessandra
Cherubini
Achille
Frigeri
Zuhua
Liu
A finite deterministic (semi)automaton A = (Q, Σ, δ) is kcompressible if there is some word w ∈ Σ + such that theimage 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 calleda kcompressing word for A and A is said to be kcompressed by w. A word is kcollapsing if it is kcompressing foreach kcompressible automaton, and it is ksynchronizing if it is kcompressing for all kcompressible automata withk+1 states. We compute a set W of short words such that each 3compressible automaton on a twoletter alphabetis 3compressed 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 3collapsing word of length 53. Moreover, as previously announced, we showthat the shortest 3synchronizing word is not 3collapsing, illustrating the new bounds 34 ≤ c(2, 3) ≤ 53 for the length c(2, 3) of the shortest 3collapsing word on a twoletter alphabet.
06
20
2017
1280
https://creativecommons.org/licenses/byn
https://hal.archivesouvertes.fr/hal01184460v3
https://hal.archivesouvertes.fr/hal01184460v2
https://hal.archivesouvertes.fr/hal01184460v1
10.23638/DMTCS19117
https://dmtcs.episciences.org/1280

https://dmtcs.episciences.org/3709/pdf