Skip to main content
Top
Published in: KI - Künstliche Intelligenz 2-3/2018

13-06-2018 | Technical Contribution

Answer Set Programming from a Logical Point of View

Authors: Pedro Cabalar, David Pearce, Agustín Valverde

Published in: KI - Künstliche Intelligenz | Issue 2-3/2018

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In this paper we provide an introductory explanation of the underlying semantics of answer set programming in terms of equilibrium logic. Rather than a thorough formal presentation of this formalism and its properties, we emphasize the intuitive meaning of its main logical definitions, explaining their effect on some example programs. We also overview some of the main extensions and relations to other logical approaches.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

KI - Künstliche Intelligenz

The Scientific journal "KI – Künstliche Intelligenz" is the official journal of the division for artificial intelligence within the "Gesellschaft für Informatik e.V." (GI) – the German Informatics Society - with constributions from troughout the field of artificial intelligence.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Show more products
Footnotes
1
Notice that \(\lnot { fire}\) is, read as “we have no evidence on fire,” is either certain (when indeed \({ fire}\) is false) or false (when some evidence exists, i.e. \({ fire}\) is certain or weakly true).
 
2
These sets are informally known as “here” and “there”. The reader familar with possible worlds semantics may think of them as the atoms verified at two worlds, ‘here’ and ‘there’.
 
3
See [6], and also [7] for more detailed information and references.
 
4
Using HT-logic we can only test the equivalence of ground rules and programs. In practice it makes sense to apply a first-order, quantified version of HT that captures the strong equivalence of programs with variables. For details, see [9, 10]. The complexity of strong equivalence for non-ground programs is analysed in [11].
 
5
It is slightly unfortunate that [19] called it “classical” negation.
 
6
Notice that the meaning of such a relation is still co-determined by the two components \(\mathcal {T}\) and \(\Pi\) because normally not all models of \(\mathcal {T}\) will be able to be enriched into equilibrium models of \(\mathcal {T} \cup \Pi\).
 
7
The main references are as follows. For the complexity of satisfiability in many-valued logics such as HT, see [38]. For the complexity of reasoning tasks associated with disjunctive logic programs, see [39]. For the strong equivalence of logic programs, see [37] and also independently some results of [40] and [41]. For the full details of the reduction method sketched here, see [37, 42].
 
8
Ie. logics captured semantically by possible worlds frames with a reflexive accessibility relation.
 
9
See [48].
 
10
Another modal embedding of HT can be found in [54].
 
