16
$\begingroup$

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:

  1. NFA minimization is PSPACE-Complete.
  2. NFA minimization over finite languages is DP-Hard.
  3. UFA minimization is NP-Complete.
  4. 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?

$\endgroup$
14
$\begingroup$

I think the IJFCS'05 paper by Leung: Descriptional complexity of nfa of different ambiguity provides an example with a family of NFA accepting finite languages that involve an exponential blowup for "disambiguation" (in the proof of Theorem 5).

What is more, those automata have a special structure (DFA with multiple initial states).

$\endgroup$
16
$\begingroup$

There is even a stronger result than your request:

There are exponentially-ambiguous NFAs for which the minimal polynomially-ambiguous NFAs are exponentially larger, and in particular the minimal UFAs.

Check this paper by Hing Leung.

$\endgroup$
  • 1
    $\begingroup$ Thanks @Shaull. Do you know if a similar result exists for finite languages? $\endgroup$ – R B Jan 12 '14 at 15:41
  • 1
    $\begingroup$ I am not aware of any similar results for finite languages, sorry. $\endgroup$ – Shaull Jan 12 '14 at 15:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.