Proof Complexity of Non-classical Logics
From MaRDI portal
Publication:5894972
DOI10.1007/978-3-642-31485-8_1zbMath1250.03116OpenAlexW1510102921WikidataQ61835458 ScholiaQ61835458MaRDI QIDQ5894972
Publication date: 1 November 2012
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: http://eprints.whiterose.ac.uk/74776/10/beyersdorff.pdf
Modal logic (including the logic of norms) (03B45) Other nonclassical logic (03B60) Logic in artificial intelligence (68T27) Subsystems of classical logic (including intuitionistic logic) (03B20) Complexity of proofs (03F20)
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Proof complexity of propositional default logic
- Functional interpretations of feasibly constructive arithmetic
- Exponential lower bounds for the pigeonhole principle
- Complexity of admissible rules
- 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 intractability of resolution
- Tautologies with a unique Craig interpolant, uniform vs. nonuniform complexity
- The monotone circuit complexity of Boolean functions
- A logic for default reasoning
- Nonmonotonic reasoning, preferential models and cumulative logics
- Lower bounds for the polynomial calculus
- Tools and techniques in modal logic
- The complexity of the disjunction and existential properties in intuitionistic logic
- Admissibility of logical inference rules
- The complexity of the pigeonhole principle
- Tableau-based characterization and theorem proving for default logic
- Some consequences of cryptographical conjectures for \(S_2^1\) and EF
- Many-dimensional modal logics: theory and applications
- Mathematical modal logic: A view of its evolution
- What is a logic translation?
- Carnap, Goguen, and the hyperontologies: logical pluralism and heterogeneous structuring in ontology design
- Frege systems for extensible modal logics
- On the admissible rules of intuitionistic propositional logic
- Tautologies from Pseudo-Random Generators
- Resolution in Modal, Description and Hybrid Logic
- Bases of Admissible Rules of Lukasiewicz Logic
- Three uses of the Herbrand-Gentzen theorem in relating model theory and proof theory
- Interpolation for extended modal languages
- Propositional proof systems, the consistency of first order theories and the complexity of computations
- Proof-complexity results for nonmonotonic reasoning
- Admissible Rules of Lukasiewicz Logic
- On the correspondence between arithmetic theories and propositional proof systems – a survey
- Complexity Results for Nonmonotonic Logics
- One hundred and two problems in mathematical logic
- The Computational Complexity of Provability in Systems of Modal Propositional Logic
- The relative efficiency of propositional proof systems
- Unification in intuitionistic logic
- A survey of complexity results for non-monotonic logics
- Lower bounds to the size of constant-depth propositional proofs
- Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
- Lower bounds for cutting planes proofs with small coefficients
- Lower bounds for resolution and cutting plane proofs and monotone computations
- Short proofs are narrow—resolution made simple
- Resolution-based methods for modal logics
- On Interpolation and Automatization for Frege Systems
- Pseudorandom Generators in Propositional Proof Complexity
- An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
- A proof theoretical approach to default reasoning I: tableaux for default logic
- Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
- On the complexity of the disjunction property in intuitionistic and modal logics
- Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds
- Logical Foundations of Proof Complexity
- Lower bounds for modal logics
- The Complexity of Propositional Proofs
- A Machine-Oriented Logic Based on the Resolution Principle
- A Computing Procedure for Quantification Theory
- Admissible Rules of Modal Logics
- Sequent calculi for propositional nonmonotonic logics
- A problem concerning the notion of definability
- Proof Complexity of Non-classical Logics
- On the computational content of intuitionistic propositional proofs
This page was built for publication: Proof Complexity of Non-classical Logics
