Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-25T02:36:25.069Z Has data issue: false hasContentIssue false
  • English
  • Français

Splitting Epistemic Logic Programs

Published online by Cambridge University Press:  05 May 2020

PEDRO CABALAR ,
JORGE FANDINNO Open the ORCID record for JORGE FANDINNO [Opens in a new window]  and
LUIS FARIÑAS DEL CERRO
PEDRO CABALAR
Affiliation:
University of Corunna, Spain, (e-mail: [email protected])
JORGE FANDINNO
Affiliation:
Universität Potsdam, Germany (e-mail: [email protected])
LUIS FARIÑAS DEL CERRO
Affiliation:
IRIT, University of Toulouse, CNRS, France (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Epistemic logic programs constitute an extension of the stable model semantics to deal with new constructs called subjective literals. Informally speaking, a subjective literal allows checking whether some objective literal is true in all or some stable models. As it can be imagined, the associated semantics has proved to be non-trivial, since the truth of subjective literals may interfere with the set of stable models it is supposed to query. As a consequence, no clear agreement has been reached and different semantic proposals have been made in the literature. Unfortunately, comparison among these proposals has been limited to a study of their effect on individual examples, rather than identifying general properties to be checked. In this paper, we propose an extension of the well-known splitting property for logic programs to the epistemic case. We formally define when an arbitrary semantics satisfies the epistemic splitting property and examine some of the consequences that can be derived from that, including its relation to conformant planning and to epistemic constraints. Interestingly, we prove (through counterexamples) that most of the existing approaches fail to fulfill the epistemic splitting property, except the original semantics proposed by Gelfond 1991 and a recent proposal by the authors, called Founded Autoepistemic Equilibrium Logic.

Keywords

knowledge representation and nonmonotonic reasoninglogic programming methodology and applicationstheory
Type
Original Article
Information
Theory and Practice of Logic Programming , Volume 21 , Issue 3 , May 2021 , pp. 296 - 316
Check for updates
Copyright
© The Author(s), 2020. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

*

This is an extended version of a conference paper presented at the Fifteenth International Conference on Logic Programming and Nonmonotonic Reasoning, Philadelphia, PA, USA, June 3–7, 2019, where it received a best technical paper award (Cabalar et al. 2019b) An earlier version was also presented at the Seventeenth International Workshop on Non-monotonic Reasoning (Cabalar et al. 2018). This work was partially supported by MINECO, Spain, grant TIC2017-84453-P, Xunta de Galicia, Spain (GPC ED431B 2019/03). The second author was funded by the Centre International de Mathématiques et d’Informatique de Toulouse (CIMI) through contract ANR-11-LABEX-0040-CIMI within the program ANR-11-IDEX-0002-02 and the Alexander von Humboldt Foundation. We are thankful to Michael Gelfond, Richard Watson, Patrick T. Kahl, and the anonymous reviewers of the Seventeenth International Workshop on Non-monotonic Reasoning (NMR’18) and the Fifteenth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’19) where preliminary versions of this work were presented, for their comments and suggestions that have helped improving the paper substantially. We are also thankful to the organizers of LPNMR’19 for their support in preparing this extended version.

References

