Existence of an infinite ternary 64-abelian square-free word

Mari Huova

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2014)

  • Volume: 48, Issue: 3, page 307-314
  • ISSN: 0988-3754

Abstract

top
We consider a recently defined notion of k-abelian equivalence of words by concentrating on avoidance problems. The equivalence class of a word depends on the numbers of occurrences of different factors of length k for a fixed natural number k and the prefix of the word. We have shown earlier that over a ternary alphabet k-abelian squares cannot be avoided in pure morphic words for any natural number k. Nevertheless, computational experiments support the conjecture that even 3-abelian squares can be avoided over ternary alphabets. In this paper we establish the first avoidance result showing that by choosing k to be large enough we have an infinite k-abelian square-free word over three letter alphabet. In addition, this word can be obtained as a morphic image of a pure morphic word.

How to cite

top

Huova, Mari. "Existence of an infinite ternary 64-abelian square-free word." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 48.3 (2014): 307-314. <http://eudml.org/doc/273016>.

@article{Huova2014,
abstract = {We consider a recently defined notion of k-abelian equivalence of words by concentrating on avoidance problems. The equivalence class of a word depends on the numbers of occurrences of different factors of length k for a fixed natural number k and the prefix of the word. We have shown earlier that over a ternary alphabet k-abelian squares cannot be avoided in pure morphic words for any natural number k. Nevertheless, computational experiments support the conjecture that even 3-abelian squares can be avoided over ternary alphabets. In this paper we establish the first avoidance result showing that by choosing k to be large enough we have an infinite k-abelian square-free word over three letter alphabet. In addition, this word can be obtained as a morphic image of a pure morphic word.},
author = {Huova, Mari},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {combinatorics on words; k-abelian equivalence; square-freeness; -abelian; equivalence},
language = {eng},
number = {3},
pages = {307-314},
publisher = {EDP-Sciences},
title = {Existence of an infinite ternary 64-abelian square-free word},
url = {http://eudml.org/doc/273016},
volume = {48},
year = {2014},
}

TY - JOUR
AU - Huova, Mari
TI - Existence of an infinite ternary 64-abelian square-free word
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2014
PB - EDP-Sciences
VL - 48
IS - 3
SP - 307
EP - 314
AB - We consider a recently defined notion of k-abelian equivalence of words by concentrating on avoidance problems. The equivalence class of a word depends on the numbers of occurrences of different factors of length k for a fixed natural number k and the prefix of the word. We have shown earlier that over a ternary alphabet k-abelian squares cannot be avoided in pure morphic words for any natural number k. Nevertheless, computational experiments support the conjecture that even 3-abelian squares can be avoided over ternary alphabets. In this paper we establish the first avoidance result showing that by choosing k to be large enough we have an infinite k-abelian square-free word over three letter alphabet. In addition, this word can be obtained as a morphic image of a pure morphic word.
LA - eng
KW - combinatorics on words; k-abelian equivalence; square-freeness; -abelian; equivalence
UR - http://eudml.org/doc/273016
ER -

References

top
  1. [1] J.-P. Allouche and J. Shallit, Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press (2003). Zbl1086.11015MR1997038
  2. [2] G. Badkobeh and M. Crochemore, Finite-Repetition threshold for infinite ternary words, in 8th International Conference WORDS 2011, edited by P. Ambroz, S. Holub and Z. Masáková. EPTCS 63 (2011) 37–43. Zbl1331.68160
  3. [3] J. Cassaigne, Unavoidable binary patterns. Acta Informatica30 (1993) 385–395. Zbl0790.68096MR1227889
  4. [4] C. Choffrut and J. Karhumäki, Combinatorics of words, in vol. 1 of Handbook of Formal Languages, edited by G. Rozenberg and A. Salomaa. Springer (1997) 329–438. Zbl0866.68057MR1469998
  5. [5] K. Culik, J. Karhumäki and A. Lepistö, Alternating iteration of morphisms and the Kolakoski sequence, in Lindenmayer Systems, edited by G. Rozenberg and A. Salomaa. Springer (1992) 93–106. Zbl0766.68073MR1226686
  6. [6] J.D. Currie, Open problems in pattern avoidance. Amer. Math. Monthly100 (1993) 790–793. Zbl0798.68139MR1542406
  7. [7] F.M. Dekking, Strongly non-repetitive sequences and progression-free sets. J. Combin. Theory Ser. A27 (1979) 181–185. Zbl0437.05011MR542527
  8. [8] A.A. Evdokimov, Strongly asymmetric sequences generated by a finite number of symbols. Dokl. Akad. Nauk SSSR 179 (1968) 1268–1271; English translation in Soviet Math. Dokl. 9 (1968) 536–539. Zbl0186.01504MR234842
  9. [9] M. Huova and J. Karhumäki, On Unavoidability of k-abelian Squares in Pure Morphic Words. J. Integer Sequences, being bublished. Zbl1285.68135
  10. [10] M. Huova, J. Karhumäki and A. Saarela, Problems in between words and abelian words: k-abelian avoidability, in Formal and Natural Computing Honoring the 80th Birthday of Andrzej Ehrenfeucht, edited by G. Rozenberg and A. Salomaa. Theoret. Comput. Sci. 454 (2012) 172–177. Zbl1280.68149MR2966632
  11. [11] M. Huova, J. Karhumäki, A. Saarela and K. Saari, Local squares, periodicity and finite automata, in Rainbow of Computer Science, edited by C.S. Calude, G. Rozenberg and A. Salomaa. Vol. 6570 of Lect. Notes Comput. Sci. Springer (2011) 90–101. Zbl1327.68182MR2805552
  12. [12] V. Keränen, Abelian squares are avoidable on 4 letters, in Proc. ICALP 1992, edited by W. Kuich. Vol. 623 of Lect. Notes Comput. Sci. Springer (1992) 41–52. MR1250629
  13. [13] M. Lothaire, Combinatorics on words, Addison-Wesley (1983). Zbl0514.20045MR675953
  14. [14] M. Lothaire, Algebraic combinatorics on words. Cambridge University Press (2002). Zbl1221.68183MR1905123
  15. [15] R. Mercas and A. Saarela, 5-abelian cubes are avoidable on binary alphabets, in the conference the 14th Mons Days of Theoretical Computer Science (2012). Zbl06182460
  16. [16] P.A.B. Pleasant, Non-repetitive sequences. Proc. Cambridge Philos. Soc.68 (1970) 267–274. Zbl0237.05010MR265173
  17. [17] A. Thue, Über unendliche Zeichenreihen. Norske vid. Selsk. Skr. Mat. Nat. Kl. 7 (1906) 1–22. JFM39.0283.01
  18. [18] A. Thue, Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Norske vid. Selsk. Skr. Mat. Nat. Kl. 1 (1912) 1–67. Zbl44.0462.01JFM44.0462.01

NotesEmbed ?

top

You must be logged in to post comments.