Schubert, Aleksy and Urzyczyn, Paweł and Zdanowski, Konrad - On the Mints Hierarchy in First-Order Intuitionistic Logic

lmcs:2623 - Logical Methods in Computer Science, April 27, 2017, Volume 12, Issue 4
On the Mints Hierarchy in First-Order Intuitionistic Logic

Authors: Schubert, Aleksy and Urzyczyn, Paweł and Zdanowski, Konrad

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.

Source : oai:arXiv.org:1610.02675
DOI : 10.2168/LMCS-12(4:11)2016
Volume: Volume 12, Issue 4
Published on: April 27, 2017
Submitted on: November 23, 2015
Keywords: Computer Science - Logic in Computer Science