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, Demen Güler, Petra Wolf, Klaus-Joern Lange

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.)

Related Items

Properties of graphs specified by a regular language, Properties of graphs specified by a regular language, On the decidability of finding a positive ILP-instance in a regular set of ILP-instances, From decidability to undecidability by considering regular sets of instances, Lamplighter groups and automata