A New Approach to Determinisation Using Bit-Parallelism

摘要

We present a new approach to the determinisation process of specified types of automata using bit-parallel algorithms. We present the determinisation of nondeterministic pattern matching automata (PMA) for approximate pattern matching and we introduce the determinisation of suffix automata. This new approach speeds the determinisation up to m times, where m is the length of the pattern searched by PMA, or accepted by the suffix automaton, respectively.