Hostname: page-component-586b7cd67f-t8hqh Total loading time: 0 Render date: 2024-11-26T17:53:12.862Z Has data issue: false hasContentIssue false
  • English
  • Français

Abelian pattern avoidance in partial words∗

Published online by Cambridge University Press:  10 June 2014

F. Blanchet-Sadri ,
Benjamin De Winkle  and
Sean Simmons
F. Blanchet-Sadri
Affiliation:
Department of Computer Science, University of North Carolina, P.O. Box 26170, Greensboro, NC 27402–6170, USA.. [email protected]
Benjamin De Winkle
Affiliation:
Department of Mathematics, Pomona College, 610 North College Avenue, Claremont, CA 91711–4411, USA.
Sean Simmons
Affiliation:
Department of Mathematics, Massachusetts Institute of Technology, Building 2, Room 236, 77 Massachusetts Avenue, Cambridge, MA 02139–4307, USA.
Get access

Abstract

Pattern avoidance is an important topic in combinatorics on words which dates back to the beginning of the twentieth century when Thue constructed an infinite word over a ternary alphabet that avoids squares, i.e., a word with no two adjacent identical factors. This result finds applications in various algebraic contexts where more general patterns than squares are considered. On the other hand, Erdős raised the question as to whether there exists an infinite word that avoids abelian squares, i.e., a word with no two adjacent factors being permutations of one another. Although this question was answered affirmately years later, knowledge of abelian pattern avoidance is rather limited. Recently, (abelian) pattern avoidance was initiated in the more general framework of partial words, which allow for undefined positions called holes. In this paper, we show that any pattern p with n> 3 distinct variables of length at least 2n is abelian avoidable by a partial word with infinitely many holes, the bound on the length of p being tight. We complete the classification of all the binary and ternary patterns with respect to non-trivial abelian avoidability, in which no variable can be substituted by only one hole. We also investigate the abelian avoidability indices of the binary and ternary patterns.

Keywords

Combinatorics on wordspartial wordsabelian powerspatternsabelian patternsavoidable patternsavoidability index
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 48 , Issue 3: Special issue in the honor of the 14th “Journées montoises d’informatique théorique”. I. , July 2014 , pp. 315 - 339
Copyright
© EDP Sciences 2014

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Berstel, J. and Boasson, L., Partial words and a theorem of Fine and Wilf. Theoret. Comput. Sci. 218 (1999) 135–141. Google Scholar
F. Blanchet-Sadri, Algorithmic Combinatorics on Partial Words. Chapman & Hall/CRC Press, Boca Raton, FL (2008).
F. Blanchet-Sadri and S. Simmons, Abelian pattern avoidance in partial words, in MFCS 2012, 37th International Symposium on Mathematical Foundations of Computer Science. Edited by B. Rovan, V. Sassone and P. Widmayer. Vol. 7464 of Lect. Notes Comput. Sci. Springer-Verlag, Berlin (2012) 210–221.
Blanchet-Sadri, F., Kim, J.I., Mercaş, R., Severa, W., Simmons, S. and Xu, D., Avoiding abelian squares in partial words. J. Combin. Theory, Ser. A 119 (2012) 257–270. Google Scholar
Blanchet-Sadri, F., Lohr, A. and Scott, S., Computing the partial word avoidability indices of binary patterns. J. Discrete Algorithms 23 (2013) 113–118 Google Scholar
Blanchet-Sadri, F., A. Lohr and S. Scott. Computing the partial word avoidability indices of ternary patterns. J. Discrete Algorithms 23 (2013) 119–142 Google Scholar
Blanchet-Sadri, F., Simmons, S. and Xu, D., Abelian repetitions in partial words. Adv. Appl. Math. 48 (2012) 194–214. Google Scholar
Currie, J.D., Pattern avoidance: themes and variations. Theoret. Comput. Sci. 339 (2005) 7–18. Google Scholar
Currie, J. and Linek, V., Avoiding patterns in the abelian sense. Can. J. Math. 53 (2001) 696–714. Google Scholar
Currie, J. and Visentin, T., On abelian 2-avoidable binary patterns. Acta Informatica 43 (2007) 521–533. Google Scholar
Currie, J. and Visentin, T., Long binary patterns are abelian 2-avoidable. Theoret. Comput. Sci. 409 (2008) 432–437. Google Scholar
Dekking, F.M., Strongly non-repetitive sequences and progression-free sets. J. Combin. Theory, Ser. A 27 (1979) 181–185. Google Scholar
Erdős, P., Some unsolved problems. Magyar Tudományos Akadémia Matematikai Kutató Intézete Közl. 6 (1961) 221–254. Google Scholar
V. Keränen, Abelian squares are avoidable on 4 letters, in ICALP 1992, 19th International Colloquium on Automata, Languages and Programming. Edited by W. Kuich, vol. 623 of Lect. Notes Comput. Sci. Springer-Verlag, Berlin (1992) 41–52.
P. Leupold, Partial words for DNA coding, in 10th International Workshop on DNA Computing. Edited by G. Rozenberg, P. Yin, E. Winfree, J.H. Reif, B.-T. Zhang, M.H. Garzon, M. Cavaliere, M.J. Pérez-Jiménez, L. Kari and S. Sahu. Vol. 3384 of Lect. Notes Comput. Sci. Springer-Verlag, Berlin (2005) 224–234.
M. Lothaire, Algebraic Combinatorics on Words. Cambridge University Press, Cambridge (2002).
Pleasants, P.A.B., Non repetitive sequences. Proc. Cambridge Philosophical Soc. 68 (1970) 267–274. Google Scholar
Thue, A., Über unendliche Zeichenreihen. Norske Vid. Selsk. Skr. I, Mat. Nat. Kl. Christiana 7 (1906) 1–22. Google Scholar