License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-25234
URL: http://drops.dagstuhl.de/opus/volltexte/2010/2523/

Creignou, Nadia ; Meier, Arne ; Thomas, Michael ; Vollmer, Heribert

The Complexity of Reasoning for Fragments of Autoepistemic Logic

pdf-format:
Dokument 1.pdf (293 KB)


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.

BibTeX - Entry

@InProceedings{creignou_et_al:DSP:2010:2523,
  author =	{Nadia Creignou and Arne Meier and Michael Thomas and Heribert Vollmer},
  title =	{The Complexity of Reasoning for Fragments of Autoepistemic Logic},
  booktitle =	{Circuits, Logic, and Games},
  year =	{2010},
  editor =	{Benjamin Rossman and Thomas Schwentick and Denis Th{\'e}rien and Heribert Vollmer},
  number =	{10061},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2523},
  annote =	{Keywords: Autoepistemic logic, computational complexity, nonmonotonic reasoning, Post's lattice}
}

Keywords: Autoepistemic logic, computational complexity, nonmonotonic reasoning, Post's lattice
Seminar: 10061 - Circuits, Logic, and Games
Issue date: 2010
Date of publication: 26.04.2010


DROPS-Home | Fulltext Search | Imprint Published by LZI