Dynamic allocation of finite automata states for fast string recognition

dc.contributor.author	Ngassam E.K.	en
dc.contributor.author	Watson B.W.	en
dc.contributor.author	Kourie D.G.	en
dc.date.accessioned	2012-11-01T16:31:29Z
dc.date.available	2012-11-01T16:31:29Z
dc.date.issued	2006	en
dc.identifier.citation	International Journal of Foundations of Computer Science	en
dc.identifier.citation	17	en
dc.identifier.citation	6	en
dc.identifier.issn	1290541	en
dc.identifier.other	10.1142/S0129054106004431	en
dc.identifier.uri	http://hdl.handle.net/10500/7295
dc.description.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.	en
dc.language.iso	en	en
dc.subject	Automata; Cache locality of reference; Dynamic state allocation; Implementation; Performance	en
dc.title	Dynamic allocation of finite automata states for fast string recognition	en
dc.type	Conference Paper	en