Dynamic allocation of finite automata states for fast string recognition
No Thumbnail Available
Authors
Ngassam E.K.
Watson B.W.
Kourie D.G.
Issue Date
2006
Type
Conference Paper
Language
en
Keywords
Automata; Cache locality of reference; Dynamic state allocation; Implementation; Performance
Alternative Title
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 Dynamic State Allocation algorithm outperforms the traditional table-driven algorithm for strings that tend to repeatedly access the same set of states, provided that the string is long enough to amortize the allocation cost. Further improvements on the algorithm result in even better performance. © World Scientific Publishing Company.
Description
Citation
International Journal of Foundations of Computer Science
17
6
17
6
Publisher
License
Journal
Volume
Issue
PubMed ID
DOI
ISSN
1290541