On the proof complexity of logics of bounded branching

DOI10.1016/J.APAL.2022.103181OpenAlexW4287812606WikidataQ113880314 ScholiaQ113880314MaRDI QIDQ2084964

Emil Jeřábek

Publication date: 14 October 2022

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2004.11282

zbMATH Keywords

modal logicdisjunction propertyproof complexityintermediate logicextended Frege system

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45) Complexity of proofs (03F20) Intermediate logics (03B55)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Proof complexity of intuitionistic implicational formulas
• A lower bound for intuitionistic logic
• On lengths of proofs in non-classical logics
• Substitution Frege and extended Frege proof systems in non-classical logics
• The complexity of the disjunction and existential properties in intuitionistic logic
• Admissibility of logical inference rules
• On reducibility and symmetry of disjoint NP pairs.
• Dual weak pigeonhole principle, Boolean complexity, and derandomization
• Rules with parameters in modal logic. II.
• Rules with parameters in modal logic. I.
• Frege systems for extensible modal logics
• Independent Bases of Admissible Rules
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• The relative efficiency of propositional proof systems
• Proof Complexity
• INCOMPLETENESS IN THE FINITE DOMAIN
• A sequence of decidable finitely axiomatizable intermediate logics with the disjunction property
• On the complexity of the disjunction property in intuitionistic and modal logics
• Lower bounds for modal logics
• On the computational content of intuitionistic propositional proofs

This page was built for publication: On the proof complexity of logics of bounded branching