| Autor: |
Aleksy Schubert, Paweł Urzyczyn, Konrad Zdanowski |
| Jazyk: |
angličtina |
| Rok vydání: |
2017 |
| Předmět: |
|
| Zdroj: |
Logical Methods in Computer Science, Vol Volume 12, Issue 4 (2017) |
| Druh dokumentu: |
article |
| ISSN: |
1860-5974 |
| DOI: |
10.2168/LMCS-12(4:11)2016 |
| Popis: |
We stratify intuitionistic first-order logic over $(\forall,\to)$ into fragments determined by the alternation of positive and negative occurrences of quantifiers (Mints hierarchy). We study the decidability and complexity of these fragments. We prove that even the $\Delta_2$ level is undecidable and that $\Sigma_1$ is Expspace-complete. We also prove that the arity-bounded fragment of $\Sigma_1$ is complete for co-Nexptime. |
| Databáze: |
Directory of Open Access Journals |
| Externí odkaz: |
|
