# 5-abelian cubes are avoidable on binary alphabets

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

- Volume: 48, Issue: 4, page 467-478
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topMercaş, Robert, and Saarela, Aleksi. "5-abelian cubes are avoidable on binary alphabets." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 48.4 (2014): 467-478. <http://eudml.org/doc/273075>.

@article{Mercaş2014,

abstract = {A k-abelian cube is a word uvw, where the factors u, v, and w are either pairwise equal, or have the same multiplicities for every one of their factors of length at most k. Previously it has been shown that k-abelian cubes are avoidable over a binary alphabet for k ≥ 8. Here it is proved that this holds for k ≥ 5.},

author = {Mercaş, Robert, Saarela, Aleksi},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {combinatorics on words; k-abelian equivalence; repetition-freeness; cube-freeness; -abelian cubes; equivalence},

language = {eng},

number = {4},

pages = {467-478},

publisher = {EDP-Sciences},

title = {5-abelian cubes are avoidable on binary alphabets},

url = {http://eudml.org/doc/273075},

volume = {48},

year = {2014},

}

TY - JOUR

AU - Mercaş, Robert

AU - Saarela, Aleksi

TI - 5-abelian cubes are avoidable on binary alphabets

JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

PY - 2014

PB - EDP-Sciences

VL - 48

IS - 4

SP - 467

EP - 478

AB - A k-abelian cube is a word uvw, where the factors u, v, and w are either pairwise equal, or have the same multiplicities for every one of their factors of length at most k. Previously it has been shown that k-abelian cubes are avoidable over a binary alphabet for k ≥ 8. Here it is proved that this holds for k ≥ 5.

LA - eng

KW - combinatorics on words; k-abelian equivalence; repetition-freeness; cube-freeness; -abelian cubes; equivalence

UR - http://eudml.org/doc/273075

ER -

## References

top- [1] F. Blanchet-Sadri, J.I. Kim, R. Mercaş, W. Severa, S. Simmons and D. Xu, Avoiding abelian squares in partial words. J. Combin. Theory Ser. A119 (2012) 257–270. Zbl1233.68183MR2844095
- [2] F. Blanchet-Sadri, R. MercaşandG. Scott, A generalization of Thue freeness for partial words. Theoret. Comput. Sci. 410 (2009) 793–800. Zbl1162.68029MR2492017
- [3] F. Blanchet-Sadri, K. Black and A. Zemke, Unary pattern avoidance in partial words dense with holes. In Proc. of Language and Automata Theory and Applications – 5th International Conference, LATA 2011, Tarragona, Spain, May 26-31, 2011. Edited by A.H. Dediu, S. Inenaga and C. Martín-Vide. Vol. 6638 of Lect. Notes Comput. Science. Springer (2011) 155–166. Zbl1330.68232MR2893673
- [4] F.M. Dekking, Strongly nonrepetitive sequences and progression-free sets. J. Combin. Theory Ser. A27 (1979) 181–185. Zbl0437.05011MR542527
- [5] P. Erdős, Some unsolved problems. Magyar Tudományos Akadémia Matematikai Kutató Intézete6 (1961) 221–254. Zbl0100.02001MR177846
- [6] M. Huova, Existence of an infinite ternary 64-abelian square-free word. RAIRO: ITA 48 (2014) 307–314. Zbl1297.68192MR3302490
- [7] M. Huova and J. Karhumäki, On the unavoidability of k-abelian squares in pure morphic words. J. Integer Seq. 16 (2013). Zbl1285.68135MR3032392
- [8] M. Huova, J. Karhumäki and A. Saarela, Problems in between words and abelian words: k-abelian avoidability. Theoret. Comput. Sci.454 (2012) 172–177. Zbl1280.68149MR2966632
- [9] M. Huova, J. Karhumäki, A. Saarela and K. Saari, Local squares, periodicity and finite automata. In Rainbow of Computer Science, edited by C. Calude, G. Rozenberg and A. Salomaa. Springer (2011) 90–101. Zbl1327.68182MR2805552
- [10] J. Karhumäki, S. Puzynina and A. Saarela, Fine and Wilf’s theorem for k-abelian periods. Internat. J. Found. Comput. Sci.24 (2013) 1135–1152. Zbl1293.68210MR3189714
- [11] V. Keränen, Abelian squares are avoidable on 4 letters. In Proc. of the 19th International Colloquium on Automata, Languages and Programming (1992) 41–52. MR1250629
- [12] F. Manea and R. Mercaş, Freeness of partial words. Theoret. Comput. Sci.389 (2007) 265–277. Zbl1154.68457MR2363377
- [13] R. MercaşandA. Saarela, 3-abelian cubes are avoidable on binary alphabets. In Proc. of the 17th International Conference on Developments in Language Theory, edited by M.-P. Béal and O. Carton, vol. 7907 of Lect. Notes Comput. Science. Springer (2013) 374–383. Zbl06182460MR3097343
- [14] M. Rao, On some generalizations of abelian power avoidability. preprint (2013).
- [15] A. Thue, Über unendliche Zeichenreihen. Norske Vid. Selsk. Skr. I, Mat. Nat. Kl. Christiania 7 (1906) 1–22. (Reprinted in Selected Mathematical Papers of A. Thue, T. Nagell, editor, Universitetsforlaget, Oslo, Norway (1977) 139–158). JFM39.0283.01
- [16] A. Thue, Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Norske Vid. Selsk. Skr. I, Mat. Nat. Kl. Christiania 1 (1912) 1–67. (Reprinted in Selected Mathematical Papers of Axel Thue, T. Nagell, editor, Universitetsforlaget, Oslo, Norway (1977) 413–478). Zbl44.0462.01JFM44.0462.01

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.