Name
Title | ||
|---|---|---|
Deciding Regular Intersection Emptiness of Complete Problems for PSPACE and the Polynomial Hierarchy. |
Abstract | ||
|---|---|---|
For a regular set R of quantified Boolean formulae we decide whether R contains a true formula. We conclude that there is a P SPACE-complete problem for which emptiness of intersection with a regular set is decidable. Furthermore, by restricting depth and order of quantification we obtain complete problems for each level of the polynomial hierarchy with this decidability as well. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1007/978-3-319-77313-1_12 | Lecture Notes in Computer Science |
Keywords | Field | DocType |
Automata and logic,Emptiness of regular intersection,Quantified Boolean formula,PSPACE,Polynomial hierarchy | Polynomial hierarchy,Discrete mathematics,Combinatorics,Computer science,Decidability,PSPACE,Emptiness | Conference |
Volume | ISSN | Citations |
10792 | 0302-9743 | 0 |
PageRank | References | Authors |
0.34 | 4 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Demen Güler | 1 | 0 | 0.34 |
| Andreas Krebs | 2 | 3 | 4.15 |
| Klaus-Jörn Lange | 3 | 274 | 30.58 |
| petra wolf | 4 | 6 | 6.14 |