Pascal Hitzler, Anthony Karel Seda · 2010
This chapter discusses stable model semantics by the so-called fixpoint completion of programs. It enables the readers to draw almost effortlessly a number of corollaries on the stable model semantics, and provides some additional observations on stratification and the perfect model semantics. The fixpoint completion is a program transformation which is based on the notion of unfolding, meaning the replacement of a body atom by the body of a clause which also has head. In essence, the fixpoint completion of a given program is obtained by performing (recursively) a complete unfolding through all positive body atoms and disregarding all clauses which after this process still contain positive body atoms. The chapter describes an iterative method for obtaining the perfect model for locally stratified programs. Since locally stratified programs are a generalization of locally hierarchical programs, it is clear that each locally hierarchical program has a unique perfect model.
Cited by 4Open access
The MIT Press eBooks · 1997
This chapter contains sections titled: 18.1 Basic concepts of logic programming, 18.2 Stable models of logic programs, 18.3 An alternative characterization, 18.4 Logic programs with classical negation, Problems
Cited by 37
Yann Loyer, Umberto Straccia · arXiv (Cornell University) · 2004
Stable model semantics has become a very popular approach for the management of negation in logic programming. This approach relies mainly on the closed world assumption to complete the available knowledge and its formulation has its basis in the so-called Gelfond-Lifschitz transformation. The primary goal of this work is to present an alternative and epistemic-based characterization of stable model semantics, to the Gelfond-Lifschitz transformation. In particular, we show that stable model semantics can be defined entirely as an extension of the Kripke-Kleene semantics. Indeed, we show that the closed world assumption can be seen as an additional source of `falsehood' to be added cumulatively to the Kripke-Kleene semantics. Our approach is purely algebraic and can abstract from the particular formalism of choice as it is based on monotone operators (under the knowledge order) over bilattices only.
Cited by 0Open access
Luı́s Moniz Pereira · 2003
Cited by 0
Mário António Rodrigues Grande Abrantes, Luı́s Moniz Pereira · arXiv (Cornell University) · 2014
The stable model (SM) semantics lacks the properties of existence, relevance and cumulativity. If we prospectively consider the class of conservative extensions of SM semantics (i.e., semantics that for each normal logic program P retrieve a superset of the set of stable models of P), one may wander how do the semantics of this class behave in what concerns the aforementioned properties. That is the type of issue dealt with in this paper. We define a large class of conservative extensions of the SM semantics, dubbed affix stable model semantics, ASM, and study the above referred properties into two non-disjoint subfamilies of the class ASM, here dubbed ASMh and ASMm. From this study a number of results stem which facilitate the assessment of semantics in the class ASMh U ASMm with respect to the properties of existence, relevance and cumulativity, whilst unveiling relations among these properties. As a result of the approach taken in our work, light is shed on the characterization of the SM semantics, as we show that the properties of (lack of) existence and (lack of) cautious monotony are equivalent, which opposes statements on this issue that may be found in the literature; we also characterize the relevance failure of SM semantics in a more clear way than usually stated in the literature.
Cited by 0Open access
Piero A. Bonatti · Journal of Automated Reasoning · 2001
Cited by 28
Patrik Simons · ArXiv.org · 2000
An algorithm for computing the stable model semantics of logic programs is developed. It is shown that one can extend the semantics and the algorithm to handle new and more expressive types of rules. Emphasis is placed on the use of efficient implementation techniques. In particular, an implementation of lookahead that safely avoids testing every literal for failure and that makes the use of lookahead feasible is presented. In addition, a good heuristic is derived from the principle that the search space should be minimized. Due to the lack of competitive algorithms and implementations for the computation of stable models, the system is compared with three satisfiability solvers. This shows that the heuristic can be improved by breaking ties, but leaves open the question of how to break them. It also demonstrates that the more expressive rules of the stable model semantics make the semantics clearly preferable over propositional logic when a problem has a more compact logic program representation. Conjunctive normal form representations are never more compact than logic program ones.
Cited by 76Open access
Federica Di Stefano, Mantas Šimkus · Proceedings of the AAAI Conference on Artificial Intelligence · 2024
This paper studies a stable model semantics for Description Logic (DL) knowledge bases (KBs) and for (possibly cyclic) terminologies, ultimately showing that terminologies under the proposed semantics can be equipped with effective reasoning algorithms. The semantics is derived using Quantified Equilibrium Logic, and---in contrast to the usual semantics of DLs based on classical logic---supports default negation and allows to combine the open-world and the closed-world assumptions in a natural way. Towards understanding the computational properties of this and related formalisms, we show a strong undecidability result that applies not only to KBs under the stable model semantics, but also to the more basic setting of minimal model reasoning. Specifically, we show that concept satisfiability in minimal models of an ALCIO KB is undecidable. We then turn our attention to (possibly cyclic) DL terminologies, where ontological axioms are limited to definitions of concept names in terms of complex concepts. This restriction still yields a very rich setting. We show that standard reasoning problems, like concept satisfiability and subsumption, are ExpTime-complete for terminologies expressed in ALCI under the stable model semantics.
Cited by 2Open access
2008
Abstract We propose a new declarative semantics for logic programs with negation. Its formulation is quite simple; at the same time, it is more general than the iterated fixed point semantics for stratified programs, and is applicable to some useful programs that are not stratified. 1. Introduction This paper belongs to the direction of research which attempts to define the declarative meaning of logic programs by means of "canonical models". The programs under consideration are sets of rules of the form A L1; : : : ; Lm (1)
Cited by 0
Michael J. Maher · 1996
Cited by 0
Xuegang Wang, Peter Mott · 1999
In this paper, we argue that both the stable model semantics and its three-valued version are conceptually flawed. 1 Introduction The semantics of logic programming and deductive databases has been extensively studied in the past two decades. A whole spectrum of semantic theories for logic programs have been proposed, ranging from those that infer very little information from a logic program ("skeptical") to those that infer a great deal ("credulous"). The most skeptical semantics is the well-founded semantics [4] while the most credulous is the the stable model semantics [6] and its different but equivalent three-valued versions, including 3-stable models [8], partial stable models [9] and preferred extensions [2]. The chief drawback of the stable semantics is that a two-valued stable model is not defined for all logic programs. In the three-valued variant a model is always defined but that model may leave all atoms undetermined [8]. The original problem of the non-existence of a ...
Cited by 0
COSTANTINI S., MAGLIOCCO, LANZARONE, GAETANO AURELIO · IrInSubria (University of Insubria) · 1996
Cited by 0
Patrik Simons, Ilkka Niemelä, Timo Soininen · Artificial Intelligence · 2002
Cited by 843
Francesco Ricca, Wolfgang Faber, Nicola Leone · 2008
Cited by 0
José Alberto Fernández, Jorge Lobo, Jack Minker et al. · 1993
We show that stable models of logic programs may be viewed as minimal models of programs that satisfy certain additional constraints. To do so, we transform the normal programs into disjunctive logic programs and sets of integrity constraints. We show that the stable models of the normal program coincide with the minimal models of the disjunctive program that satisfy the integrity constraints. As a consequence, the stable model semantics can be characterized using the Extended Generalized Closed World Assumption for disjunctive logic programs. Using this result, we develop a bottom-up algorithm for function free logic programs to find all stable models of a normal program by computing the perfect models of a disjunctive stratified logic program and checking them for consistency with the integrity constraints. The integrity constraints provide a rationale as to why some normal logic programs have no stable models. 1 Introduction We consider the problem of finding the stable models o...
Cited by 0
Mario Alviano, Michael Morak, Andréas Pieris · Edinburgh Research Explorer · 2017
Normal tuple-generating dependencies (NTGDs) are TGDs enriched with default negation, a.k.a. negation as failure. Query answering under NTGDs, where negation is interpreted according to the stable model semantics, is an intriguing new problem that gave rise to flourishing research activity in the database and KR communities. So far, all the existing works that investigate this problem, except for one recent paper that adopts an operational semantics based on the chase, follow the so-called logic programming (LP) approach. According to the LP approach, the existentially quantified variables are first eliminated via Skolemization, which leads to a normal logic program, and then the standard stable model semantics for normal logic programs is applied. However, as we discuss in the paper, Skolemization is not appropriate in the presence of default negation since it fails to capture the intended meaning of NTGDs, while the operational semantics mentioned above fails to overcome the limitations of the LP approach. This reveals the need to adopt an alternative approach to stable model semantics that is directly applicable to NTGDs with existentially quantified variables. We propose such an approach based on a recent characterization of stable models in terms of second-order logic, which indeed overcomes the limitations of the LP approach. We then perform an in-depth complexity analysis of query answering under prominent classes of NTGDs based on the main decidability paradigms for TGDs, namely weak-acyclicity, guardedness and stickiness. Interestingly, weakly-acyclic NTGDs give rise to robust and highly expressive query languages that allow us to solve in a declarative way problems in the second level of the polynomial hierarchy.
Cited by 13Open access
Joohyung Lee, Yi Wang · ArXiv.org · 2025
We define a stable model semantics for fuzzy propositional formulas, which generalizes both fuzzy propositional logic and the stable model semantics of classical propositional formulas. The syntax of the language is the same as the syntax of fuzzy propositional logic, but its semantics distinguishes stable models from non-stable models. The generality of the language allows for highly configurable nonmonotonic reasoning for dynamic domains involving graded truth degrees. We show that several properties of Boolean stable models are naturally extended to this many-valued setting, and discuss how it is related to other approaches to combining fuzzy logic and the stable model semantics.
Cited by 0Open access
PIRRI ARDIZZONE, Maria Fiora, Clara Pizzuti · IRIS Research product catalog (Sapienza University of Rome) · 1990
Cited by 0
Michael Bartholomew, Joohyung Lee · Artificial Intelligence · 2019
Cited by 7
Emad Saad · Lecture notes in computer science · 2007
Cited by 5