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


Share

Consultation statistics

This page has been seen 175 times.
This article's PDF has been downloaded 91 times.