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 |
|---|---|
| ISSN (Print) | 1862-4405 |
Abstract
Autoepistemic logic extends propositional logic by the modal operator L. A formula ϕ that is preceded by an L is said to be “believed”. The logic was introduced by Moore 1985 for modeling an ideally rational agent’s behavior and reasoning about his own beliefs. In this paper we analyze all Boolean fragments of autoepistemic logic with respect to the computational complexity of the three most common decision problems expansion existence, brave reasoning and cautious reasoning. As a second contribution we classify the computational complexity of counting the number of stable expansions of a given knowledge base. To the best of our knowledge this is the first paper analyzing the counting problem for autoepistemic logic.
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).
Publikation: Beitrag in Buch/Bericht/Sammelwerk/Konferenzband › Beitrag in sonstigem Bericht › Forschung › Peer-Review
}
TY - CHAP
T1 - The Complexity of Reasoning for Fragments of Autoepistemic Logic∗
AU - Creignou, Nadia
AU - Meier, Arne
AU - Thomas, Michael
AU - Vollmer, Heribert
N1 - Funding information: *Supported in part by DFG grant VO 630/6-1.
PY - 2010
Y1 - 2010
N2 - Autoepistemic logic extends propositional logic by the modal operator L. A formula ϕ that is preceded by an L is said to be “believed”. The logic was introduced by Moore 1985 for modeling an ideally rational agent’s behavior and reasoning about his own beliefs. In this paper we analyze all Boolean fragments of autoepistemic logic with respect to the computational complexity of the three most common decision problems expansion existence, brave reasoning and cautious reasoning. As a second contribution we classify the computational complexity of counting the number of stable expansions of a given knowledge base. To the best of our knowledge this is the first paper analyzing the counting problem for autoepistemic logic.
AB - Autoepistemic logic extends propositional logic by the modal operator L. A formula ϕ that is preceded by an L is said to be “believed”. The logic was introduced by Moore 1985 for modeling an ideally rational agent’s behavior and reasoning about his own beliefs. In this paper we analyze all Boolean fragments of autoepistemic logic with respect to the computational complexity of the three most common decision problems expansion existence, brave reasoning and cautious reasoning. As a second contribution we classify the computational complexity of counting the number of stable expansions of a given knowledge base. To the best of our knowledge this is the first paper analyzing the counting problem for autoepistemic logic.
UR - http://www.scopus.com/inward/record.url?scp=85175018031&partnerID=8YFLogxK
M3 - Contribution to other report
AN - SCOPUS:85175018031
VL - 10061
T3 - Dagstuhl Seminar Proceedings
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 -