article

Stable models and circumscription

Authors:

Paolo Ferraris,

Vladimir LifschitzAuthors Info & Claims

Artificial Intelligence, Volume 175, Issue 1

Pages 236 - 263

https://doi.org/10.1016/j.artint.2010.04.011

Published: 01 January 2011 Publication History

Abstract

The concept of a stable model provided a declarative semantics for Prolog programs with negation as failure and became a starting point for the development of answer set programming. In this paper we propose a new definition of that concept, which covers many constructs used in answer set programming and, unlike the original definition, refers neither to grounding nor to fixpoints. It is based on a syntactic transformation similar to parallel circumscription.

References

[1]

Clark, Keith, Negation as failure. In: Gallaire, Herve, Minker, Jack (Eds.), Logic and Data Bases, Plenum Press, New York. pp. 293-322.

[2]

Erdem, Esra and Lifschitz, Vladimir, Tight logic programs. Theory and Practice of Logic Programming. v3. 499-518.

[3]

.

[4]

Fages, François, Consistency of Clark's completion and existence of stable models. Journal of Methods of Logic in Computer Science. v1. 51-60.

[5]

Ferraris, Paolo and Lifschitz, Vladimir, Mathematical foundations of answer set programming. In: We Will Show Them! Essays in Honour of Dov Gabbay, King's College Publications. pp. 615-664.

[6]

Paolo Ferraris, Joohyung Lee, Vladimir Lifschitz, A new perspective on stable models, in: Proceedings of International Joint Conference on Artificial Intelligence (IJCAI), 2007, pp. 372-379.

[7]

Paolo Ferraris, Joohyung Lee, Vladimir Lifschitz, Ravi Palla, Symmetric splitting in the general theory of stable models, in: Proceedings of International Joint Conference on Artificial Intelligence (IJCAI), 2009, pp. 797-803.

Digital Library

[8]

Paolo Ferraris, Answer sets for propositional theories, in: Proceedings of International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR), 2005, pp. 119-131.

Digital Library

[9]

Gelfond, Michael and Lifschitz, Vladimir, The stable model semantics for logic programming. In: Kowalski, Robert, Bowen, Kenneth (Eds.), Proceedings of International Logic Programming Conference and Symposium, MIT Press. pp. 1070-1080.

[10]

Gelfond, Michael and Lifschitz, Vladimir, Classical negation in logic programs and disjunctive databases. New Generation Computing. v9. 365-385.

[11]

Gomes, Carla P., Kautz, Henry, Sabharwal, Ashish and Selman, Bart, Satisfiability solvers. In: van Harmelen, Frank, Lifschitz, Vladimir, Porter, Bruce (Eds.), Handbook of Knowledge Representation, Elsevier. pp. 89-134.

[12]

Lee, Joohyung and Lin, Fangzhen, Loop formulas for circumscription. Artificial Intelligence. v170 i2. 160-185.

[13]

Joohyung Lee, Yunsong Meng, On loop formulas with variables, in: Proceedings of the International Conference on Knowledge Representation and Reasoning (KR), 2008, pp. 444-453.

[14]

Joohyung Lee, Vladimir Lifschitz, Ravi Palla, A reductive semantics for counting and choice in answer set programming, in: Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 2008, pp. 472-479.

[15]

Lifschitz, Vladimir, Pearce, David and Valverde, Agustin, Strongly equivalent logic programs. ACM Transactions on Computational Logic. v2. 526-541.

[16]

Vladimir Lifschitz, David Pearce, Agustin Valverde, A characterization of strong equivalence for logic programs with variables, in: Proceedings of International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR), 2007.

[17]

Vladimir Lifschitz, Computing circumscription, in: Proceedings of International Joint Conference on Artificial Intelligence (IJCAI), 1985, pp. 121-127.

[18]

Lifschitz, Vladimir, Pointwise circumscription. In: Ginsberg, Matthew (Ed.), Readings in Nonmonotonic Reasoning, Morgan Kaufmann, San Mateo, CA. pp. 179-193.

[19]

