Geodesic
Avoiding Patterns in the Abelian Sense
Canadian journal of mathematics, Tome 53 (2001) no. 4, pp. 696-714

Voir la notice de l'article provenant de la source Cambridge University Press

We classify all 3 letter patterns that are avoidable in the abelian sense. A short list of four letter patterns for which abelian avoidance is undecided is given. Using a generalization of Zimin words we deduce some properties of $\omega$ -words avoiding these patterns.
DOI : 10.4153/CJM-2001-028-4
Mots-clés : 05, 68 
Currie, J.; Linek, V. Avoiding Patterns in the Abelian Sense. Canadian journal of mathematics, Tome 53 (2001) no. 4, pp. 696-714. doi: 10.4153/CJM-2001-028-4
@article{10_4153_CJM_2001_028_4,
     author = {Currie, J. and Linek, V.},
     title = {Avoiding {Patterns} in the {Abelian} {Sense}},
     journal = {Canadian journal of mathematics},
     pages = {696--714},
     year = {2001},
     volume = {53},
     number = {4},
     doi = {10.4153/CJM-2001-028-4},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CJM-2001-028-4/}
}
TY  - JOUR
AU  - Currie, J.
AU  - Linek, V.
TI  - Avoiding Patterns in the Abelian Sense
JO  - Canadian journal of mathematics
PY  - 2001
SP  - 696
EP  - 714
VL  - 53
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CJM-2001-028-4/
DO  - 10.4153/CJM-2001-028-4
ID  - 10_4153_CJM_2001_028_4
ER  - 
%0 Journal Article
%A Currie, J.
%A Linek, V.
%T Avoiding Patterns in the Abelian Sense
%J Canadian journal of mathematics
%D 2001
%P 696-714
%V 53
%N 4
%U http://geodesic.mathdoc.fr/articles/10.4153/CJM-2001-028-4/
%R 10.4153/CJM-2001-028-4
%F 10_4153_CJM_2001_028_4

[1] [1] Baker, Kirby A. McNulty, George F. and Taylor, Walter, Growth problems for avoidable words. Theoret. Comput. Sci. (3) 69(1989), 319–345. MR :68109. Google Scholar

[2] [2] Bean, Dwight R., Ehrenfeucht, Andrzej and McNulty, George, Avoidable Patterns in Strings of Symbols. Pacific J. Math. 85(1979), 261–294; MR :20075. Google Scholar

[3] [3] Berstel, Jean, Axel Thue's papers on repetitions in words: a translation. Google Scholar

[4] [4] Burris, Stanley and Nelson, Evelyn, Embedding the dual of Π in the lattice of equational classes of semigroups. Algebra Universalis 1(1971/72), 248–253. MR #5257. Google Scholar

[5] [5] Carpi, Arturo, On abelian squares and substitutions. Theoret. Comput. Sci. (1) 218(1999), 61–81. Google Scholar

[6] [6] Cassaigne, Julien, Motifs évitables et régularités dans les mots. Thèse de doctorat, L.I.T.P., Université Paris 6, 1994. Google Scholar

[7] [7] Cassaigne, J. and Currie, J., Words strongly avoiding fractional powers. European J. Combin., to appear. Google Scholar

[8] [8] Currie, James D., Open problems in pattern avoidance. Amer. Math.Monthly 100(1993), 790–793. Google Scholar

[9] [9] Dekking, F. M., Strongly non-repetitive sequences and progression-free sets. J. Combin Theory Ser. A 27(1979), 181–185. MR :05027. Google Scholar

[10] [10] Erdős, Paul, Some unsolved problems. Magyar Tud. Akad. Mat. Kutato. Int. Kozl. 6(1961), 221–254. Google Scholar

[11] [11] Evdomikov, A. A., Strongly asymmetric sequences generated by a finite number of symbols. Dokl. Akad. Nauk. SSSR 179(1968), 1268–1271; Soviet Math. Dokl. (1968), 536–539. Google Scholar

[12] [12] Keränen, Veikko, Abelian squares are avoidable on 4 letters. In: Automata, Languages and Programming, Lecture Notes in Comput. Sci. , Springer-Verlag, 1992, 41–52. Google Scholar

[13] [13] Morse, Marston and Hedlund, Gustav A., Symbolic dynamics I, II. Amer. J. Math. 60(1938), 815–866; (1940), 1–42. MR , 123d. Google Scholar

[14] [14] Novikov, P. S. and Adjan, S. I., Infinite periodic groups I, II, III. Izv. Akad. Nauk. SSSR Ser. Mat. 32(1968), 212–244; 251–524; 709–731. MR #1532a–c. Google Scholar

[15] [15] Pleasants, P. A. B., Non-repetitive sequences. Proc. Cambridge Philos. Soc. 68(1970), 267–274. MR #85. Google Scholar

[16] [16] Shevrin, L. N. and Volkov, M. V., Identities of semigroups. Math. USSR Izv. (11) 29(1985), 3–47. Google Scholar

[17] [17] Thue, Axel, Über unendliche Zeichenreihen. Norske Vid. Selsk. Skr. I. Mat.-Nat. Kl. Christiana (1906), Nr. 7. Google Scholar

[18] [18] Zimin, A., Blocking sets of terms. Mat. Sb. (N.S.) (1982), 363–375, 447; Math. USSR-Sb. 47(1984), 353–364. Google Scholar

Cité par Sources :