Balduccini, M., Lierler, Y. and Woltran, S., Eds. 2019. In Proceedings of the Fifteenth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’19). Lecture Notes in Artificial Intelligence, vol. 11481. Springer-Verlag.CrossRefGoogle Scholar
Cabalar, P., Fandinno, J. and Fariñas del Cerro, L. 2018. Splitting epistemic logic programs. InProceedings of the Seventeenth International Workshop on Non-monotonic Reasoning (NMR’18), 81–89.Google Scholar
Cabalar, P., Fandinno, J. and Fariñas del Cerro, L. 2019a. Founded world views with autoepistemic equilibrium logic. See Balduccini et al. (2019), 134–147.Google Scholar
Cabalar, P., Fandinno, J. and Fariñas del Cerro, L. 2019b. Splitting epistemic logic programs. See Balduccini et al. (2019), 120–133.Google Scholar
Fandinno, J. 2019. Founded (auto)epistemic equilibrium logic satisfies epistemic splitting. Theory and Practice of Logic Programming19, 5–6, 671–687.Google Scholar
Fariñas del Cerro, L., Herzig, A. and Iraz Su, E. 2015. Epistemic equilibrium logic. InProceedings of the Twenty-fourth International Joint Conference on Artificial Intelligence (IJCAI’15), Q. Yang and M. Wooldridge, Eds. AAAI Press, 2964–2970.Google Scholar
Gelfond, M. 1991. Strong introspection. In Proceedings of the Ninth National Conference on Artificial Intelligence (AAAI’91), T. Dean and K. McKeown, Eds. AAAI Press/The MIT Press, 386–391.Google Scholar
Gelfond, M. 2011. New semantics for epistemic specifications. In Proceedings of the Eleventh International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’11), J. Delgrande and W. Faber, Eds. Lecture Notes in Artificial Intelligence, vol. 6645. Springer-Verlag, 260–265.Google Scholar
Gelfond, M. and Lifschitz, V. 1988. The stable model semantics for logic programming. InProceedings of the Fifth International Conference and Symposium of Logic Programming (ICLP’88), R. Kowalski and K. Bowen, Eds. MIT Press, 1070–1080.Google Scholar
Gelfond, M. and Przymusinska, H. 1992. On consistency and completeness of autoepistemic theories. Fundamenta Informaticae 16, 1, 59–92.Google Scholar
Kahl, P.,Watson, R., Balai, E., Gelfond, M. and Zhang, Y. 2015. The language of epistemic specifications (refined) including a prototype solver. Journal of Logic and Computation. CrossRefGoogle Scholar
Lecrerc, A. and Kahl, P. 2018a. Epistemic logic programs with world view constraints. InTechnical Communications of the Thirty-Forth International Conference on Logic Programming (ICLP’18). Schloss Dagstuhl - Leibniz-Zentrum für Informatik.Google Scholar
Lecrerc, A. and Kahl, P. 2018b. A survey of advances in epistemic logic program solvers. InProceedings of the Eleventh International Workshop on Answer Set Programming and Other Computer Paradigms (ASPOCP’18).Google Scholar
Leone, N., Rullo, P. and Scarcello, F. 1997. Disjunctive stable models: Unfounded sets, fixpoint semantics, and computation. Information and Computation 135, 2, 69–112.Google Scholar
Lifschitz, V. and Turner, H. 1994. Splitting a logic program. InProceedings of the Eleventh International Conference on Logic Programming. MIT Press, 23–37.Google Scholar
Moore, R. 1985. Semantical considerations on nonmonotonic logic. Artificial Intelligence25, 75–94.Google Scholar
Pearce, D. 1997. A new logical characterisation of stable models and answer sets. InProceedings of the Sixth International Workshop on Non-Monotonic Extensions of Logic Programming (NMELP’96), J. Dix, L. Pereira and T. Przymusinski, Eds. Lecture Notes in Computer Science, vol. 1216. Springer-Verlag, 57–70.Google Scholar
Shen, Y. and Eiter, T. 2017. Evaluating epistemic negation in answer set programming (extended abstract). See Sierra (2017), 5060–5064.Google Scholar
Sierra, C., Ed. 2017. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI’17). IJCAI/AAAI Press.Google Scholar
Son, T., Le, T., Kahl, P. and Leclerc, A. 2017. On computing world views of epistemic logic programs. See Sierra (2017), 1269–1275.Google Scholar
Truszczyński, M. 2011. Revisiting epistemic specifications. InLogic Programming, Knowledge Representation, and Nonmonotonic Reasoning - Essays Dedicated to Michael Gelfond on the Occasion of His Sixty-Fifth Birthday, M. Balduccini and T. Son, Eds. Lecture Notes in Computer Science, vol. 6565. Springer, 315–333.Google Scholar
Wang, K. and Zhang, Y. 2005. Nested epistemic logic programs. InProceedings of the Eighth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’05), C. Baral, G. Greco, N. Leone, and G. Terracina, Eds. Lecture Notes in Artificial Intelligence, vol. 3662. Springer-Verlag, 279–290.Google Scholar
Watson, R. 2000. A splitting set theorem for epistemic specifications. In Proceedings of the Eighth International Workshop on Non-Monotonic Reasoning (NMR’00)cs.AI/0003038.Google Scholar