Vladimir Lifschitz, Twelve definitions of a stable model, in: Proceedings of International Conference on Logic Programming (ICLP), 2008, pp. 37-51.

Digital Library

[20]

Lin, Fangzhen and Reiter, Raymond, Rules as actions: A situation calculus semantics for logic programs. Journal of Logic Programming. v31. 299-330.

[21]

Lin, Fangzhen and Yoav, Shoham, A logic of knowledge and justified assumptions. Artificial Intelligence. v57. 271-289.

[22]

Lin, Fangzhen and Zhao, Yuting, ASSAT: Computing answer sets of a logic program by SAT solvers. In: Proceedings of National Conference on Artificial Intelligence (AAAI), MIT Press. pp. 112-117.

[23]

Fangzhen Lin, Yi Zhou, From answer set logic programming to circumscription via logic of GK, in: Proceedings of International Joint Conference on Artificial Intelligence (IJCAI), 2007.

Digital Library

[24]

Fangzhen Lin, A study of nonmonotonic reasoning, PhD thesis, Stanford University, 1991.

[25]

Marek, Victor and Truszczyński, Mirosław, Stable models and an alternative logic programming paradigm. In: The Logic Programming Paradigm: A 25-Year Perspective, Springer-Verlag. pp. 375-398.

[26]

McCarthy, John, Circumscription-a form of non-monotonic reasoning. Artificial Intelligence. v13. 27-39.

[27]

McCarthy, John, Applications of circumscription to formalizing common sense knowledge. Artificial Intelligence. v26 i3. 89-116.

[28]

Moore, Robert, Semantical considerations on nonmonotonic logic. Artificial Intelligence. v25 i1. 75-94.

[29]

Niemelä, Ilkka, Logic programs with stable model semantics as a constraint programming paradigm. Annals of Mathematics and Artificial Intelligence. v25. 241-273.

[30]

Oikarinen, Emilia and Janhunen, Tomi, Achieving compositionality of the stable model semantics for Smodels programs. Theory and Practice of Logic Programming. v5-6. 717-761.

[31]

David Pearce, Hans Tompits, Stefan Woltran, Encodings for equilibrium logic and logic programs with nested expressions, in: Proceedings of Portuguese Conference on Artificial Intelligence (EPIA), 2001, pp. 306-320.

Digital Library

[32]

Pearce, David, A new logical characterization of stable models and answer sets. In: Dix, Jürgen, Pereira, Luis, Przymusinski, Teodor (Eds.), Lecture Notes in Artificial Intelligence, vol. 1216. Springer-Verlag. pp. 57-70.

[33]

Reiter, Raymond, A logic for default reasoning. Artificial Intelligence. v13. 81-132.

[34]

Simons, Patrik, Niemelä, Ilkka and Soininen, Timo, Extending and implementing the stable model semantics. Artificial Intelligence. v138. 181-234.

[35]

Wallace, Mark, Tight, consistent and computable completions for unrestricted logic programs. Journal of Logic Programming. v15. 243-273.

Cited By

Heuer JWernhard C(2024)Synthesizing Strongly Equivalent Logic Programs: Beth Definability for Answer Set Programs via Craig Interpolation in First-Order LogicAutomated Reasoning10.1007/978-3-031-63498-7_11(172-193)Online publication date: 3-Jul-2024
https://dl.acm.org/doi/10.1007/978-3-031-63498-7_11
Fandinno JLifschitz VMarquis PSon TKern-Isberner G(2023)Omega-completeness of the logic of here-and-there and strong equivalence of logic programsProceedings of the 20th International Conference on Principles of Knowledge Representation and Reasoning10.24963/kr.2023/24(240-251)Online publication date: 2-Sep-2023
https://dl.acm.org/doi/10.24963/kr.2023/24
Fandinno JLierler YWilliams BChen YNeville J(2023)Splitting answer set programs with respect to intensionality statementsProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i5.25780(6338-6345)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i5.25780
Show More Cited By

Stable models and circumscription
1. Computing methodologies
  1. Artificial intelligence
    1. Knowledge representation and reasoning
2. Theory of computation
  1. Logic
  2. Models of computation

Recommendations

