A Constant Time Algorithm for Deterministic Finite Automata Problem on a Reconfigurable Mesh
Young Hak Kim · The Transactions of the Korea Information Processing Society · 1999
Finite automation is a mathematical model to represent a system with discrete inputs and outputs. Finite automata are a useful tool for solving problems such as text editor, lexical analyzer, and switching circuit. In this paper, given a deterministic finite automaton of an input string of length n and m states, we propose a constant time parallel algorithm that represents the transition states of finite automata and determines the acceptance of an input string on a reconfigurable mesh of size [nm/2]2m.