Complexity of subclasses of the intuitionistic propositional calculus

DOI10.1007/BF01995108MaRDI QIDQ688732zbMATH OpenOpenAlexFDO

Authors G. E. Mints

Publication date 22 June 1994

Published in BIT (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01995108

zbMATH Keywords

complexity of the decision problem for subclasses of intuitionistic propositional calculusupper bounds for decision procedures

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Subsystems of classical logic (including intuitionistic logic) (03B20) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Proof complexity of substructural logics
• scientific article; zbMATH DE number 1390276
• Proof complexity of intuitionistic implicational formulas
• Complexity of intuitionistic propositional logic and its fragments
• On the complexity of propositional quantification in intuitionistic logic
• Proof theoretic complexity of low subrecursive classes
• Propositional logics complexity and the sub-formula property
• scientific article; zbMATH DE number 5289966
• The computational complexity of propositional cirquent calculus
• Complexity of deductions in a system of classical propositional calculus

Cites work

• scientific article; zbMATH DE number 15881 (Why is no real title available?)
• scientific article; zbMATH DE number 50149 (Why is no real title available?)
• scientific article; zbMATH DE number 3325541 (Why is no real title available?)
• scientific article; zbMATH DE number 3073037 (Why is no real title available?)
• Justification of the structural synthesis of programs

Cited in

(7)

• scientific article; zbMATH DE number 5289966 (Why is no real title available?)
• scientific article; zbMATH DE number 1342223 (Why is no real title available?)
• Intuitionistic Decision Procedures Since Gentzen
• scientific article; zbMATH DE number 54580 (Why is no real title available?)
• Abductive Reasoning in Intuitionistic Propositional Logic via Theorem Synthesis
• Transitive primal infon logic
• Intuitionistic formal theories with realizability in subrecursive classes

This page was built for publication: Complexity of subclasses of the intuitionistic propositional calculus

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