Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

The Complexity of Unavoidable Word Patterns

  • Published:
Theory of Computing Systems Aims and scope Submit manuscript

Abstract

The avoidability, or unavoidability of patterns in words over finite alphabets has been studied extensively. The word α over a finite set A is said to be unavoidable for an infinite set B+ of nonempty words over a finite set B if, for all but finitely many elements w of B+, there exists a semigroup morphism \(\phi :A^{+}\rightarrow B^{+}\) such that ϕ(α) is a factor of w. We discuss unavoidability in the milieu of various types of complexity. For words that are unavoidable, we provide a constructive upper bound to the lengths of words that can avoid them. We then discuss the relative density of unavoidable words. Subsequently, we investigate computational aspects of unavoidable words, focusing on the computational complexity of determining whether a word is unavoidable. This culminates in a proof that this problem is NP-complete.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Adian, S.I., Adjan, S.I, Lennox, J., Wiegold, J.: The Burnside Problem and Identities in Groups. Results in Mathematics and Related Areas, Springer (1979)

    Book  Google Scholar 

  2. Alon, N., Grytczuk, J., Hałuszczak, M., Riordan, O.: Nonrepetitive colorings of graphs. Random Structures & Algorithms 21(3-4), 336–346 (2002)

    Article  MathSciNet  Google Scholar 

  3. Arshon, S.: Démonstration de l’existence des suites asymétriques infinies. Rec. Math. [Mat. Sbornik] N.S. 44(4), 769–779 (June 1937)

  4. Bean, D.R., Ehrenfeucht, A., McNulty, G.F.: Avoidable patterns in strings of symbols. Pac. J. Math. 85(2), 261–294 (1979)

    Article  MathSciNet  Google Scholar 

  5. Blakeley, B., Blanchet-Sadri, F., Gunter, J., Rampersad, N.: On the complexity of deciding avoidability of sets of partial words. In: Diekert, V, Nowotka, D (eds.) Developments in Language Theory, pp. 113–124, Berlin, Heidelberg. Springer Berlin Heidelberg (2009)

  6. Burris, S., Nelson, E.: Embedding the dual of πm in the lattice of equational classes of commutative semigroups. Proc. Am. Math. Soc 30(1), 37–39 (1971)

    MathSciNet  MATH  Google Scholar 

  7. Conlon, D., Fox, J., Sudakov, B.: Tower-type bounds for unavoidable patterns in words Transactions of the American Mathematical Society (2019)

  8. Cooper, J., Rorabaugh, D.: Bounds on Zimin word avoidance. Congressus Numerantium 09, 87–95 (2014)

    MathSciNet  MATH  Google Scholar 

  9. Currie, J: Open problems in pattern avoidance. Am. Math. Mon. 100(8), 790–793 (1993)

    Article  MathSciNet  Google Scholar 

  10. Dekking, M.: On repetitions of blocks in binary sequences. J. Comb. Theory 20, 292–299 (1976)

    Article  MathSciNet  Google Scholar 

  11. Erdős, P.: Some unsolved problems. Michigan Math. J. 4(3), 291–300 (1957)

    Article  MathSciNet  Google Scholar 

  12. Evdokimov, A.A.: Strongly asymmetric sequences generated by a finite number of symbols. Dokl. Akad. Nauk SSSR 179, 1268–1271 (1968). (also Soviet Math. Dokl. 9 (1968),536-539)

    MathSciNet  MATH  Google Scholar 

  13. Fouché, W.L.: Unavoidable regularities and factor permutations of words. In: Proc. Royal Society Edinburgh, vol. 125A, pp. 519–524. Cambridge University Press (1995)

  14. Graham, R.L., Rothschild, B.L.: Ramsey Theory, 2nd. Wiley, New York (1990)

    MATH  Google Scholar 

  15. Grytczuk, J.: Pattern avoiding colorings of euclidean spaces. Ars Comb. 64, 109–07 (2002)

    MathSciNet  MATH  Google Scholar 

  16. Hawkins, D., Mientka, W.: On sequences which contain no repetition. Math. Student 24, 185–187 (1956)

    MathSciNet  MATH  Google Scholar 

  17. Hedlund, G.: Remarks on the work of Axel Thue on sequences. Nordisk. Mat. Tidskr. 15, 147–150 (1967)

    MathSciNet  MATH  Google Scholar 

  18. Heitsch, C.E.: Computational Complexity of Generalized Pattern Matching. PhD thesis, University of California, Berkeley. AAI3001868 (2000)

  19. Heitsch, C.E.: Generalized pattern matching and the complexity of unavoidability testing. In: Proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching, CPM ’01, pp. 219–230, London, UK, UK, Springer-Verlag (2001)

  20. Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, Massachusetts (1979)

    MATH  Google Scholar 

  21. Ježek, J: Intervals in the lattice of varieties. Algebra Universalis 6(1), 147–158 (Dec 1976)

  22. Justin, J.: Propriétés combinatoires de certains semigroupes. CRAS 269, 1113–1115 (1969)

    MathSciNet  MATH  Google Scholar 

  23. Keranen, V.: Abelian squares are avoidable on 4 letters. Lect. Notes Comput. Sci 623(07), 41–52 (1992)

    Article  MathSciNet  Google Scholar 

  24. Larson, J.A., Laver, R., Mcnulty, G.: Square-free and cube-free colorings of the ordinals. Pacific J Math 89, 07 (1980)

    Article  MathSciNet  Google Scholar 

  25. Leech, J.: A problem on strings of beads. Math. Gaz. 41, 277–278 (1957)

    Article  Google Scholar 

  26. Lothaire, M.: Algebraic Combinatorics on Words. Encyclopedia of Mathematics and its Applications. Cambridge University Press (2002)

  27. Morse, M.: A solution of the problem of finding an infinite play in chess. Bull. Amer. Math. Soc. 44, 632 (1938)

    Google Scholar 

  28. Morse, M, Hedlund, G.A.: Unending chess, symbolic dynamics and a problem in semigroups. Duke Math. J. 11(1), 1–7 (1944). 03

    Article  MathSciNet  Google Scholar 

  29. Murskii, V.L.: Examples of varieties of semigroups. Mathematical notes of the Academy of Sciences of the USSR 3(6), 423–427 (Jun 1968)

  30. Novikov, P.S., Adjan, S.I.: Infinite periodic groups. iii. Mathematics of the USSR-Izvestiya 2(3), 665 (1968)

    Article  Google Scholar 

  31. Pleasants, P.A.: Non-repetitive sequences. Mat. Proc. Camb. Phil. Soc. 68, 267–274 (1970)

    Article  MathSciNet  Google Scholar 

  32. Prouhet, M.E.: Mémoire sur quelques relations entre les puissances des nombres. C. R. Acad. Sci. Paris 33(A), 03 (1851)

    Google Scholar 

  33. Entringer, D., Jackson R., Schatz, J.: On nonrepetitive sequences. J. Combinatorial Theory 16, 159–164 (1974)

    Article  MathSciNet  Google Scholar 

  34. Ramsey, F.P.: On a problem of formal logic. Proc. Lond. Math. Soc s2–30(1), 264–286 (1930). 01

    Article  MathSciNet  Google Scholar 

  35. Rytter, W, Shur, A.M.: Searching for Zimin patterns. Theor. Comput. Sci. 571, 50–57 (2015)

    Article  MathSciNet  Google Scholar 

  36. Sapir, M.V.: Problems of Burnside type and the finite basis property in varieties of semi- groups. Izv. Akad. Nauk. SSSR. Ser. Mat. 51, 319–340 (1987)

    Google Scholar 

  37. Sapir, M.V., Guba, V.S., Volkov, M.V: Combinatorial Algebra: Syntax and Semantics. Springer Monographs in Mathematics. Springer International Publishing (2016)

  38. Tarski, A: The concept of truth in formalized languages. In: Logic, Semantics, Metamathematics, pp. 152–278. Oxford University Press, Oxford. 1936/1956. Translation, by Joseph H. Woodger, tarski36 (1933)

  39. Thue, A.: Über unendliche Zeichenreihen. Skrifter udgivne af Videnskabsselskabet i Christiania: Mathematisk-naturvidenskabelig Klasse (1906)

  40. Zimin, A.I.: Blocking sets of terms. Math. USSR-Sb. 47(2), 353 (1984)

    Article  Google Scholar 

Download references

Acknowledgements

My deepest thanks go to Willem Fouché, Petrus Potgieter, Pascal Vanier, Arno Pauly, Holger Spakowski, Niko Sauer, Narad Rampersad and James Currie. Without their generous patience, deep insight, diligence and kindness, this paper would not have been possible. Many thanks also to the wonderful anonymous editors and reviewers of TOCS. This paper has been written in partial fulfillment of the requirements for the degree Doctor of Philosophy in Operations Research at the University of South Africa.

Author information

Authors and Affiliations

  1. University of South Africa, Department of Decision Sciences, Unisa Muckleneuk Campus Preller Street Muckleneuk, Pretoria, South Africa

    Paul Sauer

Authors
  1. Paul Sauer
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Paul Sauer.

Additional information

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Sauer, P. The Complexity of Unavoidable Word Patterns. Theory Comput Syst 66, 802–820 (2022). https://doi.org/10.1007/s00224-022-10090-z

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00224-022-10090-z

Keywords

Search

Navigation