Abelian Patterns

Given a pattern (i.e., a word)
p = p1p2 ... pn
we say that a word w encounters p in the Abelian sense if w contains a factor P1P2 ... Pn where word Pi is an anagram of word Pj whenever pi = pj. Otherwise w avoids p in the Abelian sense and is Abelian p-free. As an example, the word
reproportioners = re pro por tion er s
encounters abbca in the Abelian sense.

We say that pattern p is avoidable in the Abelian sense if for some fixed finite alphabet Σ there are arbitrarily long words over Σ which avoid p. Equivalently, there is an infinite p-free sequence over Σ. We say that p is k-avoidable in the Abelian sense there is an infinite Abelian p-free sequence over {1, 2, 3, ..., k}. Keränen showed that xx is Abelian 4-avoidable; Dekking showed that xxx is Abelian 3-avoidable and xxxx is Abelian 2-avoidable. Avoiding patterns in the Abelian sense generalizes an existing theory of pattern avoidance [2,3,19]. (We sometimes speak of avoiding patterns "in the ordinary sense".) To encounter p in the "ordinary sense", we modify the definition above to insist that Pi = Pj whenever pi = pj. It is decidable whether a pattern p is avoidable in this sense, while the corresponding decision problem for k-avoidability is open. The word wΔ given in [2] is 4-avoidable, but not 3-avoidable. In [8] a pattern is given which is 5-avoidable, but not 4-avoidable.

Open Problem: Is there a pattern p which is 6-avoidable but not 5-avoidable?

The complexity of deciding avoidability remains open, although unsubstantiated claims have been made that deciding avoidability is NP-complete, or even exponential.

Open Problem: Given pattern p, what is the complexity of deciding whether p is avoidable?

In the case of words avoiding Abelian patterns, even less is known. In [7], Abelian fractional powers are defined; a word xyx' where x' is an anagram of x is an Abelian k-power where k=|xyx'|/|xy|. It is proved that for fixed 1 < k < 2 there exists an alphabet size nk such that an infinite word exists over {1, 2, ..., nk } not containing any Abelian k-power. In [11], this is used to prove that certain patterns are avoidable in the Abelian sense. The pattern
p = abcabadabacba
is shown to be avoidable, but not Abelian avoidable.

Open Problem: Which patterns are Abelian avoidable?

Here are some quite specific subproblems left over from [11]:

Open Problem: Which of the following patterns is avoidable in the Abelian sense?

In [12, 13], a start is made on a theory of Abelian k-avoidablity. (See this link for some slides.) It is shown that binary patterns of length 119 or more are Abelian 2-avoidable. This leaves a large but approachable project:

Open Problem: Which binary patterns are Abelian 2-avoidable?

Bibliography

  1. S. V. Avgustinovich, A. E. Frid, Words avoiding Abelian inclusions. J. Autom. Lang. Comb. 7 (2002), no. 1, 3–9.
  2. K. A. Baker, G. F. McNulty, W. Taylor, Growth problems for avoidable words, Theoret. Comput. Sci. 69 (1989), no. 3, 319–345; MR 91f:68109.
  3. D. R. Bean, A. Ehrenfeucht , G. McNulty, Avoidable Patterns in Strings of Symbols, Pacific J. Math. 85 (1979), 261–294; MR 81i:20075.
  4. A. Carpi, On Abelian squares and substitutions. Theoret. Comput. Sci. 218 (1999), no. 1, 61–81
  5. A. Carpi, On the number of Abelian square-free words on four letters, Disc. Appl. Math, 81 (1998) 155–167
  6. A. Carpi, On Abelian squares and substitutions, Theoret. Comp. Sci., 218 (1999) 61–81
  7. J. Cassaigne, J. D. Currie, Words strongly avoiding fractional powers, European J. Combin. 20 (8) (1999), 725–737.
  8. R. J. Clark, Avoidable Formulas in Combinatorics on Words, Doctoral Thesis, UCLA, (2001).
  9. R. Cori , M. R. Formisano, On the number of partially Abelian square-free words on a three-letter alphabet, Theoret. Comput. Sci. 81 (1991), no. 1, (Part A), 147–153.
  10. J. D. Currie, Open problems in pattern avoidance, Amer. Math. Monthly 100 (1993), 790–793.
  11. J. D. Currie , V. Linek, Avoiding Patterns in the Abelian Sense, Canadian J. Math. 51 no. 4 (2001), 696 – 714.
  12. J. D. Currie, T. I. Visentin, On Abelian 2-avoidable binary patterns. Acta Inf. 43(8): 521–533 (2007)
  13. J. D. Currie, T. I. Visentin, Long binary patterns are Abelian 2-avoidable. Theoret. Comp. Sci. 43(8). To appear.
  14. F. M. Dekking. Strongly non-repetitive sequences and progression-free sets. J. Comb. Theory Ser. A 27 (1979), 181-185.
  15. P. Erdös, Some unsolved problems, Magyar Tud. Akad. Mat. Kutato. Int. Kozl. 6 (1961), 221–254.
  16. A. A. Evdomikov, 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.
  17. J. Justin, Characterization of the repetitive commutative semigroups. J. Algebra 21 (1972), 87–90.
  18. V. Keränen, Abelian squares are avoidable on 4 letters, Automata, Languages and Programming: Lecture notes in Computer Science 623 (1992) Springer-Verlag, 41–52.
  19. A. Zimin, Blocking sets of terms, Mat. Sb. (N.S.) 119 (161) (1982); Math. USSR Sbornik 47 (1984), 353–364.