Ambiguity in Finite Automata - Schmidt, Erik Meineche (DAIMI Report Series, 1977)
The gain in succinctness of descriptions of regular languages when nondeterministic (unambiguous) finite automata are used rather than unambiguous (deterministic) finite automata, is not bounded by any polynomium. The problem of deciding whether an unambiguous regular expression does not generate all words over its terminal alphabet, is in NP.