7
$\begingroup$

I'm doing some research regarding NFAs and inclusion problems with them. I know that in general, the inclusion problems, and converting to an unambiguous NFA, are both PSPACE-complete.

I'm wondering, are there any sub-classes of NFA for which these can be decided efficiently? In particular, the NFAs I'm looking at accept finite language where all words have the same Parikh vector.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Parikh vector, wikipedia $\endgroup$ – vzn Jun 13 '13 at 16:34
  • $\begingroup$ any more motivation/application? $\endgroup$ – vzn Jun 13 '13 at 17:23
  • $\begingroup$ [recommend migrate to tcs.se] $\endgroup$ – vzn Jun 16 '13 at 22:58
  • $\begingroup$ That would be good. $\endgroup$ – jmite Jun 17 '13 at 1:41
2
+50
$\begingroup$

here are three refs that may be helpful.

We show that language inclusion for languages of infinite words defined by non- deterministic automata can be tested in polynomial time if the automata are unambiguous and have simple acceptance conditions, namely safety or reachability conditions. An automaton with safety condition accepts an infinite word if there is a run that never visits a forbidden state, and an automaton with reachability condition accepts an infinite word if there is a run that visits an accepting state at least once.

this 2nd ref is more indirect & would rely on a mapping between NFAs and tree automata.

We show the significantly improved efficiency of this framework through a series of experiments with verifying various programs over dynamic linked tree-shaped data structures

the above ref also cites the following:

We show that on the difficult instances of this probabilistic model, the antichain algorithm outperforms the standard one by several orders of magnitude. We also show how variations of the antichain method can be used for solving the language-inclusion problem for nondeterministic finite automata...

Improve this answer
$\endgroup$
1
  • $\begingroup$ The antichains look really promising. I'm guessing their performance boost comes because they're polynomial for most cases. Do you know if anyone's look at which classes of NFAs give polynomial runs for the antichain algorithms? $\endgroup$ – jmite Jun 13 '13 at 17:24
2
$\begingroup$

As a negative example, It is shown in this paper by Kozen that given DFAs $A_1,...,A_n$, deciding whether $\bigcup_{i=1}^n L(A_i)=\Sigma^*$ is PSPACE-complete (a direct result of Lemma 3.2.3 in the paper).

Thus, deciding containment even for finitely-ambiguous NFAs is PSPACE-complete.

While this doesn't mean that your case cannot be decided efficiently, it does give some evidence that it might not be.

Improve this answer
$\endgroup$
1
  • $\begingroup$ While both true and good advice, not quite what I'm looking for. I guess, if it's PSPACE-complete even for finitely-ambiguous NFAs, I want to know, what subclasses of FA-NFAs is it polynomial for? $\endgroup$ – jmite Jun 13 '13 at 17:09

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.