Deciding regular intersection emptiness of complete problems for PSPACE and the polynomial hierarchy

DOI10.1007/978-3-319-77313-1_12zbMath1504.68102MaRDI QIDQ1647695

Andreas Krebs, Petra Wolf, Klaus-Joern Lange, Demen Güler

Publication date: 26 June 2018

Full work available at URL: https://doi.org/10.1007/978-3-319-77313-1_12

zbMATH Keywords

polynomial hierarchy; quantified Boolean formula; PSPACE; automata and logic; emptiness of regular intersection

Mathematics Subject Classification ID

68Q45: Formal languages and automata

03D05: Automata and formal grammars in connection with logical questions

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)