DI-UMONS : Dépôt institutionnel de l’université de Mons

Recherche transversale
(titres de publication, de périodique et noms de colloque inclus)
2009-10-01 - Article/Dans un journal avec peer-review - Anglais - 12 page(s)

Baeza-Yates Ricardo, Bruyère Véronique , Delgrange Olivier , Scheihing Rodrigo, "On the size of Boyer-Moore automata" in Theoretical Computer Science, 410, 43, 4432-4443

  • Edition : Elsevier Science, Amsterdam (The Netherlands)
  • Codes CREF : Théorie des graphes (DI1146), Informatique mathématique (DI1160)
  • Unités de recherche UMONS : Informatique théorique (S829)
Texte intégral :

Abstract(s) :

(Anglais) In this work we study the size of Boyer-Moore automata introduced in Knuth, Morris & Pratt's famous paper on pattern matching. We experimentally show that a finite class of binary patterns produce very large Boyer-Moore automata, and find one particular case which we conjecture, generates automata of size Omeg (m^6). Further experimental results suggest that the maximal size could be a polynomial of O(m^7), or even an exponential O(2^0.4m), where m is the length of the pattern.