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 article: Article in PostScript Article in PDF
 PostScript   PDF