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

DOI10.1007/978-3-319-77313-1_12zbMath1504.68102OpenAlexW2793155354MaRDI 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 hierarchyquantified Boolean formulaPSPACEautomata and logicemptiness of regular intersection

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (5)

Lamplighter groups and automata ⋮ 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

This page was built for publication: Deciding regular intersection emptiness of complete problems for PSPACE and the polynomial hierarchy