Details
| Originalsprache | Englisch |
|---|---|
| Aufsatznummer | a17 |
| Fachzeitschrift | ACM Transactions on Computational Logic |
| Jahrgang | 13 |
| Ausgabenummer | 2 |
| Publikationsstatus | Veröffentlicht - Apr. 2012 |
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 in 1985 for modeling an ideally rational agent's behavior and reasoning about his own beliefs. In this article 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 checking that a given set of formulae characterizes a stable expansion and that of counting the number of stable expansions of a given knowledge base. We improve the best known Δ 2 p-upper bound on the former problem to completeness for the second level of the Boolean hierarchy. To the best of our knowledge, this is the first paper analyzing counting problem for autoepistemic logic.
ASJC Scopus Sachgebiete
- Mathematik (insg.)
- Theoretische Informatik
- Informatik (insg.)
- Allgemeine Computerwissenschaft
- Mathematik (insg.)
- Logik
- Mathematik (insg.)
- Computational Mathematics
Zitieren
- Standard
- Harvard
- Apa
- Vancouver
- BibTex
- RIS
in: ACM Transactions on Computational Logic, Jahrgang 13, Nr. 2, a17, 04.2012.
Publikation: Beitrag in Fachzeitschrift › Artikel › Forschung › Peer-Review
}
TY - JOUR
T1 - The complexity of reasoning for fragments of autoepistemic logic
AU - Creignou, Nadia
AU - Meier, Arne
AU - Vollmer, Heribert
AU - Thomas, Michael
PY - 2012/4
Y1 - 2012/4
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 in 1985 for modeling an ideally rational agent's behavior and reasoning about his own beliefs. In this article 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 checking that a given set of formulae characterizes a stable expansion and that of counting the number of stable expansions of a given knowledge base. We improve the best known Δ 2 p-upper bound on the former problem to completeness for the second level of the Boolean hierarchy. To the best of our knowledge, this is the first paper analyzing 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 in 1985 for modeling an ideally rational agent's behavior and reasoning about his own beliefs. In this article 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 checking that a given set of formulae characterizes a stable expansion and that of counting the number of stable expansions of a given knowledge base. We improve the best known Δ 2 p-upper bound on the former problem to completeness for the second level of the Boolean hierarchy. To the best of our knowledge, this is the first paper analyzing counting problem for autoepistemic logic.
KW - Autoepistemic logic
KW - Complexity
KW - Nonmonotonic reasoning
KW - Post's lattice
UR - http://www.scopus.com/inward/record.url?scp=84860305809&partnerID=8YFLogxK
U2 - 10.1145/2159531.2159539
DO - 10.1145/2159531.2159539
M3 - Article
VL - 13
JO - ACM Transactions on Computational Logic
JF - ACM Transactions on Computational Logic
SN - 1529-3785
IS - 2
M1 - a17
ER -