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 (). 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