Cuvillier Verlag

Publications, Dissertations, Habilitations & Brochures.
International Specialist Publishing House for Science and Economy

Cuvillier Verlag

De En Es
On the Complexity of Fragments of Nonmonotonic Logics

Hard Copy
EUR 24.40 EUR 23.18

E-book
EUR 17.08

On the Complexity of Fragments of Nonmonotonic Logics (English shop)

Michael Thomas (Author)

Preview

Table of Contents, Datei (28 KB)
Extract, Datei (80 KB)

ISBN-13 (Printausgabe) 3869555718
ISBN-13 (Hard Copy) 9783869555713
ISBN-13 (eBook) 9783736935716
Language English
Page Number 146
Edition 1 Aufl.
Volume 0
Publication Place Göttingen
Place of Dissertation Universität Hannover
Publication Date 2010-11-29
General Categorization Dissertation
Departments Informatics
Keywords nonmonotonic logic, computational complexity, Post's lattice
Description

Nonmonotonic reasoning is one of the most important tasks in the area of knowledge representation and reasoning. Several logics have been developed to formalize nonmonotonic reasoning. In this thesis we consider three well-known logics that facilitate nonmonotonic reasoning by different means: default logic, autoepistemic logic and circumscription. We study the computational complexity of consistency, reasoning and counting problems for fragments of these logics obtained by restricting the available Boolean connectives, as well as the possibility to translate between these fragments. For this we generalize the logics to allow for arbitrary connectives rather than the Boolean standard base and study the complexity of the problems and possibility of translations for all finite sets of allowed Boolean connectives.
Our results show that in all cases the complexity of the problems does not depend on the particular set B of available connectives but on the set of functions expressible by projections and arbitrary compositions from B. We obtain polytomous complexity classifications (that is, into a finite number of complexity degrees) for all decision problems studied herein ranging from completeness for classes in the second level of the polynomial hierarchy down to membership in AC0. Furthermore, the counting problems are with one interesting exception shown to be trichotomous with complexity degrees spanning the first three levels of the counting hierarchy. To the best of our knowledge, the counting complexity of default logic is addressed here for the first time.
Finally, we consider translations between fragments of these logics that leave the set of propositional consequences of the input invariant. We show which fragments of default logic, autoepistemic logic and circumscription can, under the chosen notion of translations, be embedded into fragments of the other two logics. We complete this picture by showing that in almost all cases in which no translation is given, no translation preserving the set of propositional consequences may exist unless the polynomial hierarchy collapses.