The Complexity of Reasoning for Fragments of Autoepistemic Logic

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

doi:10.4230/DagSemProc.10061.6

Document

The Complexity of Reasoning for Fragments of Autoepistemic Logic

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

Part of: Volume: Dagstuhl Seminar Proceedings, Volume 10061
Part of: Series: Dagstuhl Seminar Proceedings (DagSemProc)
License: Creative Commons Attribution 4.0 International license
Publication Date: 2010-04-26

PDF

File

PDF

DagSemProc.10061.6.pdf

Filesize: 292 kB
10 pages

Document Identifiers

DOI: 10.4230/DagSemProc.10061.6
URN: urn:nbn:de:0030-drops-25234

Subject Classification

Keywords

Autoepistemic logic
computational complexity
nonmonotonic reasoning
Post's lattice

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

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.

Cite As Get BibTex

Nadia Creignou, Arne Meier, Michael Thomas, and Heribert Vollmer. The Complexity of Reasoning for Fragments of Autoepistemic Logic. In Circuits, Logic, and Games. Dagstuhl Seminar Proceedings, Volume 10061, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010) https://doi.org/10.4230/DagSemProc.10061.6

Author Details

Nadia Creignou

Arne Meier

Michael Thomas

Heribert Vollmer

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail