Propositional logics complexity and the sub-formula property

MaRDI QIDQ5013887zbMATH OpenFDO

Authors Edward Hermann Haeusler

Publication date 3 December 2021

Full work available at URL https://arxiv.org/abs/1401.8209, http://eptcs.web.cse.unsw.edu.au/paper.cgi?DCM2014.1

Mathematics Subject Classification ID

Classical propositional logic (03B05) Logics of knowledge and belief (including belief change) (03B42) Modal logic (including the logic of norms) (03B45) Many-valued logic (03B50) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Computer Science Logic
• Disjunction property and complexity of substructural logics
• scientific article; zbMATH DE number 3995647
• Complexity of intuitionistic propositional logic and its fragments
• scientific article; zbMATH DE number 757645

Cites work

• A natural deduction approach to dynamic logic
• A natural extension of natural deduction
• Classic-Like Analytic Tableaux for Finite-Valued Logics
• Finitely many-valued logics and natural deduction
• General-elimination harmony and the meaning of the logical constants
• scientific article; zbMATH DE number 3630747 (Why is no real title available?)
• scientific article; zbMATH DE number 560935 (Why is no real title available?)
• scientific article; zbMATH DE number 3275554 (Why is no real title available?)
• scientific article; zbMATH DE number 3335866 (Why is no real title available?)
• scientific article; zbMATH DE number 970633 (Why is no real title available?)
• Intuitionistic propositional logic is polynomial-space complete
• Knowledge and common knowledge in a distributed environment
• Labelled propositional modal logics: theory and practice
• On Interpolation and Automatization for Frege Systems
• Propositional dynamic logic of regular programs
• Strict canonical constructive systems

Cited in

(8)

• A unified procedure for provability and counter-model generation in minimal implicational logic
• scientific article; zbMATH DE number 5289966 (Why is no real title available?)
• From the subformula property to cut-admissibility in propositional sequent calculi
• scientific article; zbMATH DE number 4114609 (Why is no real title available?)
• Substitution and Propositional Proof Complexity
• Disjunction property and complexity of substructural logics
• Complexity of subclasses of the intuitionistic propositional calculus
• Existence of simple propositional formulas

This page was built for publication: Propositional logics complexity and the sub-formula property

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