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.
Classes of NFAs which allow efficient subset testing or unambiguity conversions
complexity theory;formal languages;automata;finite automata;nondeterminism
here are three refs that may be helpful.Efficient Inclusion Testing for Simple Classes ofUnambiguous $\omega$-AutomataDimitri Isaaka, Christof LodingaWe 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-basedUniversality and Inclusion Testingover Nondeterministic FiniteTree AutomataAhmed Bouajjani, Peter Habermehl,Lukas Holk, Tayssir Touili, andTomas VojnarWe show the signicantly improved efciency of this framework through a series of experiments  with verifying various programs over dynamic linked tree-shaped data structuresthe above ref also cites the following:Antichains: A New Algorithm for CheckingUniversality of Finite Automata, M. De Wulf, L. Doyen, T. A. Henzinger, and J.F. RaskinWe 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...