Geodesic
Composing short 3-compressing words on a 2-letter alphabet
Discrete mathematics & theoretical computer science, Tome 19 (2017-2018) no. 1

Voir la notice de l'article provenant de la source Episciences

A finite deterministic (semi)automaton A = (Q, Σ, δ) is k-compressible 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 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 foreach k-compressible automaton, and it is k-synchronizing if it is k-compressing for all k-compressible automata withk+1 states. We compute a set W of short words such that each 3-compressible automaton on a two-letter alphabetis 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 showthat the shortest 3-synchronizing word is not 3-collapsing, illustrating the new bounds 34 ≤ c(2, 3) ≤ 53 for the length c(2, 3) of the shortest 3-collapsing word on a two-letter alphabet. 
@article{DMTCS_2017_19_1_a15,
     author = {Cherubini, Alessandra and Frigeri, Achille and Liu, Zuhua},
     title = {Composing short 3-compressing words on a 2-letter alphabet},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {19},
     number = {1},
     year = {2017-2018},
     doi = {10.23638/DMTCS-19-1-17},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-1-17/}
}
TY  - JOUR
AU  - Cherubini, Alessandra
AU  - Frigeri, Achille
AU  - Liu, Zuhua
TI  - Composing short 3-compressing words on a 2-letter alphabet
JO  - Discrete mathematics & theoretical computer science
PY  - 2017-2018
VL  - 19
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-1-17/
DO  - 10.23638/DMTCS-19-1-17
LA  - en
ID  - DMTCS_2017_19_1_a15
ER  - 
%0 Journal Article
%A Cherubini, Alessandra
%A Frigeri, Achille
%A Liu, Zuhua
%T Composing short 3-compressing words on a 2-letter alphabet
%J Discrete mathematics & theoretical computer science
%D 2017-2018
%V 19
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-1-17/
%R 10.23638/DMTCS-19-1-17
%G en
%F DMTCS_2017_19_1_a15
Cherubini, Alessandra; Frigeri, Achille; Liu, Zuhua. Composing short 3-compressing words on a 2-letter alphabet. Discrete mathematics & theoretical computer science, Tome 19 (2017-2018) no. 1. doi: 10.23638/DMTCS-19-1-17

Cité par Sources :