Document Open Access Logo

Every Binary Pattern of Length Greater Than 14 Is Abelian-2-Avoidable

Author Matthieu Rosenfeld

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2016.81.pdf
  • Filesize: 422 kB
  • 11 pages

Document Identifiers

Author Details

Matthieu Rosenfeld

Cite As Get BibTex

Matthieu Rosenfeld. Every Binary Pattern of Length Greater Than 14 Is Abelian-2-Avoidable. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 81:1-81:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.MFCS.2016.81

Abstract

We show that every binary pattern of length greater than 14 is abelian-2-avoidable. The best known upper bound on the length of abelian-2-unavoidable binary pattern was 118, and the best known lower bound is 7.

We designed an algorithm to decide, under some reasonable assumptions, if a morphic word avoids a pattern in the abelian sense. This algorithm is then used to show that some binary patterns are abelian-2-avoidable. We finally use this list of abelian-2-avoidable pattern to show our result. We also discuss the avoidability of binary patterns on 3 and 4 letters.

Subject Classification

Keywords
  • combinatorics on words
  • pattern avoidance
  • abelian repetitions

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. K. A. Baker, G. F. McNulty, and W. Taylor. Growth problems for avoidable words. Theoretical Computer Science, 69(3):319-345, 1989. URL: http://dx.doi.org/10.1016/0304-3975(89)90071-6.
  2. D. R. Bean, A. Ehrenfeucht, and G. F. McNulty. Avoidable patterns in strings of symbols. Pacific J. Math., 85(2):261-294, 1979. Google Scholar
  3. F. Blanchet-Sadri and B. Woodhouse. Strict bounds for pattern avoidance. Theoretical Computer Science, 506:17-27, 2013. Google Scholar
  4. J. Cassaigne. Unavoidable binary patterns. Acta Informatica, 30(4):385-395. URL: http://dx.doi.org/10.1007/BF01209712.
  5. J. D. Currie and N. Rampersad. Fixed points avoiding abelian k-powers. Journal of Combinatorial Theory, Series A, 119(5):942-948, July 2012. URL: http://dx.doi.org/10.1016/j.jcta.2012.01.006.
  6. J. D. Currie and T. I. Visentin. Long binary patterns are abelian 2-avoidable. Theoretical Computer Science, 409(3):432-437, 2008. URL: http://dx.doi.org/10.1016/j.tcs.2008.08.039.
  7. F. M. Dekking. Strongly non-repetitive sequences and progression-free sets. Journal of Combinatorial Theory, Series A, 27(2):181-185, 1979. URL: http://dx.doi.org/10.1016/0097-3165(79)90044-X.
  8. P. Erdős. Some unsolved problems. The Michigan Mathematical Journal, 4(3):291-300, 1957. URL: http://dx.doi.org/10.1307/mmj/1028997963.
  9. P. Erdős. Some unsolved problems. Magyar Tud. Akad. Mat. Kutató Int. Közl., 6:221-254, 1961. Google Scholar
  10. A. A. Evdokimov. Strongly asymmetric sequences generated by a finite number of symbols. Dokl. Akad. Nauk SSSR, 179:1268-1271, 1968. Google Scholar
  11. V. Keränen. Abelian squares are avoidable on 4 letters. In ICALP, pages 41-52, 1992. Google Scholar
  12. V. Keränen. New abelian square-free DT0L-languages over 4 letters. Manuscript, 2003. Google Scholar
  13. M. Lothaire. Combinatorics on Words. Cambridge University Press, 1997. Google Scholar
  14. R. Mercas, P. Ochem, A. V. Samsonov, and A. M. Shur. Binary patterns in binary cube-free words: Avoidability and growth. RAIRO - Theor. Inf. and Applic, 48(4):369-389, 2014. Google Scholar
  15. P. Ochem. Doubled patterns are 3-avoidable. Electron. J. Combinatorics., 23(1), 2016. Google Scholar
  16. P. Ochem and A. Pinlou. Application of entropy compression in pattern avoidance. Electron. J. Combinatorics., 21(2), 2014. Google Scholar
  17. P. A. B. Pleasants. Non-repetitive sequences. Mathematical Proceedings of the Cambridge Philosophical Society, 68:267-274, 9 1970. URL: http://dx.doi.org/10.1017/S0305004100046077.
  18. M. Rao and M. Rosenfeld. On Mäkelä’s Conjectures: deciding if a morphic word avoids long abelian-powers. ArXiv e-prints, November 2015. URL: http://arxiv.org/abs/1511.05875.
  19. M. Rao and M. Rosenfeld. Avoidability of long k-abelian repetitions. Mathematics of Computation, in press 2015. Google Scholar
  20. P. Roth. Every binary pattern of length six is avoidable on the two-letter alphabet. Acta Informatica, 29(1):95-107. URL: http://dx.doi.org/10.1007/BF01178567.
  21. U. Schmidt. Avoidable patterns on two letters. Theoretical Computer Science, 63(1):1-17, 1989. URL: http://dx.doi.org/10.1016/0304-3975(89)90064-9.
  22. A. Thue. Über unendliche Zeichenreihen. Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiania,, 1906. Google Scholar
  23. A. Thue. Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiania,, 10:1-67, 1912. Google Scholar
  24. A. I. Zimin. Blocking sets of terms. Sbornik: Mathematics, 47(2):353-364, 1984. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact