Restricted positive quantification is not elementary

DOI10.4230/LIPICS.TYPES.2014.251MaRDI QIDQ5277980zbMATH OpenOpenAlexFDO

Authors Aleksy Schubert, Paweł Urzyczyn, Daria Walukiewicz-Chrząszcz

Publication date 12 July 2017

Full work available at URL https://www.mimuw.edu.pl/~alx/positivenonelem.pdf

zbMATH Keywords

automata theorycomplexityconstructive logic

Mathematics Subject Classification ID

Subsystems of classical logic (including intuitionistic logic) (03B20) Mechanization of proofs and logical operations (03B35) Automata and formal grammars in connection with logical questions (03D05)

Recommendations

• How hard is positive quantification?
• Eigenvariables, bracketing and the decidability of positive minimal predicate logic
• Algorithmic properties of first-order superintuitionistic logics of finite Kripke frames in restricted languages
• On the complexity of propositional quantification in intuitionistic logic
• Complexity of some problems in positive and related calculi

Cited in

(3)

• First-order Answer Set Programming as Constructive Proof Search
• How hard is positive quantification?
• On the Mints hierarchy in first-order intuitionistic logic

This page was built for publication: Restricted positive quantification is not elementary

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5277980)