Pattern avoidance is an important research topic in combinatorics on words which dates back to Thue’s construction of an infinite word over three letters that avoids squares, i.e., a sequence with no two adjacent identical factors. This result finds applications in various algebraic contexts where more general patterns than squares are considered. A more general form of pattern avoidance has recently emerged to allow for undefined positions in sequences. New concepts on patterns such as depth have been introduced and a number of questions have been raised, some of them we answer. In the process, we prove a strict bound on the number of square occurrences in an unavoidable pattern, and consequently, any pattern with more square occurrences than distinct variables is avoidable over three letters. We also provide an algorithm that determines whether a given pattern is of bounded depth, and if so, computes its depth.
Accepté le :
DOI : 10.1051/ita/2016014
Mots clés : Formal languages, combinatorics on words, pattern avoidance, partial words, depth of pattern
@article{ITA_2016__50_2_117_0,
author = {Blanchet-Sadri, F. and Lohr, Andrew},
title = {Computing {Depths} of {Patterns}},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {117--133},
publisher = {EDP-Sciences},
volume = {50},
number = {2},
year = {2016},
doi = {10.1051/ita/2016014},
mrnumber = {3580106},
zbl = {1359.68237},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ita/2016014/}
}
TY - JOUR AU - Blanchet-Sadri, F. AU - Lohr, Andrew TI - Computing Depths of Patterns JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2016 SP - 117 EP - 133 VL - 50 IS - 2 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ita/2016014/ DO - 10.1051/ita/2016014 LA - en ID - ITA_2016__50_2_117_0 ER -
%0 Journal Article %A Blanchet-Sadri, F. %A Lohr, Andrew %T Computing Depths of Patterns %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2016 %P 117-133 %V 50 %N 2 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ita/2016014/ %R 10.1051/ita/2016014 %G en %F ITA_2016__50_2_117_0
Blanchet-Sadri, F.; Lohr, Andrew. Computing Depths of Patterns. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 50 (2016) no. 2, pp. 117-133. doi : 10.1051/ita/2016014. http://www.numdam.org/articles/10.1051/ita/2016014/
, and , Avoidable patterns in strings of symbols. Pacific J. Math. 85 (1979) 261–294. | DOI | MR | Zbl
F. Blanchet-Sadri, K. Black and A. Zemke, Unary pattern avoidance in partial words dense with holes. In LATA 2011, 5th International Conference on Language and Automata Theory and Applications. Vol. 6638 of Lect. Notes Comput. Sci., edited by A.-H. Dediu, S. Inenaga and C. Martín-Vide. Springer-Verlag. Berlin, Heidelberg. (2011) 155–166. | MR
, and , Abelian pattern avoidance in partial words. RAIRO-Theoretical Informatics and Applications 48 (2014) 315–339. | DOI | Numdam | MR | Zbl
, and , Computing the partial word avoidability indices of binary patterns. J. Discrete Algorithms 23 (2013) 113–118. | DOI | MR | Zbl
, and , Computing the partial word avoidability indices of ternary patterns. J. Discrete Algorithms 23 (2013) 119–142. | DOI | MR | Zbl
F. Blanchet-Sadri, A. Lohr, S. Simmons and B. Woodhouse, Computing depths of patterns. In LATA 2014, 8th International Conference on Language and Automata Theory and Applications. Vol. 8370 of Lect. Notes Comput. Sci., edited by A.-H. Dediu, C. Martín-Vide, J.-L. Sierra-Rodriguez and B. Truthe. Springer-Verlag. Berlin, Heidelberg (2014) 173–185. | MR
, , and , Avoidable binary patterns in partial words. Acta Inf. 48 (2011) 25–41. | DOI | MR | Zbl
and , Strict bounds for pattern avoidance. Theor. Comput. Sci. 506 (2013) 17–28. | DOI | MR | Zbl
J. Cassaigne, Motifs évitables et régularités dans les mots, Ph.D. thesis, Paris VI (1994).
, , and , Pattern avoidance in partial permutations. Electron. J. Combin. 18 (2011) P25. | DOI | MR | Zbl
, Pattern avoidance: themes and variations. Theoret. Comput. Sci. 339 (2005) 7–18. | DOI | MR | Zbl
A. Gagol, Pattern avoidance in partial words over a ternary alphabet. Ann. Univ. Mariae Curie-Sklodowska Lublin-Polonia LXIX (2015) 73–82. | MR
M. Lothaire, Combinatorics on Words. Cambridge University Press, Cambridge (1997). | MR | Zbl
M. Lothaire, Algebraic Combinatorics on Words. Cambridge University Press, Cambridge (2002). | Zbl
and , Freeness of partial words. Theoret. Comput. Sci. 389 (2007) 265–277. | DOI | MR | Zbl
, A generator of morphisms for infinite words. RAIRO: ITA 40 (2006) 427–441. | Numdam | MR | Zbl
and , Application of entropy compression in pattern avoidance. Electron. J. Combin. 21 (2014) P2.7. | DOI | MR | Zbl
, Blocking sets of terms. Mathematics of the USSR-Sbornik 47 (1984) 353–364. | DOI | MR | Zbl
Cité par Sources :
