Name
Abstract | ||
|---|---|---|
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 @W(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^.^4^m), where m is the length of the pattern. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.tcs.2009.07.024 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
maximal size,Boyer-Moore automaton,binary pattern,exponential O,large Boyer-Moore automaton,pattern matching,experimental result,famous paper,finite class,particular case | Journal | 410 |
Issue | ISSN | Citations |
43 | 0304-3975 | 1 |
PageRank | References | Authors |
0.35 | 4 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ricardo Baeza-Yates | 1 | 6173 | 635.97 |
| Véronique Bruyère | 2 | 429 | 43.59 |
| O Delgrange | 3 | 112 | 11.20 |
| Rodrigo Scheihing | 4 | 6 | 1.02 |