Andreas Weber and Helmut Seidl. On the Degree of Ambiguity of Finite Automata. Theor. Comput. Sci., 88(2):325-349, 1991.

We show that the degree of ambiguity of a nondeterministic finite automaton (NFA) with n states, if finite, is not greater than $2^{n\cdot log_2 n + c _1\cdot n}$ ($c_1 \cong 2.0566$). We present an algorithm which decides in polynomial time whether the degree of ambiguity of a NFA is finite or not. Additionally, the authors obtain in [14] a corresponding upper bound for the finite valuedness of a normalized finite transducer (NFT), and also a polynomial-time algorithm which decides whether the valuedness of a NFT is finite or not

Download: PDF Reference: Bibtex