An aperiodicity problem for multiwords

Véronique Bruyère; Olivier Carton; Alexandre Decan; Olivier Gauwin; Jef Wijsen

RAIRO - Theoretical Informatics and Applications (2012)

  • Volume: 46, Issue: 1, page 33-50
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Bruyère, Véronique, et al. "An aperiodicity problem for multiwords." RAIRO - Theoretical Informatics and Applications 46.1 (2012): 33-50. <http://eudml.org/doc/221995>.

@article{Bruyère2012,
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. },
author = {Bruyère, Véronique, Carton, Olivier, Decan, Alexandre, Gauwin, Olivier, Wijsen, Jef},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Pattern matching; aperiodicity; partial words; pattern matching},
language = {eng},
month = {3},
number = {1},
pages = {33-50},
publisher = {EDP Sciences},
title = {An aperiodicity problem for multiwords},
url = {http://eudml.org/doc/221995},
volume = {46},
year = {2012},
}

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
DA - 2012/3//
PB - EDP Sciences
VL - 46
IS - 1
SP - 33
EP - 50
AB - 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.
LA - eng
KW - Pattern matching; aperiodicity; partial words; pattern matching
UR - http://eudml.org/doc/221995
ER -

References

top
  1. A.V. Aho and M.J. Corasick, Efficient string matching: An aid to bibliographic search. Commun. ACM18 (1975) 333–340.  Zbl0301.68048
  2. A.V. Aho, J.E. Hopcroft and J.D. Ullman, The Design and Analysis of Computer Algorithms. Addison-Wesley (1974).  Zbl0326.68005
  3. J. Berstel and L. Boasson, Partial words and a theorem of Fine and Wilf. Theoret. Comput. Sci.218 (1999) 135–141.  Zbl0916.68120
  4. F. Blanchet-Sadri, Algorithmic Combinatorics on Partial Words (Discrete Mathematics and Its Applications). Chapman & Hall/CRC (2007).  
  5. R.S. Boyer and J.S. Mooren, A fast string searching algorithm. Commun. ACM20 (1977) 762–772.  Zbl1219.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).  Zbl0844.68101
  8. M. Crochemore, C. Hancart and T. Lecroq, Algorithms on Strings. Cambridge University Press (2007) 392.  Zbl1137.68060
  9. N.J. Fine and H.S. Wilf, Uniqueness theorems for periodic functions. Proc. of Amer. Math. Soc.16 (1965) 109–114.  Zbl0131.30203
  10. M.J. Fischer and M.S. Paterson, String matching and other products. SIAM-AMS Proceedings, Complexity of Computation7 (1974) 113–125.  Zbl0301.68027
  11. V. Halava, T. Harju and T. Kärki, Relational codes of words. Theoret. Comput. Sci.389 (2007) 237–249.  Zbl1143.68036
  12. J. Holub, W.F. Smyth and S. Wang, Fast pattern-matching on indeterminate strings. J. Discrete Algorithms6 (2008) 37–50.  Zbl1162.68808
  13. D.E. Knuth, J.H. Morris and V.R. Pratt, Fast pattern matching in strings. SIAM J. Comput.6 (1977) 323–350.  Zbl0372.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.  
  15. M. Lothaire, Combinatorics on words. Cambridge University Press (1997).  Zbl0874.20040
  16. R. McNaughton and S. Papert, Counter-free Automata. MIT Press, Cambridge, MA (1971).  Zbl0232.94024
  17. J.-É. Pin, Varieties of Formal Languages. North Oxford, London and Plenum, New-York (1986).  
  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.  Zbl1160.68684
  19. M.P. Schützenberger, On finite monoids having only trivial subgroups. Inform. Control8 (1965) 190–194.  Zbl0131.02001

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.