Deciding Universality of ptNFAs is PSpace-Complete

DOI10.1007/978-3-319-73117-9_29zbMath1444.68097OpenAlexW2778312178MaRDI QIDQ5127189

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

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

Related Items (1)

On the height of towers of subsequences and prefixes

This page was built for publication: Deciding Universality of ptNFAs is PSpace-Complete