[Solved]: Classes of NFAs which allow efficient subset testing or unambiguity conversions

Problem Detail: 

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.

Asked By : jmite

Answered By : vzn

here are three refs that may be helpful.

• Efficient Inclusion Testing for Simple Classes of Unambiguous $\omega$-Automata Dimitri Isaaka, Christof Lodinga

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.

• Antichain-based Universality and Inclusion Testing over Nondeterministic Finite Tree Automata Ahmed Bouajjani, Peter Habermehl, Luka´ˇs Hol´ık, Tayssir Touili, and Toma´ˇs Vojnar

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:

• Antichains: A New Algorithm for Checking Universality of Finite Automata, M. De Wulf, L. Doyen, T. A. Henzinger, and J.F. Raskin

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11841

3.2K people like this

 Download Related Notes/Documents