Proof Complexity of Non-classical Logics
From MaRDI portal
Publication:5894972
DOI10.1007/978-3-642-31485-8_1zbMath1250.03116WikidataQ61835458 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
03B45: Modal logic (including the logic of norms)
03B60: Other nonclassical logic
68T27: Logic in artificial intelligence
03B20: Subsystems of classical logic (including intuitionistic logic)
03F20: Complexity of proofs
Related Items
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
