×

zbMATH — the first resource for mathematics

Vicious circle principle, aggregates, and formation of sets in ASP based languages. (English) Zbl 07099223
Summary: The paper introduces an extension of the original Answer Set Prolog (ASP) by several set constructs including aggregates, defined as functions on sets. The new language, called \(\mathcal{A}\log\) allows creating sets based on the Vicious Circle Principle by Poincaré and Russell which eliminates a number of problems found in existing extensions of ASP by aggregates. We argue that, despite the fact that \(\mathcal{A}\log\) is not as expressive as other extensions of ASP by aggregates, clarity of its syntax and semantics, addition of several new set-based constructs, and simplicity and the ease of use make it a viable competitor to these languages. We also study a number of important properties of the language and show how ideas used in its design can be utilized to generalize and simplify the definition of another important extension of ASP by aggregates.
MSC:
68T Artificial intelligence
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Gelfond, M., On stratified autoepistemic theories, (Proceedings of Sixth National Conference on Artificial Intelligence, (1987)), 207-212
[2] Gelfond, M.; Lifschitz, V., The stable model semantics for logic programming, (Proceedings of ICLP-88, (1988)), 1070-1080
[3] Gelfond, M.; Lifschitz, V., Classical negation in logic programs and disjunctive databases, New Gener. Comput., 9, 3/4, 365-386, (1991) · Zbl 0735.68012
[4] Niemela, I.; Simons, P.; Soininen, T., Extending and implementing the stable model semantics, Artif. Intell., 138, 1-2, 181-234, (2002) · Zbl 0995.68021
[5] Lin, F.; Zhao, Y., ASSAT: computing answer sets of a logic program by SAT solvers, Artif. Intell., 157, 1-2, 115-137, (2004) · Zbl 1085.68544
[6] Lierler, Y., Cmodels - SAT-based disjunctive answer set solver, (LPNMR, (2005)), 447-451
[7] Lin, Z.; Zhang, Y.; Hernandez, H., Fast SAT-based answer set solver, (Proceedings of AAAI, (2006)), 92-97
[8] Leone, N.; Pfeifer, G.; Faber, W.; Eiter, T.; Gottlob, G.; Perri, S.; Scarcello, F., The DLV system for knowledge representation and reasoning, ACM Trans. Comput. Log., 7, 499-562, (2006) · Zbl 1367.68308
[9] Faber, W.; Pfeifer, G.; Leone, N.; Dell’Armi, T.; Ielpa, G., Design and implementation of aggregate functions in the DLV system, Theory Pract. Log. Program., 8, 5-6, 545-580, (2008) · Zbl 1156.68010
[10] Gebser, M.; Kaufmann, B.; Neumann, A.; Schaub, T., Conflict-driven answer set enumeration, (International Conference on Logic Programming and Nonmonotonic Reasoning, (2007), Springer), 136-148 · Zbl 1149.68332
[11] Janhunen, T.; Niemelä, I., Compact translations of non-disjunctive answer set programs to propositional clauses, (Logic Programming, Knowledge Representation, and Nonmonotonic Reasoning, (2011), Springer), 111-130 · Zbl 1326.68058
[12] Gebser, M.; Kaufmann, B.; Schaub, T., Conflict-driven answer set solving: from theory to practice, Artif. Intell., 187, 52-89, (2012) · Zbl 1251.68060
[13] Alviano, M.; Dodaro, C.; Faber, W.; Leone, N.; Ricca, F., WASP: a native ASP solver based on constraint learning, (International Conference on Logic Programming and Nonmonotonic Reasoning, (2013), Springer), 54-66
[14] Maratea, M.; Pulina, L.; Ricca, F., Multi-level algorithm selection for ASP, (International Conference on Logic Programming and Nonmonotonic Reasoning, (2015), Springer), 439-445 · Zbl 06504251
[15] Balduccini, M.; Baral, C.; Lierler, Y., Knowledge representation and question answering, (Handbook of Knowledge Representation, (2006)), chapter 21
[16] Brewka, G.; Eiter, T.; Truszczynski, M., Answer set programming at a glance, Commun. ACM, 54, 12, 92-103, (2011)
[17] Erdem, E.; Gelfond, M.; Leone, N., Applications of answer set programming, AI Mag., 37, 3, 53-68, (2016)
[18] Falkner, A.; Friedrich, G.; Schekotihin, K.; Taupe, R.; Teppan, E. C., Industrial applications of answer set programming, Künstl. Intell., 32, 2-3, 165-176, (2018)
[19] Balduccini, M.; Gelfond, M., Logic programs with consistency-restoring rules, (International Symposium on Logical Formalization of Commonsense Reasoning. International Symposium on Logical Formalization of Commonsense Reasoning, AAAI 2003 Spring Symposium Series, vol. 102, (2003), The AAAI Press)
[20] Baral, C.; Gelfond, M.; Rushton, J. N., Probabilistic reasoning with answer sets, Theory Pract. Log. Program., 9, 1, 57-144, (2009) · Zbl 1170.68003
[21] Pearce, D., A new logical characterization of stable models and answer sets, (Non-monotonic Extension of Logic Programming. Non-monotonic Extension of Logic Programming, LNCS, vol. 1216, (1997), Springer Verlag), 57-70
[22] Ferraris, P.; Lee, J.; Lifschitz, V., A new perspective on stable models, (Proceedings of International Joint Conference on Artificial Intelligence (IJCAI), (2007)), 372-379
[23] Niemelä, I.; Simons, P., Extending the smodels system with cardinality and weight constraints, (Logic-Based Artificial Intelligence, (2000), Springer), 491-521 · Zbl 0979.68015
[24] Buccafurri, F.; Leone, N.; Rullo, P., Strong and weak constraints in disjunctive datalog, (International Conference on Logic Programming and Nonmonotonic Reasoning, (1997), Springer), 2-17
[25] Pelov, N.; Denecker, M.; Bruynooghe, M., Well-founded and stable semantics of logic programs with aggregates, Theory Pract. Log. Program., 7, 355-375, (2007) · Zbl 1111.68070
[26] Son, T. C.; Pontelli, E., A constructive semantic characterization of aggregates in answer set programming, Theory Pract. Log. Program., 7, 3, 355-375, (2007) · Zbl 1111.68072
[27] Faber, W.; Pfeifer, G.; Leone, N., Semantics and complexity of recursive aggregates in answer set programming, Artif. Intell., 175, 1, 278-298, (2011) · Zbl 1216.68263
[28] Gelfond, M., Representing knowledge in A-prolog, (Kakas, A. C.; Sadri, F., Computational Logic: Logic Programming and Beyond. Computational Logic: Logic Programming and Beyond, Essays in Honour of Robert A. Kowalski, Part II, vol. 2408, (2002), Springer Verlag: Springer Verlag Berlin), 413-451 · Zbl 1012.68545
[29] Kemp, D. B.; Stuckey, P. J., Semantics of logic programs with aggregates, (ISLP, vol. 91, (1991), Citeseer), 387-401
[30] Gelfond, M.; Zhang, Y., Vicious circle principle and logic programs with aggregates, Theory Pract. Log. Program., 14, 4-5, 587-601, (2014) · Zbl 1309.68032
[31] Gelfond, M.; Zhang, Y., Vicious circle principle and formation of sets in ASP based languages, (International Conference on Logic Programming and Nonmonotonic Reasoning, (2017), Springer), 146-159 · Zbl 06769658
[32] Mumick, I. S.; Pirahesh, H.; Ramakrishnan, R., The magic of duplicates and aggregates, (Proceedings of the 16th International Conference on Very Large Data Bases, (1990), Morgan Kaufmann Publishers Inc.), 264-277
[33] Ross, K. A.; Sagiv, Y., Monotonic aggregation in deductive database, J. Comput. Syst. Sci., 54, 1, 79-97, (1997) · Zbl 0869.68042
[34] Son, T. C.; Pontelli, E.; Elkabani, I., An unfolding-based semantics for logic programming with aggregates, CoRR
[35] Gelfond, M.; Przymusinska, H., On consistency and completeness of autoepistemic theories, Fundam. Inform., 16, 1, 59-92, (1992) · Zbl 0766.03017
[36] Lifschitz, V.; Turner, H., Splitting a logic program, (Proceedings of the 11th International Conference on Logic Programming (ICLP94), (1994)), 23-38
[37] Turner, H., Splitting a default theory, (Proceedings of AAAI-96, (1996)), 645-651
[38] Baral, C.; Gelfond, M., Logic programming and knowledge representation, J. Log. Program., 19, 20, 73-148, (1994) · Zbl 0820.68028
[39] Apt, K. R.; Blair, H. A.; Walker, A., Towards a theory of declarative knowledge, (Foundations of Deductive Databases and Logic Programming, (1988), Morgan Kaufmann), 89-148
[40] Alviano, M.; Faber, W., Stable model semantics of abstract dialectical frameworks revisited: a logic programming perspective, (Proceedings of the 21st International Joint Conference on Artificial Intelligence. IJCAI Organization. Proceedings of the 21st International Joint Conference on Artificial Intelligence. IJCAI Organization, Buenos Aires, Argentina, (2015)), 2684-2690
[41] Cabalar, P.; Fandinno, J.; Schaub, T.; Schellhorn, S., Gelfond-Zhang aggregates as propositional formulas, (International Conference on Logic Programming and Nonmonotonic Reasoning, (2017), Springer), 117-131 · Zbl 06769656
[42] Gelfond, M.; Zhang, Y., Vicious circle principle and logic programs with aggregates, preprint · Zbl 1309.68032
[43] Lifschitz, V.; Pearce, D.; Valverde, A., Strongly equivalent logic programs, ACM Trans. Comput. Log., 2, 4, 526-541, (2001) · Zbl 1365.68149
[44] Alviano, M.; Leone, N., Complexity and compilation of GZ-aggregates in answer set programming, Theory Pract. Log. Program., 15, 4-5, 574-587, (2015) · Zbl 1379.68035
[45] Son, T. C.; Pontelli, E.; Tu, P. H., Answer sets for logic programs with arbitrary abstract constraint atoms, J. Artif. Intell. Res., 29, 353-389, (2007) · Zbl 1182.68044
[46] Marek, V. W.; Truszczynski, M., Logic programs with abstract constraint atoms, (Proceedings of AAAI04, (2004)), 86-91
[47] Marek, V. W.; Remmel, J. B., Set constraints in logic programming, (Logic Programming and Nonmonotonic Reasoning, (2004), Springer), 167-179 · Zbl 1122.68381
[48] Shen, Y.; You, J.; Yuan, L., Characterizations of stable model semantics for logic programs with arbitrary constraint atoms, Theory Pract. Log. Program., 9, 4, 529-564, (2009) · Zbl 1177.68042
[49] Liu, G.; Goebel, R.; Janhunen, T.; Niemelä, I.; You, J.-H., Strong equivalence of logic programs with abstract constraint atoms, (Logic Programming and Nonmonotonic Reasoning, (2011), Springer), 161-173 · Zbl 1327.68067
[50] Faber, W.; Leone, N.; Pfeifer, G., Recursive aggregates in disjunctive logic programs: semantics and complexity, (Proceedings of the 8th European Conference on Artificial Intelligence (JELIA 2004), (2004)), 200-212 · Zbl 1111.68380
[51] Ferraris, P.; Lifschitz, V., Weight constraints as nested expressions, Theory Pract. Log. Program., 5, 1-2, 45-74, (2005) · Zbl 1093.68017
[52] Ferraris, P., Answer sets for propositional theories, (International Conference on Logic Programming and Nonmonotonic Reasoning, (2005), Springer), 119-131 · Zbl 1152.68408
[53] Ferraris, P., Logic programs with propositional connectives and aggregates, ACM Trans. Comput. Log., 12, 4, 25, (2011) · Zbl 1351.68053
[54] Bogaerts, B.; Vennekens, J.; Denecker, M., Grounded fixpoints and their applications in knowledge representation, Artif. Intell., 224, 51-71, (2015) · Zbl 1343.68233
[55] Lee, J.; Lifschitz, V.; Palla, R., A reductive semantics for counting and choice in answer set programming, (Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence. Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence, AAAI 2008, Chicago, Illinois, USA, July 13-17, 2008, (2008)), 472-479
[56] Lee, J.; Meng, Y., On reductive semantics of aggregates in answer set programming, (Logic Programming and Nonmonotonic Reasoning, (2009), Springer), 182-195 · Zbl 1258.68032
[57] 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) · Zbl 1207.68119
[58] Shen, Y.-D.; Wang, K.; Eiter, T.; Fink, M.; Redl, C.; Krennwallner, T.; Deng, J., FLP answer set semantics without circular justifications for general logic programs, Artif. Intell., 213, 1-41, (2014) · Zbl 1391.68016
[59] Gebser, M.; Harrison, A.; Kaminski, R.; Lifschitz, V.; Schaub, T., Abstract gringo, Theory Pract. Log. Program., 15, 4-5, 449-463, (2015) · Zbl 1379.68031
[60] Harrison, A.; Lifschitz, V., Relating two dialects of answer set programming, (Working Notes of the 17th International Workshop on Non-Monotonic Reasoning, (2018))
[61] Alviano, M.; Faber, W.; Gebser, M., Rewriting recursive aggregates in answer set programming: back to monotonicity, Theory Pract. Log. Program., 15, 4-5, 559-573, (2015) · Zbl 1379.68034
[62] F. Calimeri, W. Faber, M. Gebser, G. Ianni, R. Kaminski, T. Krennwallner, N. Leone, F. Ricca, T. Schaub, Asp-core-2: input language format, 2015.
[63] Feferman, S., Predicativity, (2002)
[64] Wirth, N., On the design of programming languages, (IFIP Congress, vol. 74, (1974)), 386-393
[65] Harrison, A. J.; Lifschitz, V.; Yang, F., The semantics of gringo and infinitary propositional formulas, (KR, (2014))
[66] Gebser, M.; Kaminski, R.; Kaufmann, B.; Lindauer, M.; Ostrowski, M.; Romero, J.; Schaub, T.; Thiele, S.; Wanko, P., Potassco User Guide, (2019), Institute for Informatics, University of Potsdam, Version 2.2.0
[67] Truszczynski, M., Connecting first-order ASP and the logic FO (ID) through reducts, (Correct Reasoning, (2012), Springer), 543-559 · Zbl 1357.68225
[68] Gelfond, M., New semantics for epistemic specifications, (Logic Programming and Nonmonotonic Reasoning, (2011), Springer), 260-265 · Zbl 1327.68249
[69] Alviano, M.; Leone, N., On the properties of GZ-aggregates in answer set programming, (IJCAI, (2016)), 4105-4109
[70] Strass, H., Approximating operators and semantics for abstract dialectical frameworks, Artif. Intell., 205, 39-70, (2013) · Zbl 1334.68212
[71] Li, C.; Wang, Y.; Feng, R.; Li, Q., Loop formulas for alog answer set programs, (Proceedings of the 2017 International Conference on Computer Science and Artificial Intelligence, (2017), ACM), 38-42
[72] Zhang, Y.; Rayatidamavandi, M., A characterization of the semantics of logic programs with aggregates, (IJCAI, (2016)), 1338-1344
[73] Lifschitz, V.; Tang, L. R.; Turner, H., Nested expressions in logic programs, Ann. Math. Artif. Intell., 25, 3-4, 369-389, (1999) · Zbl 0940.68075
[74] Cabalar, P.; Fandinno, J.; del Cerro, L. F.; Pearce, D., Functional ASP with intensional sets: application to Gelfond-Zhang aggregates, Theory Pract. Log. Program., 18, 3-4, 390-405, (2018) · Zbl 06988651
[75] Dovier, A.; Pontelli, E.; Rossi, G., Intensional sets in CLP, (Logic Programming, 19th International Conference, Proceedings. Logic Programming, 19th International Conference, Proceedings, ICLP 2003, Mumbai, India, December 9-13, 2003, (2003)), 284-299 · Zbl 1204.68051
[76] Erdogan, S. T.; Lifschitz, V., Definitions in answer set programming, (Lifschitz, V.; Niemelä, I., Proceedings of International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR), (2004)), 114-126 · Zbl 1121.68330
[77] Dantsin, E.; Eiter, T.; Gottlob, G.; Voronkov, A., Complexity and expressive power of logic programming, ACM Comput. Surv., 33, 3, 374-425, (2001)
[78] Eiter, T.; Gottlob, G., On the computational cost of disjunctive logic programming: propositional case, Ann. Math. Artif. Intell., 15, 3-4, 289-323, (1995) · Zbl 0858.68016
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.