On the Splitting Property for Epistemic Logic Programs (Extended Abstract)

Pedro Cabalar, Jorge Fandinno, Luis Fariñas del CerroIJCAI 2020 · DOI

TL;DR

This paper introduces and formalizes an "epistemic splitting property" for epistemic logic programs, a powerful extension of logic programming that allows reasoning about knowledge and belief. This property provides a principled way to decompose complex epistemic programs, ensuring that certain semantic approaches behave intuitively and consistently, especially for stratified programs.

What Problem Does This Paper Address?

Traditional logic programming, particularly Answer Set Programming (ASP), excels at reasoning with incomplete information. However, real-world reasoning often requires introspection – thinking about what we know or believe. Epistemic logic programs extend ASP with modal operators (like "K" for "knows") that quantify over the stable models (possible worlds) of a program. This allows for sophisticated reasoning about knowledge.

The challenge arises when these epistemic operators are used within the rules of the program itself. This can lead to "cyclic reasoning," where the definition of a stable model depends on queries about stable models, potentially resulting in multiple, sometimes unintuitive, sets of solutions called "world views." The literature has seen various attempts to define semantics that handle these cycles gracefully, but there's been a lack of a unifying principle to evaluate their behavior, especially for simpler, non-cyclic cases. This paper addresses this by proposing the "epistemic splitting property" as a fundamental requirement for a well-behaved epistemic semantics.

Methods

The core contribution is the formalization of the epistemic splitting property. This property is inspired by the well-established "splitting theorem" in standard logic programming. The idea is to divide an epistemic logic program into two parts: a "bottom" part and a "top" part. The key constraint is that the top part can only refer to atoms in the bottom part through epistemic operators (e.g., K or M).

A semantics satisfies epistemic splitting if, for any program that can be split this way, its world views can be obtained by:

  1. Computing the world views of the bottom part.
  2. For each world view of the bottom part, simplifying the top part by replacing the epistemic literals with their truth values according to that bottom world view.
  3. Computing the world views of the simplified top part.
  4. Combining the world views from the bottom and top parts.

The paper also defines "epistemic stratification" as a condition under which epistemic splitting guarantees a unique world view, mirroring a similar concept in standard logic programming.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Bridging the Gap: The epistemic splitting property acts as a bridge, connecting the well-understood behavior of standard logic programs to the more complex world of epistemic logic programs. It ensures that even with epistemic operators, programs that can be decomposed in a specific way should behave predictably.
  • Intuitive Behavior for Stratified Programs: A significant consequence is that if an epistemic logic program is "epistemically stratified" (meaning there are no cyclic dependencies among subjective literals), then any semantics satisfying epistemic splitting will yield at most one world view. This aligns with our intuition that such programs should have a clear, unambiguous outcome.
  • Subjective Constraints: The property also ensures that "subjective constraints" (rules consisting only of subjective literals) behave monotonically. This means they simply rule out candidate world views that don't satisfy the constraint, rather than introducing complex interactions.
  • Evaluating Semantics: The paper uses this property to evaluate existing epistemic semantics, highlighting which ones adhere to this fundamental principle of decomposition and intuitive behavior.

Key Results

  • The paper formally defines the epistemic splitting property and provides a method for decomposing epistemic logic programs.
  • It proves that if a program is epistemically stratified, any semantics satisfying epistemic splitting will produce at most one world view.
  • It demonstrates that epistemic splitting implies subjective constraint monotonicity.
  • A table summarizes which of the discussed epistemic semantics satisfy the epistemic splitting property, showing that only a subset of them do.

Limitations and Future Work

  • Extended Abstract: This is an extended abstract, meaning some proofs and details are omitted. The full details are available in a separate publication.
  • Focus on a Specific Property: While epistemic splitting is a crucial property, it's one among several that might be desirable for epistemic semantics. The paper acknowledges that semantics satisfying this property might also satisfy stronger notions of splitting.
  • Future Work: The authors suggest that this property can facilitate the application of the "generate-define-test" methodology for formalizing conformant planning, indicating a direction for future research. They also point to further details in their related work.

Summary updated

BibTeX
@inproceedings{cabalar2020splitting,
  author = {Pedro Cabalar and Jorge Fandinno and Luis Fariñas del Cerro},
  title = {{On the Splitting Property for Epistemic Logic Programs (Extended Abstract)}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/653},
}
Figure