Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-05T10:43:18.047Z Has data issue: false hasContentIssue false
  • English
  • Français

Avoiding Patterns in the Abelian Sense

Published online by Cambridge University Press:  20 November 2018

J. Currie  and
V. Linek
J. Currie
Affiliation:
Department of Mathematics and Statistics, University of Winnipeg, Winnipeg, Manitoba, R3B 2E9
V. Linek
Affiliation:
Department of Mathematics and Statistics, University of Winnipeg, Winnipeg, Manitoba, R3B 2E9
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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.

Keywords

0568
Type
Research Article
Information
Canadian Journal of Mathematics , Volume 53 , Issue 4 , 01 August 2001 , pp. 696 - 714
Copyright
Copyright © Canadian Mathematical Society 2001

References

[1] Baker, Kirby A. McNulty, George F. and Taylor, Walter, Growth problems for avoidable words. Theoret. Comput. Sci. (3) 69(1989), 319–345. MR 91f:68109.Google Scholar
[2] Bean, Dwight R., Ehrenfeucht, Andrzej and McNulty, George, Avoidable Patterns in Strings of Symbols. Pacific J. Math. 85(1979), 261–294; MR 81i:20075.Google Scholar
[3] Berstel, Jean, Axel Thue's papers on repetitions in words: a translation. Google Scholar
[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 45#5257.Google Scholar
[5] Carpi, Arturo, On abelian squares and substitutions. Theoret. Comput. Sci. (1) 218(1999), 61–81.Google Scholar
[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] Cassaigne, J. and Currie, J., Words strongly avoiding fractional powers. European J. Combin., to appear.Google Scholar
[8] Currie, James D., Open problems in pattern avoidance. Amer. Math.Monthly 100(1993), 790–793.Google Scholar
[9] Dekking, F. M., Strongly non-repetitive sequences and progression-free sets. J. Combin Theory Ser. A 27(1979), 181–185. MR 81b:05027.Google Scholar
[10] Erdős, Paul, Some unsolved problems. Magyar Tud. Akad. Mat. Kutato. Int. Kozl. 6(1961), 221–254.Google Scholar
[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. 9(1968), 536–539.Google Scholar
[12] Keränen, Veikko, Abelian squares are avoidable on 4 letters. In: Automata, Languages and Programming, Lecture Notes in Comput. Sci. 623, Springer-Verlag, 1992, 41–52.Google Scholar
[13] Morse, Marston and Hedlund, Gustav A., Symbolic dynamics I, II. Amer. J. Math. 60(1938), 815–866; 62(1940), 1–42. MR 1, 123d.Google Scholar
[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 39#1532a–c.Google Scholar
[15] Pleasants, P. A. B., Non-repetitive sequences. Proc. Cambridge Philos. Soc. 68(1970), 267–274. MR 42#85.Google Scholar
[16] Shevrin, L. N. and Volkov, M. V., Identities of semigroups. Math. USSR Izv. (11) 29(1985), 3–47.Google Scholar
[17] Thue, Axel, Über unendliche Zeichenreihen. Norske Vid. Selsk. Skr. I. Mat.-Nat. Kl. Christiana (1906), Nr. 7.Google Scholar
[18] Zimin, A., Blocking sets of terms. Mat. Sb. (N.S.) 119 (161)(1982), 363–375, 447; Math. USSR-Sb. 47(1984), 353–364.Google Scholar