Voir la notice de l'article provenant de la source Numdam
Multiwords are words in which a single symbol can be replaced by a nonempty set of symbols. They extend the notion of partial words. A word w is certain in a multiword M if it occurs in every word that can be obtained by selecting one single symbol among the symbols provided in each position of M. Motivated by a problem on incomplete databases, we investigate a variant of the pattern matching problem which is to decide whether a word w is certain in a multiword M. We study the language CERTAIN(w) of multiwords in which w is certain. We show that this regular language is aperiodic for three large families of words. We also show its aperiodicity in the case of partial words over an alphabet with at least three symbols.
@article{ITA_2012__46_1_33_0,
author = {Bruy\`ere, V\'eronique and Carton, Olivier and Decan, Alexandre and Gauwin, Olivier and Wijsen, Jef},
title = {An aperiodicity problem for multiwords},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {33--50},
publisher = {EDP-Sciences},
volume = {46},
number = {1},
year = {2012},
doi = {10.1051/ita/2011131},
mrnumber = {2904959},
zbl = {1247.68203},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2011131/}
}
TY - JOUR AU - Bruyère, Véronique AU - Carton, Olivier AU - Decan, Alexandre AU - Gauwin, Olivier AU - Wijsen, Jef TI - An aperiodicity problem for multiwords JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2012 SP - 33 EP - 50 VL - 46 IS - 1 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ita/2011131/ DO - 10.1051/ita/2011131 LA - en ID - ITA_2012__46_1_33_0 ER -
%0 Journal Article %A Bruyère, Véronique %A Carton, Olivier %A Decan, Alexandre %A Gauwin, Olivier %A Wijsen, Jef %T An aperiodicity problem for multiwords %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2012 %P 33-50 %V 46 %N 1 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ita/2011131/ %R 10.1051/ita/2011131 %G en %F ITA_2012__46_1_33_0
Bruyère, Véronique; Carton, Olivier; Decan, Alexandre; Gauwin, Olivier; Wijsen, Jef. An aperiodicity problem for multiwords. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012) no. 1, pp. 33-50. doi: 10.1051/ita/2011131
Cité par Sources :