Abelian pattern avoidance in partial words

F. Blanchet-Sadri; Benjamin De Winkle; Sean Simmons

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2014)

  • Volume: 48, Issue: 3, page 315-339
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Blanchet-Sadri, F., De Winkle, Benjamin, and Simmons, Sean. "Abelian pattern avoidance in partial words." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 48.3 (2014): 315-339. <http://eudml.org/doc/273019>.

@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&gt; 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&gt; 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 -

References

top
  1. [1] J. Berstel and L. Boasson, Partial words and a theorem of Fine and Wilf. Theoret. Comput. Sci.218 (1999) 135–141. Zbl0916.68120
  2. [2] F. Blanchet-Sadri, Algorithmic Combinatorics on Partial Words. Chapman & Hall/CRC Press, Boca Raton, FL (2008). Zbl1180.68205
  3. [3] 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. Zbl06086223
  4. [4] F. Blanchet-Sadri, J.I. Kim, R. Mercaş, W. Severa, S. Simmons and D. Xu, Avoiding abelian squares in partial words. J. Combin. Theory, Ser. A 119 (2012) 257–270. Zbl1233.68183
  5. [5] F. Blanchet-Sadri, A. Lohr and S. Scott, Computing the partial word avoidability indices of binary patterns. J. Discrete Algorithms23 (2013) 113–118 Zbl1334.68166
  6. [6] F. Blanchet-Sadri, A. Lohr and S. Scott. Computing the partial word avoidability indices of ternary patterns. J. Discrete Algorithms23 (2013) 119–142 Zbl1334.68167
  7. [7] F. Blanchet-Sadri, S. Simmons and D. Xu, Abelian repetitions in partial words. Adv. Appl. Math.48 (2012) 194–214. Zbl1231.68187MR2845515
  8. [8] J.D. Currie, Pattern avoidance: themes and variations. Theoret. Comput. Sci.339 (2005) 7–18. Zbl1076.68051MR2142070
  9. [9] J. Currie and V. Linek, Avoiding patterns in the abelian sense. Can. J. Math.53 (2001) 696–714. Zbl0986.68103MR1848503
  10. [10] J. Currie and T. Visentin, On abelian 2-avoidable binary patterns. Acta Informatica43 (2007) 521–533. Zbl1111.68094MR2309577
  11. [11] J. Currie and T. Visentin, Long binary patterns are abelian 2-avoidable. Theoret. Comput. Sci.409 (2008) 432–437. Zbl1171.68034MR2473917
  12. [12] F.M. Dekking, Strongly non-repetitive sequences and progression-free sets. J. Combin. Theory, Ser. A 27 (1979) 181–185. Zbl0437.05011MR542527
  13. [13] P. Erdős, Some unsolved problems. Magyar Tudományos Akadémia Matematikai Kutató Intézete Közl.6 (1961) 221–254. Zbl0100.02001
  14. [14] 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. MR1250629
  15. [15] 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. Zbl1116.68462MR2179040
  16. [16] M. Lothaire, Algebraic Combinatorics on Words. Cambridge University Press, Cambridge (2002). Zbl1221.68183MR1905123
  17. [17] P.A.B. Pleasants, Non repetitive sequences. Proc. Cambridge Philosophical Soc.68 (1970) 267–274. Zbl0237.05010MR265173
  18. [18] A. Thue, Über unendliche Zeichenreihen. Norske Vid. Selsk. Skr. I, Mat. Nat. Kl. Christiana 7 (1906) 1–22. JFM37.0066.17

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.