Abelian pattern avoidance in partial words

@article{Blanchet2014,
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.},
author = {Blanchet-Sadri, F., De Winkle, Benjamin, Simmons, Sean},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {combinatorics on words; partial words; abelian powers; patterns; abelian patterns; avoidable patterns; avoidability index},
language = {eng},
number = {3},
pages = {315-339},
publisher = {EDP-Sciences},
title = {Abelian pattern avoidance in partial words},
url = {http://eudml.org/doc/273019},
volume = {48},
year = {2014},
}

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
PB - EDP-Sciences
VL - 48
IS - 3
SP - 315
EP - 339
AB - 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.
LA - eng
KW - combinatorics on words; partial words; abelian powers; patterns; abelian patterns; avoidable patterns; avoidability index
UR - http://eudml.org/doc/273019
ER -