| Parallel Algorithms for Finite Automata Problems (2000) | |||||||||||||||||
Abstract | |||||||||||||||||
| : Finite automata are among the most extensively studied and understood models of computation. They have wide ranging applications - for example, in image compression, protocol validation, game theory and computational biology - just to mention only some recent ones. Here we will survey efficient parallel algorithms for many fundamental computational problems on finite automata. It is well known that problems involving deterministic finite automata (DFA) have polynomial time algorithms, but the problems become hard when the input automata are nondeterministic (NFA or regular expressions) . A similar difference is observed in the case of parallel algorithms: most problems involving DFA as input have NC algorithms, while NC algorithms are unlikely with NFA (or regular expression) as input. In addition to DFA and NFA, we will also consider other inputs such as unambiguous finite automata, regular expressions and prefix grammars. The problems surveyed here include the followin... | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||