Unambiguous Finite Automatons (UFA) are special type of non-deterministic finite automatons (NFA).
A NFA is called $unambiguous$ if every word $w\in \Sigma^*$ has at most one accepting path.
This means $DFA\subset UFA\subset NFA$.
Known related automaton results:
- NFA minimization is PSPACE-Complete.
- NFA minimization over finite languages is DP-Hard.
- UFA minimization is NP-Complete.
- There exists NFAs which are exponentially smaller than minimal DFAs. (Also - there exists UFAs which are exponentially smaller than minimal DFAs - R B).
The question is: can we find a regular language $L$ such that the there exists a NFA accepting $L$ which is exponentially smaller (state-wise) than the minimal UFA for $L$? Can this happen for a finite language?
I believe such (finite) $L$ exists, but my proof currently relies on the Exponential Time Hypothesis to hold, and was wondering if someone has a proof which doesn't rely on it.
Also, can someone characterize the set of languages for which such size difference exist?
EDIT: @Shaull gave a nice link to a paper dealing with infinite language. Does anyone know a similar result for a finite language?