Proof complexity of propositional default logic

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

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.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 74,480

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

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
2013-10-27

Downloads
48 (#241,981)

6 months
1 (#417,474)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations