Abstract
The paper continues the investigation of Poincare and Russel’s Vicious Circle Principle (VCP) in the context of the design of logic programming languages with sets. We expand previously introduced language \(\mathcal {A}log\) with aggregates by allowing infinite sets and several additional set related constructs useful for knowledge representation and teaching. In addition, we propose an alternative formalization of the original VCP and incorporate it into the semantics of new language, \(\mathcal {S}log^+\), which allows more liberal construction of sets and their use in programming rules. We show that, for programs without disjunction and infinite sets, the formal semantics of aggregates in \(\mathcal {S}log^+\) coincides with that of several other known languages. Their intuitive and formal semantics, however, are based on quite different ideas and seem to be more involved than that of \(\mathcal {S}log^+\).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
It is again similar to set theory where the difficulty is normally avoided by restricting comprehension axioms guaranteeing existence of sets denoted by expressions of the form \(\{X:p(X)\}\). In ASP such restrictions are encoded in the definition of answer sets.
- 2.
By a candidate answer set we mean a consistent set of ground regular literals satisfying the rules of the program.
- 3.
There is a common argument for the semantics in which \(\{p(1)\}\) would be the answer set of \(P_2\): “Since \(card\{X: p(X)\} \ge 0\) is always true it can be dropped from the rule without changing the rule’s meaning”. But the argument assumes existence of the set denoted by \(\{X:p(X)\}\) which is not always the case in \(\mathcal {A}log\).
- 4.
Of course this is true only because of our (somewhat arbitrary) decision to limit aggregates of \(\mathcal {A}log\) to those ranging over natural numbers. We could, of course, allow aggregates mapping sets into ordinals. In this case the body of the last rule of \(E_2\) will be defined and the only answer set of \(E_2\) will be \(S_{E_1}\).
References
Alviano, M., Faber, W.: Stable model semantics of abstract dialectical frameworks revisited: a logic programming perspective. In: Proceedings of the 21st International Joint Conference on Artificial Intelligence, IJCAI Organization, Buenos Aires, Argentina, pp. 2684–2690 (2015)
Alviano, M., Faber, W., Gebser, M.: Rewriting recursive aggregates in answer set programming: back to monotonicity. Theory Pract. Logic Program. 15(4–5), 559–573 (2015)
Dovier, A., Pontelli, E., Rossi, G.: Intensional sets in CLP. In: Palamidessi, C. (ed.) ICLP 2003. LNCS, vol. 2916, pp. 284–299. Springer, Heidelberg (2003). doi:10.1007/978-3-540-24599-5_20
Faber, W., Pfeifer, G., Leone, N.: Semantics and complexity of recursive aggregates in answer set programming. Artif. Intell. 175(1), 278–298 (2011)
Ferraris, P., Lifschitz, V.: Weight constraints as nested expressions. TPLP 5(1–2), 45–74 (2005)
Gebser, M., Harrison, A., Kaminski, R., Lifschitz, V., Schaub, T.: Abstract gringo. Theory Pract. Logic Program. 15(4–5), 449–463 (2015)
Gelfond, M.: Representing knowledge in A-Prolog. In: Kakas, A.C., Sadri, F. (eds.) Computational Logic: Logic Programming and Beyond. LNCS (LNAI), vol. 2408, pp. 413–451. Springer, Heidelberg (2002). doi:10.1007/3-540-45632-5_16
Gelfond, M.: New semantics for epistemic specifications. In: Delgrande, J.P., Faber, W. (eds.) LPNMR 2011. LNCS, vol. 6645, pp. 260–265. Springer, Heidelberg (2011). doi:10.1007/978-3-642-20895-9_29
Gelfond, M., Kahl, Y.: Knowledge Representation, Reasoning, and the Design of Intelligent Agents. Cambridge University Press, Cambridge (2014)
Gelfond, M., Lifschitz, V.: Classical negation in logic programs and disjunctive databases. New Gener. Comput. 9(3/4), 365–386 (1991)
Gelfond, M., Przymusinska, H.: On consistency and completeness of autoepistemic theories. Fundam. Inf. 16(1), 59–92 (1992)
Gelfond, M., Zhang, Y.: Vicious circle principle and logic programs with aggregates. TPLP 14(4–5), 587–601 (2014). http://dx.doi.org/10.1017/S1471068414000222
Harrison, A.J., Lifschitz, V., Yang, F.: The semantics of gringo and infinitary propositional formulas. In: KR (2014)
Lee, J., Lifschitz, V., Palla, R.: A reductive semantics for counting and choice in answer set programming. In: Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence, AAAI 2008, Chicago, Illinois, USA, 13–17 July 2008, pp. 472–479 (2008). http://www.aaai.org/Library/AAAI/2008/aaai08-075.php
Lifschitz, V., Turner, H.: Splitting a logic program. In: Proceedings of the 11th International Conference on Logic Programming (ICLP 1994), pp. 23–38 (1994)
Liu, G., Goebel, R., Janhunen, T., Niemelä, I., You, J.-H.: Strong equivalence of logic programs with abstract constraint atoms. In: Delgrande, J.P., Faber, W. (eds.) LPNMR 2011. LNCS, vol. 6645, pp. 161–173. Springer, Heidelberg (2011). doi:10.1007/978-3-642-20895-9_15
Liu, L., Pontelli, E., Son, T.C., Truszczynski, M.: Logic programs with abstract constraint atoms: the role of computations. Artif. Intell. 174(3–4), 295–315 (2010)
Marek, V.W., Remmel, J.B.: Set constraints in logic programming. In: Lifschitz, V., Niemelä, I. (eds.) LPNMR 2004. LNCS, vol. 2923, pp. 167–179. Springer, Heidelberg (2003). doi:10.1007/978-3-540-24609-1_16
Niemela, I., Simons, P., Soininen, T.: Extending and implementing the stable model semantics. Artif. Intell. 138(1–2), 181–234 (2002)
Pelov, N., Denecker, M., Bruynooghe, M.: Well-fouded and stable semantics of logic programs with aggregates. Theory Pract. Logic Program. 7, 355–375 (2007)
Poincare, H.: Les mathematiques et la logique. Rev. de metaphysique et de morale 14, 294–317 (1906)
Russell, B.: Mathematical logic as based on the theory of types. Am. J. Math. 30(3), 222–262 (1908)
Shen, Y., You, J., Yuan, L.: Characterizations of stable model semantics for logic programs with arbitrary constraint atoms. TPLP 9(4), 529–564 (2009)
Son, T.C., Pontelli, E.: A constructive semantic characterization of aggregates in answer set programming. TPLP 7(3), 355–375 (2007)
Strass, H.: Approximating operators and semantics for abstract dialectical frameworks. Artif. Intell. 205, 39–70 (2013)
Truszczynski, M.: Connecting first-order ASP and the logic FO(ID) through reducts. In: Erdem, E., Lee, J., Lierler, Y., Pearce, D. (eds.) Correct Reasoning. LNCS, vol. 7265, pp. 543–559. Springer, Heidelberg (2012). doi:10.1007/978-3-642-30743-0_37
Turner, H.: Splitting a default theory. In: Proceedings of AAAI 1996, pp. 645–651 (1996)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Gelfond, M., Zhang, Y. (2017). Vicious Circle Principle and Formation of Sets in ASP Based Languages. In: Balduccini, M., Janhunen, T. (eds) Logic Programming and Nonmonotonic Reasoning. LPNMR 2017. Lecture Notes in Computer Science(), vol 10377. Springer, Cham. https://doi.org/10.1007/978-3-319-61660-5_14
Download citation
DOI: https://doi.org/10.1007/978-3-319-61660-5_14
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-61659-9
Online ISBN: 978-3-319-61660-5
eBook Packages: Computer ScienceComputer Science (R0)