Deciding Universality of ptNFAs is PSpace-Complete

DOI10.1007/978-3-319-73117-9_29MaRDI QIDQ5127189zbMATH OpenOpenAlexFDO

Authors Tomáš Masopust, Markus Krötzsch

Publication date 21 October 2020

Published in SOFSEM 2018: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-73117-9_29

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Formal languages and automata (68Q45)

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
• Publication:3489978

Cited in

(5)

• 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

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)