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.

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

2 Answers 2

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...

$\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$ Jun 13, 2013 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.

$\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$ Jun 13, 2013 at 17:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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