From answer set logic programming to circumscription via logic of GK

We first embed Pearce's equilibrium logic and Ferraris's propositional general logic programs in Lin and Shoham's logic of GK, a nonmonotonic modal logic that has been shown to include as special cases both Reiter's default logic in the propositional ...
Loop formulas for circumscription

Clark's completion is a simple nonmonotonic formalism and a special case of several nonmonotonic logics. Recently there has been work on extending completion with ''loop formulas'' so that general cases of nonmonotonic logics such as logic programs (...
Computing Circumscription Revisited: A Reduction Algorithm

In recent years, a great deal of attention has been devoted to logics of common-sense reasoning. Among the candidates proposed, circumscription has been perceived as an elegant mathematical technique for modeling nonmonotonic reasoning, but difficult to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Artificial Intelligence

Artificial Intelligence Volume 175, Issue 1

January, 2011

443 pages

ISSN:0004-3702

Issue’s Table of Contents

Copyright © Elsevier B.V. © 2010.

Publisher

Elsevier Science Publishers Ltd.

United Kingdom

Publication History

Published: 01 January 2011

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

83
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Heuer JWernhard C(2024)Synthesizing Strongly Equivalent Logic Programs: Beth Definability for Answer Set Programs via Craig Interpolation in First-Order LogicAutomated Reasoning10.1007/978-3-031-63498-7_11(172-193)Online publication date: 3-Jul-2024
https://dl.acm.org/doi/10.1007/978-3-031-63498-7_11
Fandinno JLifschitz VMarquis PSon TKern-Isberner G(2023)Omega-completeness of the logic of here-and-there and strong equivalence of logic programsProceedings of the 20th International Conference on Principles of Knowledge Representation and Reasoning10.24963/kr.2023/24(240-251)Online publication date: 2-Sep-2023
https://dl.acm.org/doi/10.24963/kr.2023/24
Fandinno JLierler YWilliams BChen YNeville J(2023)Splitting answer set programs with respect to intensionality statementsProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i5.25780(6338-6345)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i5.25780
Fandinno JLifschitz V(2023)On Heuer’s Procedure for Verifying Strong EquivalenceLogics in Artificial Intelligence10.1007/978-3-031-43619-2_18(253-261)Online publication date: 20-Sep-2023
https://dl.acm.org/doi/10.1007/978-3-031-43619-2_18
Lifschitz V(2022)Calculational ProofsEdsger Wybe Dijkstra10.1145/3544585.3544598(231-246)Online publication date: 12-Jul-2022
https://dl.acm.org/doi/10.1145/3544585.3544598
Bonatti PPetrova ISauro L(2022)Optimizing the computation of overriding in DL N Artificial Intelligence10.1016/j.artint.2022.103764311:COnline publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1016/j.artint.2022.103764
Hansen ZLierler Y(2022)Semantics for Conditional Literals via the SM OperatorLogic Programming and Nonmonotonic Reasoning10.1007/978-3-031-15707-3_20(259-272)Online publication date: 5-Sep-2022
https://dl.acm.org/doi/10.1007/978-3-031-15707-3_20
Fandinno JHansen ZLierler Y(2022)Arguing Correctness of ASP Programs with AggregatesLogic Programming and Nonmonotonic Reasoning10.1007/978-3-031-15707-3_15(190-202)Online publication date: 5-Sep-2022
https://dl.acm.org/doi/10.1007/978-3-031-15707-3_15
Gottlob GHernich AKupke CLukasiewicz T(2021)Stable Model Semantics for Guarded Existential Rules and Description Logics: Decidability and ComplexityJournal of the ACM10.1145/344750868:5(1-87)Online publication date: 22-Oct-2021
https://dl.acm.org/doi/10.1145/3447508
Tsampanaki NPatkos TFlouris GPlexousakis D(2021)Revising event calculus theories to recover from unexpected observationsAnnals of Mathematics and Artificial Intelligence10.1007/s10472-019-09663-589:1-2(209-236)Online publication date: 1-Feb-2021
https://dl.acm.org/doi/10.1007/s10472-019-09663-5
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents