The Prague Stringology Conference 2008
Wikus Coetser, Derrick G. Kourie and Bruce W. Watson
On Regular Expression Hashing to Reduce FA Size
| Abstract: |
| In [7], a new version of Brzozowski's algorithm was put forward which relies on regular expression hashing to possibly decrease the number of states in the generated finite state automata. This method utilizes a hash function to decide which states are merged, but does not, in general, construct *-equivalence classes on automaton states, as is done in minimization algorithms. The consequences of this approach depends on the hash function used, and include the construction of a super-automaton and potential non-determinism. A revised version of the hashing algorithm in [7] is presented that constructs a deterministic automaton. A method for rewriting the hash function input is presented that allows the construction of a hash function that is an injection, mapping a unique integer to each regular language. A method for measuring the difference between the exact- and super-automaton is presented. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |
| Download presentations: |  |
|