文章基本信息

标题：On the Mints Hierarchy in First-Order Intuitionistic Logic
本地全文：下载
作者：Aleksy Schubert ; Paweł Urzyczyn ; Konrad Zdanowski 等
期刊名称：Logical Methods in Computer Science
印刷版ISSN：1860-5974
电子版ISSN：1860-5974
出版年度：2016
卷号：12
期号：4
页码：1
DOI：10.2168/LMCS-12(4:11)2016
出版社：Technical University of Braunschweig
摘要：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.
其他关键词：Intuitionistic logic, Mints hierarchy, complexity, automata.