Geodesic
On $k$-abelian avoidability
Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part IV, Tome 402 (2012), pp. 170-182 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

We consider a recently defined notion of $k$-abelian equivalence of words by giving some basic results and concentrating on avoidability problems. This equivalence relation counts the numbers of factors of length $k$ for a fixed natural number $k$. We ask for the size of the smallest alphabet for which $k$-abelian squares and cubes can be avoided, respectively. For $2$-abelian squares this is four – as in the case of abelian words, while for $2$-abelian cubes we have only strong evidence that the size is two – as it is in the case of words. In addition, we point out a few properties of morphisms supporting the view that it might be difficult to find solutions to our questions by simply iterating a morphism. 
@article{ZNSL_2012_402_a9,
     author = {M. Huova and J. Karhum\"aki},
     title = {On $k$-abelian avoidability},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {170--182},
     year = {2012},
     volume = {402},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2012_402_a9/}
}
TY  - JOUR
AU  - M. Huova
AU  - J. Karhumäki
TI  - On $k$-abelian avoidability
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2012
SP  - 170
EP  - 182
VL  - 402
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2012_402_a9/
LA  - en
ID  - ZNSL_2012_402_a9
ER  - 
%0 Journal Article
%A M. Huova
%A J. Karhumäki
%T On $k$-abelian avoidability
%J Zapiski Nauchnykh Seminarov POMI
%D 2012
%P 170-182
%V 402
%U http://geodesic.mathdoc.fr/item/ZNSL_2012_402_a9/
%G en
%F ZNSL_2012_402_a9
M. Huova; J. Karhumäki. On $k$-abelian avoidability. Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part IV, Tome 402 (2012), pp. 170-182. http://geodesic.mathdoc.fr/item/ZNSL_2012_402_a9/

[1] J.-P. Allouche, J. Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, Cambridge, 2003 | MR | Zbl

[2] F.-J. Brandenburg, “Uniformly growing $k$-th power-free homomorphisms”, Theoret. Comput. Sci., 23 (1983), 69–82 | DOI | MR | Zbl

[3] A. Carpi, “On repeated factors in $C^\infty$-words”, Inform. Process. Lett., 52:6 (1994), 289–294 | DOI | MR | Zbl

[4] C. Choffrut, J. Karhumäki, “Combinatorics of words”, Handbook of Formal Languages, v. 1, eds. G. Rozenberg, A. Salomaa, Springer, Heidelberg, 1997, 329–438 | DOI | MR

[5] F. M. Dekking, “Strongly non-repetitive sequences and progression-free sets”, J. Combin. Theory Ser. A, 27:2 (1979), 181–185 | DOI | MR | Zbl

[6] Soviet Math. Dokl., 9 (1968), 536–539 | MR | Zbl

[7] M. Huova, J. Karhumäki, A. Saarela, “Problems in between words and abelian words: $k$-abelian avoidability”, Special issue of Theoretical Computer Science, eds. G. Rozenberg, A. Salomaa (to appear)

[8] M. Huova, J. Karhumäki, A. Saarela, K. Saari, “Local squares, periodicity and finite automata”, Rainbow of Computer Science, LNCS, 6570, eds. C. S. Calude, G. Rozenberg, A. Salomaa, Springer, Heidelberg, 2011, 90–101 | MR | Zbl

[9] J. Karhumäki, “Generalized Parikh mappings and homomorphisms”, Information and control, 47 (1980), 155–165 | DOI | MR | Zbl

[10] J. Karhumäki, A. Saarela, L. Zamboni, Generalized abelian equivalence, Manuscript to be published

[11] V. Keränen, “Abelian squares are avoidable on 4 letters”, ICALP 1992, LNCS, 623, ed. W. Kuich, Springer, Heidelberg, 1992, 41–52 | MR

[12] J. Leech, “A problem on strings of beads”, Math. Gazette, 41 (1957), 277–278 | DOI | MR | Zbl

[13] A. Lepistö, “Repetitions in Kolakoski sequence”, Developments in Language Theory “At the Crossroads of Mathematics, Computer Science and Biology”, eds. G. Rozenberg, A. Salomaa, World Scientific, 1994, 130–143

[14] M. Lothaire, Combinatorics on words, Addison-Wesley, Reading, 1983 | MR | Zbl

[15] P. A. B. Pleasant, “Non-repetitive sequences”, Proc. Cambridge Philos. Soc., 68 (1970), 267–274 | DOI | MR | Zbl

[16] A. Thue, “Über unendliche Zeichenreihen”, Norske vid. Selsk. Skr. Mat. Nat. Kl., 1906, no. 7, 1–22 | Zbl

[17] A. Thue, “Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen”, Norske vid. Selsk. Skr. Mat. Nat. Kl., 1912, no. 1, 1–67 | Zbl