EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC 4.0

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

Alessandra Cherubini, Achille Frigeri, Zuhua Liu

Discrete Mathematics & Theoretical Computer Science · 2017

DOI: 10.23638/dmtcs-19-1-17 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Discrete Mathematics & Theoretical Computer Science, 2017. Verfasst von Alessandra Cherubini und 2 weiteren Autor:innen. Der Volltext ist frei zugänglich (Open Access, CC BY-NC 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Cherubini, A., Frigeri, A., & Liu, Z. (2017). Composing short 3-compressing words on a 2-letter alphabet. Discrete Mathematics & Theoretical Computer Science. https://doi.org/10.23638/dmtcs-19-1-17

Vancouver

Cherubini A, Frigeri A, Liu Z. Composing short 3-compressing words on a 2-letter alphabet. Discrete Mathematics & Theoretical Computer Science. 2017. doi:10.23638/dmtcs-19-1-17

BibTeX
@article{Cherubini2017,
  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},
  year = {2017},
  doi = {10.23638/dmtcs-19-1-17}
}
Kostenlos starten →