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