Geodesic
Computing Depths of Patterns
Blanchet-Sadri, F.1 ; Lohr, Andrew2
1 Department of Computer Science, University of North Carolina, P.O. Box 26170, Greensboro, NC 27402–6170, USA.
2 Department of Mathematics, Rutgers University, 110 Frelinghuysen Rd., Piscataway, NJ 08854–8019, USA.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 50 (2016) no. 2, pp. 117-133

Voir la notice de l'article provenant de la source Numdam

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.

Reçu le :
Accepté le :
DOI : 10.1051/ita/2016014
Classification : 68R15
Keywords: Formal languages, combinatorics on words, pattern avoidance, partial words, depth of pattern

Blanchet-Sadri, F. 1 ; Lohr, Andrew 2

1 Department of Computer Science, University of North Carolina, P.O. Box 26170, Greensboro, NC 27402–6170, USA.
2 Department of Mathematics, Rutgers University, 110 Frelinghuysen Rd., Piscataway, NJ 08854–8019, USA. 
@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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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

Cité par Sources :