The Prague Stringology Conference 2005
Ernest Ketcha Ngassam, Derrick G. Kourie and Bruce W. Watson
Reordering Finite Automata States for Fast String Recognition
| Abstract: |
| The spatial and temporal locality of reference on which cache memory relies to minimize cache swaps, is exploited to design a new algorithm for finite automaton string recognition. It is shown that the algorithm, referred to as the state reordering algorithm, outperforms the traditional table-driven algorithm for strings that tend to repeatedly access the same set of states. |
| Download paper: |  |
 |
| PostScript |