An Efficient Parallel Determinisation Algorithm for Finite-state Automata
Thomas Hanneforth, Bruce W. Watson · 2012
Abstract. Determinisation of non-deterministic finite automata (NFA) is an impor-tant operation not only for optimisation purposes, but also the prerequisite for the com-plementation 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 ef-ficient 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.