Proof complexity of propositional default logic

Archive for Mathematical Logic 50 (7-8):727-742 (2011)

Abstract
Default logic is one of the most popular and successful formalisms for non-monotonic reasoning. In 2002, Bonatti and Olivetti introduced several sequent calculi for credulous and skeptical reasoning in propositional default logic. In this paper we examine these calculi from a proof-complexity perspective. In particular, we show that the calculus for credulous reasoning obeys almost the same bounds on the proof size as Gentzen’s system LK. Hence proving lower bounds for credulous reasoning will be as hard as proving lower bounds for LK. On the other hand, we show an exponential lower bound to the proof size in Bonatti and Olivetti’s enhanced calculus for skeptical default reasoning.
Keywords Default logic  Sequent calculus  Proof complexity
Categories (categorize this paper)
DOI 10.1007/s00153-011-0245-8
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 40,131
Through your library

References found in this work BETA

Frege Systems for Extensible Modal Logics.Emil Jeřábek - 2006 - Annals of Pure and Applied Logic 142 (1):366-379.
On Lengths of Proofs in Non-Classical Logics.Pavel Hrubeš - 2009 - Annals of Pure and Applied Logic 157 (2-3):194-205.

View all 6 references / Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

The Complexity of Propositional Proofs.Nathan Segerlind - 2007 - Bulletin of Symbolic Logic 13 (4):417-481.
Defaults as Restrictions on Classical Hilbert-Style Proofs.Gianni Amati, Luigia Carlucci Aiello & Fiora Pirri - 1994 - Journal of Logic, Language and Information 3 (4):303-326.
A Note on Propositional Proof Complexity of Some Ramsey-Type Statements.Jan Krajíček - 2011 - Archive for Mathematical Logic 50 (1-2):245-255.
An Interpretation of Default Logic in Minimal Temporal Epistemic Logic.Joeri Engelfriet & Jan Treur - 1998 - Journal of Logic, Language and Information 7 (3):369-388.
Russell's Completeness Proof.Peter Milne - 2008 - History and Philosophy of Logic 29 (1):31-62.

Analytics

Added to PP index
2013-10-27

Total views
38 ( #206,595 of 2,237,264 )

Recent downloads (6 months)
16 ( #48,103 of 2,237,264 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature