Extending and implementing the stable model semantics

By Patrik Simons, Ilkka Niemelä, Timo Soininen. Artificial Intelligence, 2000

1,014 citations recorded by the source corpus.

A novel logic program like language, weight constraint rules, is developed for answer set programming purposes. It generalizes normal logic programs by allowing weight constraints in place of literals to represent, e.g., cardinality and resource constraints and by providing optimization capabilities. A declarative semantics is developed which extends the stable model semantics of normal programs. The computational complexity of the language is shown to be similar to that of normal programs under the stable model semantics. A simple embedding of general weight constraint rules to a small subclass of the language called basic constraint rules is devised. An implementation of the language, the SMODELS system, is developed based on this embedding. It uses a two level architecture consisting of a front-end and a kernel language implementation. The front-end allows restricted use of variables and functions and compiles general weight constraint rules to basic constraint rules. A major part of the work is the development of an efficient search procedure for computing stable models for this kernel language. The procedure is compared with and empirically tested against satisfiability checkers and an implementation of the stable model semantics. It offers a competitive implementation of the stable model semantics for normal programs and attractive performance for problems where the new types of rules provide a compact representation.

Subfields: Artificial Intelligence

View Paper: https://www.semanticscholar.org/paper/01e70dec1012327589b166ca5832c1dc50288194

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

ASP-Core-2 Input Language Format (2019, background): “…of proposals for adding aggregates to ASP (Kemp and Stuckey 1991; Van Gelder 1992; Osorio and Jayaraman 1999; Ross and Sagiv 1997; Denecker et al. 2001; Gelfond 2002; Simons et al. 2002; Dell’Armi et al. 2003; Pelov and Truszczyński 2004; Pelov et al. 2004; Ferraris 2005; Pelov et al. 2007).”
clasp : A Conflict-Driven Answer Set Solver (2007, background): “Unfounded set detection within clasp combines source pointers [12] with the unfounded set computation algorithm in [13].”
Multi-shot ASP solving with clingo (2017, background): “12 A choice rule (Simons et al. 2002) of the form {a} ← corresponds to (normal) rules a← ∼a′ and a′ ← ∼a, where a′ is a fresh atom.”
Constraint-based Causal Discovery: Conflict Resolution with Answer Set Programming (2014, methodology): “Be- low, in Appendices C and F, we specify how to add an intervention operation to the ASP-encoding while ensuring that the d-connection properties are appropriately preserved for the d-connection graphs that specify the test results for experimental data sets.”
The DLV system for knowledge representation and reasoning (2002, methodology): “The graph instances were generated using a tool by Patrik Simons (http://tcs.hut.fi/Software/smodels/misc/hamilton.tar.gz) which originally was used to compare Smodels against SAT solvers [Simons 2000].”
Conflict-driven answer set solving: From theory to practice (2012, methodology): “To our knowledge, the only native ASP solver other than clasp that implements conflict-driven learning is smodelscc [126],16 while ASP solvers like dlv [83], smodels [119], and nomore++ [1] perform DPLL-style search.”
Potassco: The Potsdam Answer Set Solving Collection (2011, neutral): “A human-readable format is obtained by invoking gringo with the option --text (or -t for short), e.g.:”
Answer Set Solving in Practice (2012, neutral): “[69] P.”