Finite Automata Implementations Considering CPU Cache

Authors

  • J. Holub

DOI:

https://doi.org/10.14311/1008

Keywords:

deterministic finite automaton, CPU cache, implementation

Abstract

The finite automata are mathematical models for finite state systems. More general finite automaton is the nondeterministic finite automaton (NFA) that cannot be directly used. It is usually transformed to the deterministic finite automaton (DFA) that then runs in time O(n), where n is the size of the input text. We present two main approaches to practical implementation of DFA considering CPU cache. The first approach (represented by Table Driven and Hard Coded implementations) is suitable forautomata being run very frequently, typically having cycles. The other approach is suitable for a collection of automata from which various automata are retrieved and then run. This second kind of automata are expected to be cycle-free. 

Downloads

Download data is not yet available.

Author Biography

J. Holub

Downloads

Published

2007-01-06

How to Cite

Holub, J. (2007). Finite Automata Implementations Considering CPU Cache. Acta Polytechnica, 47(6). https://doi.org/10.14311/1008

Issue

Section

Articles