| Issue |
RAIRO-Theor. Inf. Appl.
Volume 46, Number 1, January-March 2012
Special issue dedicated to the 13th "Journées Montoises d'Informatique Théorique"
|
|
|---|---|---|
| Page(s) | 33 - 50 | |
| DOI | https://doi.org/10.1051/ita/2011131 | |
| Published online | 23 November 2011 | |
An aperiodicity problem for multiwords
1
Universitéde Mons – UMONS, Institut d’Informatique, Belgium
first.last@umons.ac.be
2
Université Paris Diderot, LIAFA, France
olivier.carton@liafa.jussieu.fr
Received: 4 November 2010
Accepted: 17 October 2011
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.
Mathematics Subject Classification: 68R15 / 68Q45
Key words: Pattern matching / aperiodicity / partial words
© EDP Sciences 2011
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.