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.
Mots-clés : combinatorics on words, partial words, abelian powers, patterns, abelian patterns, avoidable patterns, avoidability index
@article{ITA_2014__48_3_315_0,
author = {Blanchet-Sadri, F. and De Winkle, Benjamin and Simmons, Sean},
title = {Abelian pattern avoidance in partial words},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {315--339},
publisher = {EDP-Sciences},
volume = {48},
number = {3},
year = {2014},
doi = {10.1051/ita/2014014},
mrnumber = {3302491},
zbl = {1297.68190},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ita/2014014/}
}
TY - JOUR AU - Blanchet-Sadri, F. AU - De Winkle, Benjamin AU - Simmons, Sean TI - Abelian pattern avoidance in partial words JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2014 SP - 315 EP - 339 VL - 48 IS - 3 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ita/2014014/ DO - 10.1051/ita/2014014 LA - en ID - ITA_2014__48_3_315_0 ER -
%0 Journal Article %A Blanchet-Sadri, F. %A De Winkle, Benjamin %A Simmons, Sean %T Abelian pattern avoidance in partial words %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2014 %P 315-339 %V 48 %N 3 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ita/2014014/ %R 10.1051/ita/2014014 %G en %F ITA_2014__48_3_315_0
Blanchet-Sadri, F.; De Winkle, Benjamin; Simmons, Sean. Abelian pattern avoidance in partial words. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 48 (2014) no. 3, pp. 315-339. doi : 10.1051/ita/2014014. http://www.numdam.org/articles/10.1051/ita/2014014/
[1] and , Partial words and a theorem of Fine and Wilf. Theoret. Comput. Sci. 218 (1999) 135-141. | Zbl
[2] , Algorithmic Combinatorics on Partial Words. Chapman & Hall/CRC Press, Boca Raton, FL (2008). | Zbl
[3] and , 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.
[4] , , , , and , Avoiding abelian squares in partial words. J. Combin. Theory, Ser. A 119 (2012) 257-270. | Zbl
[5] , and , Computing the partial word avoidability indices of binary patterns. J. Discrete Algorithms 23 (2013) 113-118
[6] , and . Computing the partial word avoidability indices of ternary patterns. J. Discrete Algorithms 23 (2013) 119-142
[7] , and , Abelian repetitions in partial words. Adv. Appl. Math. 48 (2012) 194-214. | MR | Zbl
[8] , Pattern avoidance: themes and variations. Theoret. Comput. Sci. 339 (2005) 7-18. | MR | Zbl
[9] and , Avoiding patterns in the abelian sense. Can. J. Math. 53 (2001) 696-714. | MR | Zbl
[10] and , On abelian 2-avoidable binary patterns. Acta Informatica 43 (2007) 521-533. | MR | Zbl
[11] and , Long binary patterns are abelian 2-avoidable. Theoret. Comput. Sci. 409 (2008) 432-437. | MR | Zbl
[12] , Strongly non-repetitive sequences and progression-free sets. J. Combin. Theory, Ser. A 27 (1979) 181-185. | MR | Zbl
[13] , Some unsolved problems. Magyar Tudományos Akadémia Matematikai Kutató Intézete Közl. 6 (1961) 221-254. | Zbl
[14] , 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. | MR
[15] , 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. | MR | Zbl
[16] , Algebraic Combinatorics on Words. Cambridge University Press, Cambridge (2002). | MR | Zbl
[17] , Non repetitive sequences. Proc. Cambridge Philosophical Soc. 68 (1970) 267-274. | MR | Zbl
[18] , Über unendliche Zeichenreihen. Norske Vid. Selsk. Skr. I, Mat. Nat. Kl. Christiana 7 (1906) 1-22. | JFM
Cité par Sources :
