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

lmcs:2623 - Logical Methods in Computer Science, April 27, 2017, Volume 12, Issue 4 - https://doi.org/10.2168/LMCS-12(4:11)2016
On the Mints Hierarchy in First-Order Intuitionistic LogicArticle

Authors: Aleksy Schubert ORCID; Paweł Urzyczyn ; Konrad Zdanowski ORCID

    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.


    Volume: Volume 12, Issue 4
    Published on: April 27, 2017
    Accepted on: December 28, 2016
    Submitted on: November 23, 2015
    Keywords: Computer Science - Logic in Computer Science

    1 Document citing this article

    Consultation statistics

    This page has been seen 1207 times.
    This article's PDF has been downloaded 372 times.