Loading [MathJax]/extensions/tex2jax.js

The complexity of reasoning for fragments of autoepistemic logic

Research output: Contribution to journal › Article › Research › peer review

Authors

Research Organisations

External Research Organisations

  • Universite d'Aix-Marseille
  • Technisch Wissenschaftlicher Transfer GmbH (TWT)

Details

Original languageEnglish
Article numbera17
JournalACM Transactions on Computational Logic
Volume13
Issue number2
Publication statusPublished - 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.

Keywords

    Autoepistemic logic, Complexity, Nonmonotonic reasoning, Post's lattice

ASJC Scopus subject areas

Cite this

The complexity of reasoning for fragments of autoepistemic logic. / Creignou, Nadia; Meier, Arne; Vollmer, Heribert et al.
In: ACM Transactions on Computational Logic, Vol. 13, No. 2, a17, 04.2012.

Research output: Contribution to journal › Article › Research › peer review

Download
@article{df4fa2b5e2d940b8acbb5f25b12d2a62,
title = "The complexity of reasoning for fragments of autoepistemic logic",
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.",
keywords = "Autoepistemic logic, Complexity, Nonmonotonic reasoning, Post's lattice",
author = "Nadia Creignou and Arne Meier and Heribert Vollmer and Michael Thomas",
year = "2012",
month = apr,
doi = "10.1145/2159531.2159539",
language = "English",
volume = "13",
journal = "ACM Transactions on Computational Logic",
issn = "1529-3785",
publisher = "Association for Computing Machinery (ACM)",
number = "2",

}

Download

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 -

By the same author(s)