×

zbMATH — the first resource for mathematics

Forgetting auxiliary atoms in forks. (English) Zbl 07099243
Summary: In this work we tackle the problem of checking strong equivalence of logic programs that may contain local auxiliary atoms, to be removed from their stable models and to be forbidden in any external context. We call this property projective strong equivalence (PSE). It has been recently proved that not any logic program containing auxiliary atoms can be reformulated, under PSE, as another logic program or formula without them – this is known as strongly persistent forgetting. In this paper, we introduce a conservative extension of Equilibrium Logic and its monotonic basis, the logic of Here-and-There, in which we deal with a new connective ’|’ we call fork. We provide a semantic characterisation of PSE for forks and use it to show that, in this extension, it is always possible to forget auxiliary atoms under strong persistence. We further define when the obtained fork is representable as a regular formula.

MSC:
68T Artificial intelligence
Software:
CP-logic
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Baral, C., Knowledge Representation, Reasoning and Declarative Problem Solving, (2003), Cambridge University Press · Zbl 1056.68139
[2] Gebser, M.; Kaufmann, B.; Schaub, T., Conflict-driven answer set solving: from theory to practice, Artif. Intell., 187-188, 52-89, (2012) · Zbl 1251.68060
[3] 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
[4] Erdem, E.; Gelfond, M.; Leone, N., Applications of answer set programming, AI Mag., 37, 3, 53-68, (2016)
[5] Gelfond, M.; Lifschitz, V., The stable model semantics for logic programming, (Kowalski, R.; Bowen, K., Proceedings of the 19th International Conference and Symposium of Logic Programming (ICLP’88), (1988), MIT Press), 1070-1080
[6] Pearce, D., A new logical characterisation of stable models and answer sets, (Dix, J.; Pereira, L. M.; Przymusinski, T. C., Selected Papers from the Non-Monotonic Extensions of Logic Programming (NMELP’96). Selected Papers from the Non-Monotonic Extensions of Logic Programming (NMELP’96), Lecture Notes in Artificial Intelligence, vol. 1216, (1996), Springer-Verlag), 57-70
[7] Pearce, D., Equilibrium logic, Ann. Math. Artif. Intell., 47, 1-2, 3-41, (2006) · Zbl 1117.03039
[8] Ferraris, P.; Lee, J.; Lifschitz, V., A new perspective on stable models, (Sangal, R.; Mehta, H.; Bagga, R. K., Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI’07), (2007), Morgan Kaufmann Publishers Inc.), 372-379
[9] Harrison, A.; Lifschitz, V.; Truszczynski, M., On equivalence of infinitary formulas under the stable model semantics, Theory Pract. Log. Program., 15, 1, 18-34, (2015) · Zbl 1379.68070
[10] Gonçalves, R.; Knorr, M.; Leite, J., You can’t always forget what you want: on the limits of forgetting in answer set programming, (Kaminka, G. A.; Fox, M.; Bouquet, P.; Hüllermeier, E.; Dignum, V.; Dignum, F.; van Harmelen, F., Proceedings of 22nd European Conference on Artificial Intelligence (ECAI’16). Proceedings of 22nd European Conference on Artificial Intelligence (ECAI’16), Frontiers in Artificial Intelligence and Applications, vol. 285, (2016), IOS Press), 957-965 · Zbl 1403.68030
[11] Lifschitz, V.; Pearce, D.; Valverde, A., Strongly equivalent logic programs, ACM Trans. Comput. Log., 2, 4, 526-541, (2001) · Zbl 1365.68149
[12] Eiter, T.; Tompits, H.; Woltran, S., On solution correspondences in answer-set programming, (Kaelbling, L. P.; Saffiotti, A., Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence (IJCAI’05), (2005), Professional Book Center), 97-102
[13] Cabalar, P.; Pearce, D.; Valverde, A., Reducing propositional theories in equilibrium logic to logic programs, (Bento, C.; Cardoso, A.; Dias, G., Proceedings of the 12th Portuguese Conference on Progress in Artificial Intelligence (EPIA’05). Proceedings of the 12th Portuguese Conference on Progress in Artificial Intelligence (EPIA’05), Lecture Notes in Computer Science, vol. 3808, (2005), Springer), 4-17
[14] Cabalar, P.; Ferraris, P., Propositional theories are strongly equivalent to logic programs, Theory Pract. Log. Program., 7, 6, 745-759, (2007) · Zbl 1132.68321
[15] Cabalar, P.; Pearce, D.; Valverde, A., Minimal logic programs, (Dahl, V.; Niemelä, I., Proceedings of the 23rd International Conference on Logic Programming, (ICLP’07), (2007), Springer), 104-118 · Zbl 1213.68171
[16] Ferraris, P., Answer sets for propositional theories, (Baral, C.; Greco, G.; Leone, N.; Terracina, G., Proc. of the 8th Intl. Conf. on Logic Programming and Nonmonotonic Reasoning (LPNMR’05). Proc. of the 8th Intl. Conf. on Logic Programming and Nonmonotonic Reasoning (LPNMR’05), Lecture Notes in Computer Science, vol. 3662, (2005), Springer), 119-131 · Zbl 1152.68408
[17] Aguado, F.; Cabalar, P.; Pearce, D.; Pérez, G.; Vidal, C., A denotational semantics for equilibrium logic, Theory Pract. Log. Program., 15, 4-5, 620-634, (2015) · Zbl 1379.68032
[18] Pearce, D., Algebra matters in ASP and equilibrium logic, (Ojeda Aciego, M., Inma P. de Guzmán Festschrift (Liber Amicorum), (2010))
[19] Ben-Eliyahu, R.; Dechter, R., Propositional semantics for disjunctive logic programs, Ann. Math. Artif. Intell., 12, 1-2, 53-87, (1994) · Zbl 0858.68012
[20] Eiter, T.; Fink, M.; Woltran, S., Semantical characterizations and complexity of equivalences in answer set programming, ACM Trans. Comput. Log., 8, 3, 17, (2007) · Zbl 1367.68031
[21] Pearce, D.; Tompits, H.; Woltran, S., Characterising equilibrium logic and nested logic programs: reductions and complexity, Theory Pract. Log. Program., 9, 5, 565-616, (2009) · Zbl 1186.68100
[22] Leite, J., A Bird’s-eye view of forgetting in answer-set programming, (Balduccini, M.; Janhunen, T., Proc. of the 14th Intl. Conf. on Logic Programming and Nonmonotonic Reasoning (LPNMR’17). Proc. of the 14th Intl. Conf. on Logic Programming and Nonmonotonic Reasoning (LPNMR’17), Lecture Notes in Computer Science, vol. 10377, (2017), Springer), 10-22 · Zbl 06769646
[23] Knorr, M.; Alferes, J. J., Preserving strong equivalence while forgetting, (Fermé, E.; Leite, J., Logics in Artificial Intelligence - 14th European Conference, JELIA 2014, Funchal, Madeira, Portugal, September 24-26, 2014. Proceedings. Logics in Artificial Intelligence - 14th European Conference, JELIA 2014, Funchal, Madeira, Portugal, September 24-26, 2014. Proceedings, Lecture Notes in Computer Science, vol. 8761, (2014), Springer), 412-425 · Zbl 1432.68059
[24] Fink, M., A general framework for equivalences in answer-set programming by countermodels in the logic of here-and-there, Theory Pract. Log. Program., 11, 2-3, 171-202, (2011) · Zbl 1218.68070
[25] Vennekens, J.; Denecker, M.; Bruynooghe, M., CP-logic: a language of causal probabilistic events and its relation to logic programming, Theory Pract. Log. Program., 9, 3, 245-308, (2009) · Zbl 1179.68025
[26] Bochman, A., On disjunctive causal inference and indeterminism, (Proceedings of the Workshop on Nonmonotonic Reasoning, Actions and Change (NRAC’03), (2003)), 45-50
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.