Show simple item record

dc.contributor.authorDimopoulos, Yannisen
dc.contributor.authorTorres, A.en
dc.creatorDimopoulos, Yannisen
dc.creatorTorres, A.en
dc.description.abstractIn this paper we present a graph representation of logic programs and default theories. We show that many of the semantics proposed for logic programs with negation can be expressed in terms of notions emerging from graph theory, establishing in this way a link between the fields. Namely the stable models, the partial stable models, and the well-founded semantics correspond respectively to the kernels, semikernels and the initial acyclic part of an associated graph. This link allows us to consider both theoretical (existence, uniqueness) and computational problems (tractability, algorithms, approximations) from a more abstract and rather combinatorial point of view. It also provides a clear and intuitive understanding about how conflicts between rules are resolved within the different semantics. Furthermore, we extend the basic framework developed for logic programs to the case of Default Logic by introducing the notions of partial, deterministic and well-founded extensions for default theories. These semantics capture different ways of reasoning with a default theory.en
dc.sourceTheoretical Computer Scienceen
dc.subjectProblem solvingen
dc.subjectMathematical modelsen
dc.subjectGraph theoryen
dc.subjectComputation theoryen
dc.subjectLogic programmingen
dc.subjectComputational linguisticsen
dc.subjectDefault logicen
dc.subjectDefault theoryen
dc.subjectGraph theoretical structuresen
dc.titleGraph theoretical structures in logic programs and default theoriesen
dc.description.endingpage244 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied SciencesΤμήμα Πληροφορικής / Department of Computer Science
dc.description.notes<p>Cited By :110</p>en
dc.contributor.orcidDimopoulos, Yannis [0000-0001-9583-9754]

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record