Reasoning under minimal upper bounds in propositional logicReport as inadecuate

Reasoning under minimal upper bounds in propositional logic - Download this document for free, or read online. Document in PDF available to download.

Reference: Thomas Eiter and Georg Gottlob, (2006). Reasoning under minimal upper bounds in propositional logic. Theoretical Computer Science, 369 (1-3), 82–115.Citable link to this page:


Reasoning under minimal upper bounds in propositional logic

Abstract: Reasoning from the minimal models of a theory, as fostered by circumscription, is in the area of Artificial Intelligence an important method to formalize common sense reasoning. However, as it appears, minimal models may not always be suitable to capture the intuitive semantics of a knowledge base, aiming intuitively at an exclusive interpretation of disjunctions of atoms, i.e., if possible then assign at most one of the disjuncts the value true in a model. In this paper, we consider an approach which is more lenient and also admits non-minimal models, such that inclusive interpretation of disjunction also may be possible in cases where minimal model reasoning adopts an exclusive interpretation. Nonetheless, in the spirit of minimization, the approach aims at including only positive information that is necessary. This is achieved by closing the set of admissible models of a theory under minimal upper bounds in the set of models of the theory, which we refer to as curbing. We demonstrate this method on some examples, and investigate its semantical and computational properties. We establish that curbing is an expressive reasoning method, since the main reasoning tasks are shown to be PSPACE-complete. On the other hand, we also present cases of lower complexity, and in particular cases in which the complexity is located, just as for ordinary minimal model reasoning, at the second level of the Polynomial Hierarchy, or even below.

Publication status:PublishedPeer Review status:Peer reviewedVersion:Publisher's version Funder: European Union Network of Excellence   Funder: Austrian Science Fund FWF   Notes:Copyright 2006 Elsevier B.V. All rights reserved. Re-use of this article is permitted in accordance with the Terms and Conditions set out at ; Some results in this paper appeared in preliminary form in the Proceedings of LPAR 2000 [18] and the Proceedings of IJCAI-93

Bibliographic Details

Publisher: Elsevier

Publisher Website:

Host: Theoretical Computer Sciencesee more from them

Publication Website:

Issue Date: 2006-12

Copyright Date: 2006



Issn: 0304-3975

Urn: uuid:f8b0be29-7c50-45c9-b456-603e11b6f36e Item Description

Type: Article: post-print;

Language: en

Version: Publisher's versionKeywords: artificial intelligence circumscription computational complexity curbing knowledge representation minimal models non-monotonic reasoning propositional logicSubjects: Modal logic Computer science (mathematics) Tiny URL: ora:10768


Author: Thomas Eiter - institutionVienna University of Technology - - - Georg Gottlob - institutionUniversity of Oxford facultyMathematic



Related documents