Geodesic
Counting bordered partial words by critical positions
The electronic journal of combinatorics, Tome 18 (2011) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

A partial word, sequence over a finite alphabet that may have some undefined positions or holes, is bordered if one of its proper prefixes is compatible with one of its suffixes. The number theoretical problem of enumerating all bordered full words (the ones without holes) of a fixed length $n$ over an alphabet of a fixed size $k$ is well known. It turns out that all borders of a full word are simple, and so every bordered full word has a unique minimal border no longer than half its length. Counting bordered partial words having $h$ holes with the parameters $k, n$ is made extremely more difficult by the failure of that combinatorial property since there is now the possibility of a minimal border that is nonsimple. Here, we give recursive formulas based on our approach of the so-called simple and nonsimple critical positions.
DOI : 10.37236/625
Classification : 68R15, 68Q45, 05A05
Mots-clés : partial words, bordered partial words, simply bordered partial words 
@article{10_37236_625,
     author = {Emily Allen and F. Blanchet-Sadri and Cameron Byrum and Mihai Cucuringu and Robert Merca\c{s}},
     title = {Counting bordered partial words by critical positions},
     journal = {The electronic journal of combinatorics},
     year = {2011},
     volume = {18},
     number = {1},
     doi = {10.37236/625},
     zbl = {1221.68174},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/625/}
}
TY  - JOUR
AU  - Emily Allen
AU  - F. Blanchet-Sadri
AU  - Cameron Byrum
AU  - Mihai Cucuringu
AU  - Robert Mercaş
TI  - Counting bordered partial words by critical positions
JO  - The electronic journal of combinatorics
PY  - 2011
VL  - 18
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/625/
DO  - 10.37236/625
ID  - 10_37236_625
ER  - 
%0 Journal Article
%A Emily Allen
%A F. Blanchet-Sadri
%A Cameron Byrum
%A Mihai Cucuringu
%A Robert Mercaş
%T Counting bordered partial words by critical positions
%J The electronic journal of combinatorics
%D 2011
%V 18
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/625/
%R 10.37236/625
%F 10_37236_625
Emily Allen; F. Blanchet-Sadri; Cameron Byrum; Mihai Cucuringu; Robert Mercaş. Counting bordered partial words by critical positions. The electronic journal of combinatorics, Tome 18 (2011) no. 1. doi: 10.37236/625

Cité par Sources :