The complexity of disjunction in intuitionistic logic

DOI10.1007/978-3-319-27683-0_24MaRDI QIDQ5283439zbMATH OpenOpenAlexFDO

Authors

Publication date 21 July 2017

Published in Logical Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-27683-0_24

zbMATH Keywords

complexityproof theoryintuitionistic logicdisjunction

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Subsystems of classical logic (including intuitionistic logic) (03B20)

Recommendations

• The complexity of disjunction in intuitionistic logic
• On the complexity of the disjunction property in intuitionistic and modal logics
• Complexity of intuitionistic propositional logic and its fragments
• Intuitionistic implication without disjunction
• Computations in fragments of intuitionistic propositional logic

Cites work

• A DEXPTIME-complete Dolev-Yao theory with distributive encryption
• A sequence of decidable finitely axiomatizable intermediate logics with the disjunction property
• Automatic recognition of tractability in inference relations
• Easy intruder deductions
• Hypersequent calculi for intuitionistic logic with classical atoms
• Logic of infons, the propositional case
• On the security of public key protocols
• Primal Infon Logic: Derivability in Polynomial Time
• Propositional primal logic with disjunction
• Protocol insecurity with a finite number of sessions and composed keys is NP-complete.
• The complexity of primal logic with disjunction

Cited in

(8)

• On the complexity of data disjunctions.
• The complexity of disjunction in intuitionistic logic
• scientific article; zbMATH DE number 1980925 (Why is no real title available?)
• scientific article; zbMATH DE number 6440890 (Why is no real title available?)
• Disjunction property and complexity of substructural logics
• The logic of multisets continued: The case of disjunction
• scientific article; zbMATH DE number 5163096 (Why is no real title available?)
• scientific article; zbMATH DE number 3274718 (Why is no real title available?)

Describes a project that uses

Uses Software

• DKAL

This page was built for publication: The complexity of disjunction in intuitionistic logic

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