Efficient Simulation of Nondeterministic Weighted Finite Automata
Mark Eramian · Journal of automata, languages and combinatorics · 2004
Simulation of nondeterministic automata is often required in algorithms for string matching and image compression. We give three algorithms for NWFA simulation and compare them with known methods. When we consider the problem of computing the acceptance weight of all words of a given finite length, we find that the best of the three algorithms is comparable with a recursive version of a known sparse matrix based algorithm with respect to time, but offers an implementation with simpler data structures.