Literature
2.
go back to reference Gelfond M, Lifschitz V (1988) The stable models semantics for logic programming. In: Proc. of the 5th intl. conf. on log. prog., pp 1070–1080 Gelfond M, Lifschitz V (1988) The stable models semantics for logic programming. In: Proc. of the 5th intl. conf. on log. prog., pp 1070–1080
3.
go back to reference Heyting A (1930) Die formalen Regeln der intuitionistischen Logik. Sitzungsberichte der Preussischen Akademie der Wissenschaften, Physikalisch-mathematische Klasse, pp 42–56 Heyting A (1930) Die formalen Regeln der intuitionistischen Logik. Sitzungsberichte der Preussischen Akademie der Wissenschaften, Physikalisch-mathematische Klasse, pp 42–56
4.
go back to reference Pearce D. (1997) A new logical characterisation of stable models and answer sets. In: Proc. of non monotonic extensions of log. progr Pearce D. (1997) A new logical characterisation of stable models and answer sets. In: Proc. of non monotonic extensions of log. progr
7.
go back to reference Cabalar P, Fandinno J, Fariñas del Cerro L, Pearce D, Valverde A (2017) On the properties of atom definability and well-supportedness in logic programming. In: Proc. of 18th Conf. on art. intell., pp. 624–636 Cabalar P, Fandinno J, Fariñas del Cerro L, Pearce D, Valverde A (2017) On the properties of atom definability and well-supportedness in logic programming. In: Proc. of 18th Conf. on art. intell., pp. 624–636
9.
go back to reference Lifschitz V, Pearce D, Valverde A (2007) A characterization of strong equivalence for logic programs with variables. In: Proc. of 9th intl. conf. of log. prog. and nonm. reas., pp. 188–200 Lifschitz V, Pearce D, Valverde A (2007) A characterization of strong equivalence for logic programs with variables. In: Proc. of 9th intl. conf. of log. prog. and nonm. reas., pp. 188–200
11.
go back to reference Eiter T, Fink M, Tompits H, Woltran S (2005) Strong and uniform equivalence in answer-set programming: characterizations and complexity results for the non-ground case. In: Proc. of The 20th nat. conf. on artif. intell; and the 7th innov. apps. of artif. intell. conf., pp. 695–700 Eiter T, Fink M, Tompits H, Woltran S (2005) Strong and uniform equivalence in answer-set programming: characterizations and complexity results for the non-ground case. In: Proc. of The 20th nat. conf. on artif. intell; and the 7th innov. apps. of artif. intell. conf., pp. 695–700
12.
go back to reference Cabalar P, Ferraris P (2007) Propositional theories are strongly equivalent to logic programs. TPLP 7(6):745–759MathSciNetMATH Cabalar P, Ferraris P (2007) Propositional theories are strongly equivalent to logic programs. TPLP 7(6):745–759MathSciNetMATH
13.
go back to reference Cabalar P, Pearce D, Valverde A (2005) Reducing propositional theories in equilibrium logic to logic programs. In: Proc. of the 12th Europ. conf. on artif. intell., pp. 4–17 Cabalar P, Pearce D, Valverde A (2005) Reducing propositional theories in equilibrium logic to logic programs. In: Proc. of the 12th Europ. conf. on artif. intell., pp. 4–17
15.
go back to reference Gelfond M, Zhang Y (2014) Vicious circle principle and logic programs with aggregates. TPLP 14(4–5):587–601MathSciNetMATH Gelfond M, Zhang Y (2014) Vicious circle principle and logic programs with aggregates. TPLP 14(4–5):587–601MathSciNetMATH
16.
go back to reference Cabalar P, Fandinno J, Schaub T, Schellhorn S (2017) Gelfond-Zhang aggregates as propositional formulas. In: Proc. of the 14th intl. conf. on log. prog. and nonm. reas., pp. 117–131 Cabalar P, Fandinno J, Schaub T, Schellhorn S (2017) Gelfond-Zhang aggregates as propositional formulas. In: Proc. of the 14th intl. conf. on log. prog. and nonm. reas., pp. 117–131
17.
go back to reference Pearce D, Wagner G (1989) Logic programming with strong negation. In: Proc. of extensions of logic programming, pp. 311–326 Pearce D, Wagner G (1989) Logic programming with strong negation. In: Proc. of extensions of logic programming, pp. 311–326
18.
go back to reference Pearce D, Wagner G (1990) Reasoning with negative information, I: strong negation in logic programs. Language, Knowledge, and Intentionality ? Perspectives on the Philosophy of Jaakko Hintikka. Acta Philos Fennica 49:430–453 Pearce D, Wagner G (1990) Reasoning with negative information, I: strong negation in logic programs. Language, Knowledge, and Intentionality ? Perspectives on the Philosophy of Jaakko Hintikka. Acta Philos Fennica 49:430–453
19.
go back to reference Gelfond M, Lifschitz V (1990) Logic programs with classical negation. In: Proc. of 7th Intl. conf. on log. prog., pp. 579–597 Gelfond M, Lifschitz V (1990) Logic programs with classical negation. In: Proc. of 7th Intl. conf. on log. prog., pp. 579–597
21.
go back to reference Vorob’ev N (1952) A constructive propositional calculus with strong negation. Doklady Akademii Nauk SSR 85:465–468 (in Russian) Vorob’ev N (1952) A constructive propositional calculus with strong negation. Doklady Akademii Nauk SSR 85:465–468 (in Russian)
22.
go back to reference Vorob’ev N (1952) The problem of deducibility in constructive propositional calculus with strong negation. Doklady Akademii Nauk SSR 85:689–692 (in Russian) Vorob’ev N (1952) The problem of deducibility in constructive propositional calculus with strong negation. Doklady Akademii Nauk SSR 85:689–692 (in Russian)
24.
go back to reference Rosati R (2005) Semantic and computational advantages of the safe integration of ontologies and rules. In: Proc. of 3th intl. works. of principles and practice of semantic web reasoning, pp. 50–64 Rosati R (2005) Semantic and computational advantages of the safe integration of ontologies and rules. In: Proc. of 3th intl. works. of principles and practice of semantic web reasoning, pp. 50–64
25.
go back to reference Rosati R (2006) Dl+log: tight integration of description logics and disjunctive datalog. In: KR, pp. 68–78 Rosati R (2006) Dl+log: tight integration of description logics and disjunctive datalog. In: KR, pp. 68–78
26.
go back to reference de Bruijn J, Pearce D, Polleres A, Valverde A (2010) A semantical framework for hybrid knowledge bases. Knowl Inf Syst 25(1):81–104CrossRef de Bruijn J, Pearce D, Polleres A, Valverde A (2010) A semantical framework for hybrid knowledge bases. Knowl Inf Syst 25(1):81–104CrossRef
27.
go back to reference Eiter T, Lukasiewicz T, Schindlauer R, Tompits H (2004) Combining answer set programming with description logics for the semantic web. In: Proc. of 9th intl. conf. of knowledge representation, pp. 141–151 Eiter T, Lukasiewicz T, Schindlauer R, Tompits H (2004) Combining answer set programming with description logics for the semantic web. In: Proc. of 9th intl. conf. of knowledge representation, pp. 141–151
28.
go back to reference Fink M, Pearce D (2010) A logical semantics for description logic programs. In: Proc. of 12th Europ. Conf. of logics in artif. intell., pp. 156–168 Fink M, Pearce D (2010) A logical semantics for description logic programs. In: Proc. of 12th Europ. Conf. of logics in artif. intell., pp. 156–168
29.
go back to reference Kamp JA (1968) Tense logic and the theory of linear order. Ph.D. thesis, University of California at Los Angeles Kamp JA (1968) Tense logic and the theory of linear order. Ph.D. thesis, University of California at Los Angeles
30.
go back to reference Cabalar P, Pérez G (2007) Temporal equilibrium logic: a first approach. In: Proc. of the 11th intl. conf. on computer aided systems theory, pp. 241–248 Cabalar P, Pérez G (2007) Temporal equilibrium logic: a first approach. In: Proc. of the 11th intl. conf. on computer aided systems theory, pp. 241–248
31.
go back to reference Cabalar P (2015) Stable models for temporal theories. In: Proc. of the 13th intl. conf. on log. prog. and nonm. reas., pp. 1–13 Cabalar P (2015) Stable models for temporal theories. In: Proc. of the 13th intl. conf. on log. prog. and nonm. reas., pp. 1–13
34.
go back to reference Fariñas del Cerro L, Herzig A, Su EI (2015) Epistemic equilibrium logic. In: Proc. of the 24th intl. joint conf. on artif. intell., pp. 2964–2970 Fariñas del Cerro L, Herzig A, Su EI (2015) Epistemic equilibrium logic. In: Proc. of the 24th intl. joint conf. on artif. intell., pp. 2964–2970
35.
go back to reference Gelfond M (1991) Strong introspection. In: Proc. of the 9th nat. conf. on artif. intell., pp. 386–391 Gelfond M (1991) Strong introspection. In: Proc. of the 9th nat. conf. on artif. intell., pp. 386–391
37.
go back to reference Pearce D, Tompits H, Woltran S (2001) Encodings for equilibrium logic and logic programs with nested expressions. In: Proc. of 10th Portuguese conf. on artif. intell., pp. 306–320 Pearce D, Tompits H, Woltran S (2001) Encodings for equilibrium logic and logic programs with nested expressions. In: Proc. of 10th Portuguese conf. on artif. intell., pp. 306–320
39.
go back to reference Eiter T, Gottlob G (1995) On the computational cost of disjunctive logic programming: propositional case. Ann Math Artif Intell 15(3–4):289–323MathSciNetCrossRefMATH Eiter T, Gottlob G (1995) On the computational cost of disjunctive logic programming: propositional case. Ann Math Artif Intell 15(3–4):289–323MathSciNetCrossRefMATH
40.
go back to reference Lin F (2002) Reducing strong equivalence of logic programs to entailment in classical propositional logic. In: Proc. of the 8th intl. conf. on knowledge representation, pp. 170–176 Lin F (2002) Reducing strong equivalence of logic programs to entailment in classical propositional logic. In: Proc. of the 8th intl. conf. on knowledge representation, pp. 170–176
41.
go back to reference Turner H (2003) Strong equivalence made easy: nested expressions and weight constraints. TPLP 3(4–5):609–622MathSciNetMATH Turner H (2003) Strong equivalence made easy: nested expressions and weight constraints. TPLP 3(4–5):609–622MathSciNetMATH
42.
go back to reference Pearce D, Tompits H, Woltran S (2009) Characterising equilibrium logic and nested logic programs: reductions and complexity. TPLP 9(5):565–616MathSciNetMATH Pearce D, Tompits H, Woltran S (2009) Characterising equilibrium logic and nested logic programs: reductions and complexity. TPLP 9(5):565–616MathSciNetMATH
43.
go back to reference Ferraris P, Lee J, Lifschitz V (2007) A new perspective on stable models. In: Proc. of the 20th intl. joint conf. on artif. Intell Ferraris P, Lee J, Lifschitz V (2007) A new perspective on stable models. In: Proc. of the 20th intl. joint conf. on artif. Intell
44.
go back to reference Gödel K (1933) Eine Interpretation des intuitionistischen Aussagenkalküls. Ergebnisse Math Colloq 4:39–40MATH Gödel K (1933) Eine Interpretation des intuitionistischen Aussagenkalküls. Ergebnisse Math Colloq 4:39–40MATH
46.
go back to reference Esakia L (1976) The modal logic of topological spaces. Georgian Academy of Sciences, Tbilisi, pp 1–22 (preprint) Esakia L (1976) The modal logic of topological spaces. Georgian Academy of Sciences, Tbilisi, pp 1–22 (preprint)
48.
go back to reference Marek W, Truszczynski M (1993) Nonmonotonic reasoning: context-dependent reasoning. Springer, Berlin HeidelbergMATH Marek W, Truszczynski M (1993) Nonmonotonic reasoning: context-dependent reasoning. Springer, Berlin HeidelbergMATH
49.
go back to reference Przymusinski T (1991) Stable semantics for disjunctive programs. N Gener Comput 9:401–424CrossRefMATH Przymusinski T (1991) Stable semantics for disjunctive programs. N Gener Comput 9:401–424CrossRefMATH
50.
go back to reference Lifschitz V, Schwarz G (1993) Extended logic programs as autoepistemic theories. In: Proc. of intl. conf. on log. prog. and nonm. reas., pp. 101–114 Lifschitz V, Schwarz G (1993) Extended logic programs as autoepistemic theories. In: Proc. of intl. conf. on log. prog. and nonm. reas., pp. 101–114
51.
go back to reference Marek W, Truszczynski M (1993) Reflective autoepistemic logic and logic programming. In: Proc. of intl. conf. on log. prog. and nonm. reas., pp. 115–131 Marek W, Truszczynski M (1993) Reflective autoepistemic logic and logic programming. In: Proc. of intl. conf. on log. prog. and nonm. reas., pp. 115–131
52.
go back to reference Chen J (1993) Minimal knowledge + negation as failure = only knowing (sometimes). In: Proc. of intl. conf. on log. prog. and nonm. reas., pp. 132–150 Chen J (1993) Minimal knowledge + negation as failure = only knowing (sometimes). In: Proc. of intl. conf. on log. prog. and nonm. reas., pp. 132–150
53.
go back to reference Pearce D, Uridia L (2008) The Gödel and the splitting translations. In: Nonmonotonic reasoning. Essays celebrating its 30th anniversary. College Publications, pp. 335–360. Pearce D, Uridia L (2008) The Gödel and the splitting translations. In: Nonmonotonic reasoning. Essays celebrating its 30th anniversary. College Publications, pp. 335–360.
54.
go back to reference Truszczynski M (2007) The modal logic s4f, the default logic, and the logic here-and-there. In: Proc. of the 22nd AAAI conf. on artif. intell., pp. 508–514 Truszczynski M (2007) The modal logic s4f, the default logic, and the logic here-and-there. In: Proc. of the 22nd AAAI conf. on artif. intell., pp. 508–514
55.
go back to reference Gödel K (1932) Zum intuitionistischen Aussagenkalkül. Anzeiger der Akademie der Wissenschaften Wien, mathematisch, naturwissenschaftliche Klasse 69:65–66MATH Gödel K (1932) Zum intuitionistischen Aussagenkalkül. Anzeiger der Akademie der Wissenschaften Wien, mathematisch, naturwissenschaftliche Klasse 69:65–66MATH
56.
go back to reference Łukasiewicz J (1941) Die Logik und das Grundlagenproblem. Les Entreties de Zürich sur les Fondaments et la Méthode des Sciences Mathématiques 6-9, (1938) 12:87–100 Łukasiewicz J (1941) Die Logik und das Grundlagenproblem. Les Entreties de Zürich sur les Fondaments et la Méthode des Sciences Mathématiques 6-9, (1938) 12:87–100
57.
go back to reference Smetanich YS (1960) On completeness of a propositional calculus with an additional operation of one variable. Trudy Moscovskogo matrmaticheskogo obshchestva 9:357–372 (in Russian) Smetanich YS (1960) On completeness of a propositional calculus with an additional operation of one variable. Trudy Moscovskogo matrmaticheskogo obshchestva 9:357–372 (in Russian)
59.
go back to reference Hosoi T (1966) The axiomatization of the intermediate propositional systems \(S_n\) of Gödel. J Facul Sci Univ Tokyo 13:183–187MATH Hosoi T (1966) The axiomatization of the intermediate propositional systems \(S_n\) of Gödel. J Facul Sci Univ Tokyo 13:183–187MATH
60.
go back to reference Ono H (1983) Model extension theorem and Craig’s interpolation theorem for intermediate predicate logics. Rep Math Logic 15:41–58MathSciNetMATH Ono H (1983) Model extension theorem and Craig’s interpolation theorem for intermediate predicate logics. Rep Math Logic 15:41–58MathSciNetMATH
61.
go back to reference Pearce D, Valverde A (2004) Towards a first order equilibrium logic for nonmonotonic reasoning. In: Proc. of the 9th Europ. conf. on logics in artif. intell., pp. 147–160 Pearce D, Valverde A (2004) Towards a first order equilibrium logic for nonmonotonic reasoning. In: Proc. of the 9th Europ. conf. on logics in artif. intell., pp. 147–160
63.
64.
go back to reference Cabalar P, Fariñas del Cerro L, Pearce D, Valverde A (2014) A free logic for stable models with partial intensional functions. In: Proc. of 14th Europ. conf. of logics in artif. intell., pp. 340–354 Cabalar P, Fariñas del Cerro L, Pearce D, Valverde A (2014) A free logic for stable models with partial intensional functions. In: Proc. of 14th Europ. conf. of logics in artif. intell., pp. 340–354
65.
go back to reference Harrison A, Lifschitz V, Pearce D, Valverde A (2017) Infinitary equilibrium logic and strongly equivalent logic programs. Artif Intell 246:22–33MathSciNetCrossRefMATH Harrison A, Lifschitz V, Pearce D, Valverde A (2017) Infinitary equilibrium logic and strongly equivalent logic programs. Artif Intell 246:22–33MathSciNetCrossRefMATH
Metadata
Title
Answer Set Programming from a Logical Point of View
Authors
Pedro Cabalar
David Pearce
Agustín Valverde
Publication date
13-06-2018
Publisher
Springer Berlin Heidelberg
Published in
KI - Künstliche Intelligenz / Issue 2-3/2018
Print ISSN: 0933-1875
Electronic ISSN: 1610-1987
DOI
https://doi.org/10.1007/s13218-018-0547-7

Other articles of this Issue 2-3/2018

KI - Künstliche Intelligenz 2-3/2018 Go to the issue

Premium Partner