文章基本信息

标题：Restricted Positive Quantification Is Not Elementary
本地全文：下载
作者：Aleksy Schubert ; Pawel Urzyczyn ; Daria Walukiewicz-Chrzaszcz 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2015
卷号：39
页码：251-273
DOI：10.4230/LIPIcs.TYPES.2014.251
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We show that a restricted variant of constructive predicate logic with positive (covariant) quantification is of super-elementary complexity. The restriction is to limit the number of eigenvariables used in quantifier introductions rules to a reasonably usable level. This construction suggests that the known non-elementary decision algorithms for positive logic may actually be best possible.
关键词：constructive logic; complexity; automata theory