Deciding Universality of ptNFAs is PSpace-Complete
From MaRDI portal
Recommendations
- On the complexity of universality for partially ordered NFAs
- Complexity of universality and related problems for partially ordered NFAs
- On polynomial-time Turing and many-one completeness in PSPACE
- On the existence of universal finite or pushdown automata
- Universal relations and {\#}P-completeness
- Simplicity via provability for universal prefix-free Turing machines
- Simplicity via provability for universal prefix-free Turing machines
- Universality and almost decidability
- scientific article; zbMATH DE number 4162853
Cited in
(6)- Complexity of universality and related problems for partially ordered NFAs
- On the height of towers of subsequences and prefixes
- On the complexity of universality for partially ordered NFAs
- Partially ordered automata and piecewise testability
- Subset mapping problems in solvable automata
- Pattern matching under \(\mathcal{R}\)-congruence
This page was built for publication: Deciding Universality of ptNFAs is PSpace-Complete
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5127189)