Title: General Algorithms for Testing the Ambiguity of Finite Automata

(NYU-CS-TR908)

Authors: Cyril Allauzen, Mehryar Mohri and Ashish Rastogi

Abstract:
This paper presents efficient algorithms for testing the finite,
polynomial, and exponential ambiguity of finite automata with
$\epsilon$-transitions. It gives an algorithm for testing the exponential
ambiguity of an automaton $A$ in time $O(|A|_E2)$, and finite or
polynomial ambiguity in time $O(|A|_E3)$. These complexities
significantly improve over the previous best complexities given for
the same problem. Furthermore, the algorithms presented are simple
and are based on a general algorithm for the composition or
intersection of automata. We also give an algorithm to determine the
degree of polynomial ambiguity of a finite automaton $A$ that is
polynomially ambiguous in time $O(|A|_E3)$. Finally, we present an
application of our algorithms to an approximate computation of the
entropy of a probabilistic automaton.