More on Square-free Words Obtained from Prefixes by Permutations

• Autorzy: Ochem P.

Identyfikatory

DOI

10.3233/FI-2014-1035

• Języki publikacji: EN

Abstrakty

EN

An infinite square-free word w over the alphabet Σ₃ = {0, 1, 2} is said to have a k-stem σ if |σ| = k and w = σw₁w₂· · · where for each i, there exists a permutation π_i of Σ₃ which extended to a morphism gives w_i= π_i (σ). Harju proved that there exists an infinite k-stem word for k = 1, 2, 3, 9 and 13 ≤ k ≤ 19, but not for 4 ≤ k ≤ 8 and 10 ≤ k ≤ 12. He asked whether k-stem words exist for each k ≥ 20. We give a positive answer to this question. Currie has found another construction that answers Harju’s question.

Słowa kluczowe

EN

vocabulary; permutations; mathematical formulas; morphism; mathematical proofs

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 132, nr 1
• Strony: 109--112
• Opis fizyczny: Bibliogr. 5 poz.

Twórcy

autor

Ochem P.

• LIRMM, CNRS, Univ. Montpellier 2, France

Bibliografia

• [1] M. Crochemore. Sharp characterizations of squarefree morphisms, Theoret. Comput. Sci. 18(2) (1982), 221–226.
• [2] J. Currie. Infinite ternary square-free words concatenated from permutations of a single word, Theoret. Comput. Sci. 482 (2013), 1–8.
• [3] T. Harju. Square-free words obtained from prefixes by permutations, Theoret. Comput. Sci. 429 (2012), 128–133.
• [4] T. Harju and M. Müller. Square-free words generated by applying permutations to a prefix, in Proceedings of the Second Russian Finnish Symposium on Discrete Mathematics, RuFiDim II, (V. Halava, J. Karhumäki, Y. Matiyasevich, eds.) (2012), 86–91.
• [5] A. Shur. Growth rates of complexity of power-free languages, Theoret. Comput. Sci. 411(34-36) (2010), 3209–3223.