An aperiodicity problem for multiwords
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012) no. 1, pp. 33-50.

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.

DOI : https://doi.org/10.1051/ita/2011131
Classification : 68R15,  68Q45
Mots clés : pattern matching, aperiodicity, partial words
@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},
     zbl = {1247.68203},
     mrnumber = {2904959},
     language = {en},
     url = {http://www.numdam.org/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
DA  - 2012///
SP  - 33
EP  - 50
VL  - 46
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita/2011131/
UR  - https://zbmath.org/?q=an%3A1247.68203
UR  - https://www.ams.org/mathscinet-getitem?mr=2904959
UR  - https://doi.org/10.1051/ita/2011131
DO  - 10.1051/ita/2011131
LA  - en
ID  - ITA_2012__46_1_33_0
ER  - 
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. http://www.numdam.org/articles/10.1051/ita/2011131/

[1] A.V. Aho and M.J. Corasick, Efficient string matching: An aid to bibliographic search. Commun. ACM 18 (1975) 333-340. | MR 371172 | Zbl 0301.68048

[2] A.V. Aho, J.E. Hopcroft and J.D. Ullman, The Design and Analysis of Computer Algorithms. Addison-Wesley (1974). | MR 413592 | Zbl 0326.68005

[3] J. Berstel and L. Boasson, Partial words and a theorem of Fine and Wilf. Theoret. Comput. Sci. 218 (1999) 135-141. | MR 1687780 | Zbl 0916.68120

[4] F. Blanchet-Sadri, Algorithmic Combinatorics on Partial Words (Discrete Mathematics and Its Applications). Chapman & Hall/CRC (2007). | MR 2384993 | Zbl 1180.68205

[5] R.S. Boyer and J.S. Mooren, A fast string searching algorithm. Commun. ACM 20 (1977) 762-772. | Zbl 1219.68165

[6] V. Bruyère, A. Decan and J. Wijsen, On first-order query rewriting for incomplete database histories, in Proc. of the 16th International Symposium on Temporal Representation and Reasoning (TIME) (2009) 54-61.

[7] M. Crochemore and W. Rytter, Text Algorithms. Oxford University Press (1994). | MR 1307378 | Zbl 0844.68101

[8] M. Crochemore, C. Hancart and T. Lecroq, Algorithms on Strings. Cambridge University Press (2007) 392. | MR 2355493 | Zbl 1137.68060

[9] N.J. Fine and H.S. Wilf, Uniqueness theorems for periodic functions. Proc. of Amer. Math. Soc. 16 (1965) 109-114. | MR 174934 | Zbl 0131.30203

[10] M.J. Fischer and M.S. Paterson, String matching and other products. SIAM-AMS Proceedings, Complexity of Computation 7 (1974) 113-125. | MR 400782 | Zbl 0301.68027

[11] V. Halava, T. Harju and T. Kärki, Relational codes of words. Theoret. Comput. Sci. 389 (2007) 237-249. | MR 2363375 | Zbl 1143.68036

[12] J. Holub, W.F. Smyth and S. Wang, Fast pattern-matching on indeterminate strings. J. Discrete Algorithms 6 (2008) 37-50. | MR 2397082 | Zbl 1162.68808

[13] D.E. Knuth, J.H. Morris and V.R. Pratt, Fast pattern matching in strings. SIAM J. Comput. 6 (1977) 323-350. | MR 451916 | Zbl 0372.68005

[14] G. Kucherov, L. Noé and M.A. Roytberg, Subset seed automaton, in Proc. of the 12th International Conference on Implementation and Application of Automata (CIAA). Springer (2007) 180-191. | MR 2595438 | Zbl 1139.68369

[15] M. Lothaire, Combinatorics on words. Cambridge University Press (1997). | MR 1475463 | Zbl 0874.20040

[16] R. Mcnaughton and S. Papert, Counter-free Automata. MIT Press, Cambridge, MA (1971). | MR 371538 | Zbl 0232.94024

[17] J.-É. Pin, Varieties of Formal Languages. North Oxford, London and Plenum, New-York (1986). | Zbl 0632.68069

[18] M.S. Rahman, C.S. Iliopoulos and L. Mouchard, Pattern matching in degenerate DNA/RNA sequences, in Workshop on Algorithms and Computation (WALCOM), edited by M. Kaykobad and M.S. Rahman. Bangladesh Academy of Sciences (BAS) (2007) 109-120. | MR 2552884

[19] M.P. Schützenberger, On finite monoids having only trivial subgroups. Inform. Control 8 (1965) 190-194. | MR 176883 | Zbl 0131.02001

Cité par Sources :