Details
| Originalsprache | Englisch |
|---|---|
| Titel des Sammelwerks | Dagstuhl Seminar: Circuits, Logic, and Games 2010 |
| Band | 10061 |
| Publikationsstatus | Veröffentlicht - 2010 |
| Veranstaltung | Dagstuhl Seminar: Circuits, Logic, and Games 2010 - Wadern, Deutschland Dauer: 7 Feb. 2010 → 12 Feb. 2010 |
Publikationsreihe
| Name | Dagstuhl Seminar Proceedings (DSP) |
|---|---|
| Herausgeber (Verlag) | Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany |
| ISSN (Print) | 1862-4405 |
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.
ASJC Scopus Sachgebiete
- Informatik (insg.)
- Software
- Informatik (insg.)
- Hardware und Architektur
- Ingenieurwesen (insg.)
- Steuerungs- und Systemtechnik
Zitieren
- Standard
- Harvard
- Apa
- Vancouver
- BibTex
- RIS
Dagstuhl Seminar: Circuits, Logic, and Games 2010. Band 10061 2010. (Dagstuhl Seminar Proceedings (DSP)).
Publikation: Beitrag in Buch/Bericht/Sammelwerk/Konferenzband › Beitrag in sonstigem Bericht › Forschung
}
TY - CHAP
T1 - Proof Complexity of Propositional Default Logic
AU - Beyersdorff, Olaf
AU - Meier, Arne
AU - Müller, Sebastian
AU - Thomas, Michael
AU - Vollmer, Heribert
N1 - Funding information: Research supported in part by DFG grants KO 1053/5-2 and VO 630/6-1, by a grant from the John Templeton Foundation, and by the Marie Curie FP7 Initial Training Network MALOA (no. 238381).
PY - 2010
Y1 - 2010
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85175047261&partnerID=8YFLogxK
M3 - Contribution to other report
AN - SCOPUS:85175047261
VL - 10061
T3 - Dagstuhl Seminar Proceedings (DSP)
BT - Dagstuhl Seminar: Circuits, Logic, and Games 2010
T2 - Dagstuhl Seminar: Circuits, Logic, and Games 2010
Y2 - 7 February 2010 through 12 February 2010
ER -