Alessandra Cherubini ; Achille Frigeri ; Zuhua Liu - Composing short 3-compressing words on a 2-letter alphabet

dmtcs:1280 - Discrete Mathematics & Theoretical Computer Science, June 20, 2017, Vol. 19 no. 1 - https://doi.org/10.23638/DMTCS-19-1-17
Composing short 3-compressing words on a 2-letter alphabetArticle

Authors: Alessandra Cherubini 1; Achille Frigeri 1; Zuhua Liu 2

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.


Volume: Vol. 19 no. 1
Section: Automata, Logic and Semantics
Published on: June 20, 2017
Accepted on: May 24, 2017
Submitted on: June 12, 2017
Keywords: deterministic finite automaton,collapsing word,synchronizing word,[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]

Consultation statistics

This page has been seen 454 times.
This article's PDF has been downloaded 409 times.