Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1051/ita/2011131 | RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS |
Keywords | Field | DocType |
Pattern matching,aperiodicity,partial words | Mathematics Subject Classification,Symbol,Arithmetic,Natural language processing,Artificial intelligence,Regular language,Aperiodic graph,Pattern matching,Mathematics,Alphabet | Journal |
Volume | Issue | ISSN |
46 | SP1 | 0988-3754 |
Citations | PageRank | References |
0 | 0.34 | 10 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Véronique Bruyère | 1 | 429 | 43.59 |
| Olivier Carton | 2 | 381 | 40.97 |
| Alexandre Decan | 3 | 118 | 11.57 |
| Olivier Gauwin | 4 | 95 | 10.81 |
| Jef Wijsen | 5 | 678 | 95.21 |