5-abelian cubes are avoidable on binary alphabets

Robert Mercaş; Aleksi Saarela

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

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

Abstract

top
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.

How to cite

top

Mercaş, 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. [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. [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. [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. [4] F.M. Dekking, Strongly nonrepetitive sequences and progression-free sets. J. Combin. Theory Ser. A27 (1979) 181–185. Zbl0437.05011MR542527
  5. [5] P. Erdős, Some unsolved problems. Magyar Tudományos Akadémia Matematikai Kutató Intézete6 (1961) 221–254. Zbl0100.02001MR177846
  6. [6] M. Huova, Existence of an infinite ternary 64-abelian square-free word. RAIRO: ITA 48 (2014) 307–314. Zbl1297.68192MR3302490
  7. [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. [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. [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. [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. [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. [12] F. Manea and R. Mercaş, Freeness of partial words. Theoret. Comput. Sci.389 (2007) 265–277. Zbl1154.68457MR2363377
  13. [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. [14] M. Rao, On some generalizations of abelian power avoidability. preprint (2013). 
  15. [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. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.