Prague Stringology Conference 2012

Thomas Hanneforth and Bruce W. Watson

An Efficient Parallel Determinisation Algorithm for Finite-state Automata

Abstract:
Determinisation of non-deterministic finite automata (NFA) is an important operation not only for optimisation purposes, but also the prerequisite for the complementation operation, which in turn is necessary for creating robust pattern matchers, for example in string replacement and robust parsing. In the paper, we present an efficient parallel determinisation algorithm based on a message-passing graph approach. In a number of experiments on a multicore machine we show that the parallel algorithm behaves very well for acyclic and cyclic NFAs of different sizes, especially in the worst case, where determinisation leads to an exponential blow-up of states.

Download article: Article in PostScript Article in PDF BibTeX Reference
 PostScript   PDF   BibTeX reference