Name
Abstract | ||
|---|---|---|
The consequences of regular expression hashing as a means of finite state automaton reduction is explored, based on variations of Brzozowski's algorithm. In this approach, each hash collision results in the merging of the automaton's states, and it is subsequently shown that a super-automaton will always be constructed, regardless of the hash function used. Since direct adaptation of the classical Brzozowski algorithm leads to a non-deterministic super-automaton, a new algorithm is put forward for constructing a deterministic FA. Approaches are proposed for measuring the quality of a hash function.These ideas are empirically tested on a large sample of relatively small regular expressions and their associated automata, as well as on a small sample of relatively large regular expressions. Differences in the quality of tested hash functions are observed. Possible reasons for this are mentioned, but future empirical work is required to investigate the matter. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1142/S0129054109007042 | INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE |
Keywords | DocType | Volume |
Finite state automaton, DFA, NFA, state merging, equivalence classes, regular languages, super-automaton, hash function, minimization, exact automaton | Conference | 20 |
Issue | ISSN | Citations |
6 | 0129-0541 | 0 |
PageRank | References | Authors |
0.34 | 2 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wikus Coetser | 1 | 0 | 0.34 |
| Derrick G. Kourie | 2 | 223 | 33.10 |
| Bruce W. Watson | 3 | 338 | 53.24 |