Constraint Monotonicity, Epistemic Splitting
and Foundedness Can in General Be Too Strong
in Answer Set Programming^††thanks: This paper is presented at TAASP 2020: Workshop on Trends and Applications of Answer Set Programming.

In a seminal paper, Gelfond [8] introduced the notion of epistemic specifications which are disjunctive logic programs extended with two epistemic modal operators ${\bf K}$ and ${\bf M}$. Informally, for a formula $F$ and a collection $\cal A$ of interpretations, ${\bf K}F$ is true in $\cal A$ if $F$ is true in every $I\in{\cal A}$, and ${\bf M}F$ is true in $\cal A$ if $F$ is true in some $I\in{\cal A}$. An epistemic specification/program $\Pi$ consists of rules of the form

$$L_{1}\,\mid\cdots\mid\,L_{m}\leftarrow G_{1}\wedge\cdots\wedge G_{n}$$

(1)

where each $L$ is an object literal that is either an atom $A$ or its strong negation $\sim$$A$, and each $G$ is an object literal, a default negated literal of the form $\neg L$,¹¹1We use here $\neg$ for weak negation (alias default negation), as in early papers on logic programming. or a modal literal of the form ${\bf K}L$, $\neg{\bf K}L$, ${\bf M}L$ or $\neg{\bf M}L$. A rule (1) is called a constraint if its head is $\bot$, and called a subjective constraint if additionally each $G$ is a modal literal. $\Pi$ is a non-epistemic program (or an answer-set program) if it contains no modal literals.

Gelfond defined then the first answer set semantics for an epistemic program $\Pi$ as follows [8]. Given a collection $\cal A$ of interpretations as an assumption, $\Pi$ is transformed into a modal reduct $\Pi^{\cal A}$ w.r.t. $\cal A$ by first removing all rules with a modal literal $G$ that is not true in $\cal A$, then removing the remaining modal literals. The assumption $\cal A$ is defined to be a world view of $\Pi$ if it coincides with the collection of answer sets of $\Pi^{\cal A}$ under the GL-semantics defined in [7].

It turned out that the above semantics for epistemic programs has both the problem of unintended world views with recursion through K and the problem due to recursion through M [9, 12]. For the first problem, an illustrative example is $\Pi=\{p\leftarrow{\bf K}p\}$; under the above semantics $\Pi$ has two world views ${\cal A}_{1}=\{\emptyset\}$ and ${\cal A}_{2}=\{\{p\}\}$, where as commented in [9], ${\cal A}_{2}$ is undesired. For the second problem, a typical example is $\Pi=\{p\leftarrow{\bf M}p\}$; by the above semantics $\Pi$ has two world views ${\cal A}_{1}=\{\emptyset\}$ and ${\cal A}_{2}=\{\{p\}\}$, where as commented in [12], ${\cal A}_{1}$ may be undesired.

To address the two problems, several approaches have been proposed [12, 11, 4, 18]. In particular, Shen and Eiter[18] presented an approach that significantly differs from the others in the following three aspects.

1. (i)

   They introduced the modal operator $\mathbf{\mathop{not}\,}$ to directly express epistemic negation, where $\mathbf{\mathop{not}\,}F$ expresses that there is no evidence proving that $F$ is true. Modal formulas ${\bf K}F$ and ${\bf M}F$ are viewed as shorthands for $\neg\mathbf{\mathop{not}\,}F$ and $\mathbf{\mathop{not}\,}\neg F$, respectively.

2. (ii)

   Due to having the modal operator $\mathbf{\mathop{not}\,}$ to express epistemic negation, they further proposed to apply epistemic negation to minimize the knowledge in world views, a novel principle they named knowledge minimization with epistemic negation. It is based on the principle of knowledge minimization with epistemic negation that they presented a completely new definition of world views, which are free of both the problem with recursion through K and the problem through M.

3. (iii)

   Their approach is generic in the sense that it can be used to extend any of the existing answer set semantics for non-epistemic programs, such as those defined in [16, 17, 23, 5, 6, 20, 19], but also novel ones so they may be extended to an answer set semantics for epistemic programs.

Very recently, some researchers [10, 2, 3] introduced the notions of subjective constraint monotonicity, epistemic splitting, and foundedness for epistemic programs, aiming to use them as main criteria/intuitions to compare different answer set semantics proposed in the literature on how they comply with these intuitions. Specifically, they criticized the semantics defined in [12, 11, 4, 18], saying that these semantics do not satisfy the three properties.

In this note, we clarify the matter by demonstrating on some example programs that these three properties may be too strong and may exclude some desired answer sets/world views. Our conclusion is that for this reason these properties should not be used as mandatory properties that every answer set semantics must satisfy in general.

For the remainder of this note, we assume that the reader is familiar with non-monotonic logic programs in general and with answer set semantics for such programs in particular. We refrain here from providing formal definitions of answer sets and of world views of epistemic logic programs; for our concerns, it is sufficient to assume that the programs are formulated over a set $V$ of propositional atoms together with the special atoms $\top$ (truth) and $\bot$ (falsity). An answer set of an answer-set program $\Pi$ is an interpretation $I\subseteq V$ that satisfies respective conditions, where the standard definition is GL-semantics [7]. Similarly, a world view is a non-empty collection $\mathcal{A}\subseteq 2^{V}$ of interpretations that must satisfy respective conditions such as those in [8], which yield the G91-semantics for epistemic logic programs. Numerous further proposals for semantics have been made, cf. [9, 24, 12, 11, 4, 18, 10, 2, 3, 21, 15, 22].

A semantics for epistemic logic programs is said to satisfy subjective constraint monotonicity if for any epistemic program $\Pi$ and subjective constraint $C$, a world view of $\Pi\cup\{C\}$ is also a world view of $\Pi$; in other words, adding any constraint $C$ to $\Pi$ would never introduce new world views. The epistemic splitting property is even more restrictive in the sense that every semantics satisfying epistemic splitting also satisfies subjective constraint monotonicity, as has been shown in [2].

As a typical example, let $\Pi=\{p\mid q\}$, which has a unique world view $\{\{p\},\{q\}\}$. Then subjective constraint monotonicity requires that for any subjective constraint $C$, $\Pi\cup\{C\}$ should either have a unique world view $\{\{p\},\{q\}\}$ or have no world view. For example, under subjective constraint monotonicity the following program

	$\displaystyle\Pi_{1}:\quad$	$\displaystyle p\mid q$		($r_{1}$)
		$\displaystyle\bot\leftarrow\neg{\bf K}p$		($C$)

has no world view, as the only world view $\{\{p\},\{q\}\}$ of $\Pi=\{p\mid q\}$ is not a model of $\Pi_{1}$. Note that under the semantics of [12, 11, 4, 18], $\Pi_{1}$ has a world view ${\cal A}=\{\{p\}\}$. It is argued in [10, 2, 21] that $\{\{p\}\}$ should not be a world view of $\Pi_{1}$ because it violates subjective constraint monotonicity.

We comment that the requirement of constraint monotonicity (resp. epistemic splitting), i.e., adding constraints to a logic program should not introduce new answer sets/world views, may be too strong in general and may exclude some desired answer sets/world views, as demonstrated in the following examples.

1. 1.

   For a non-epistemic program $\Pi$, the GL-semantics [7] satisfies the constraint monotonicity property that adding a constraint $\bot\leftarrow body(r)$ to $\Pi$ may rule out some answer sets of $\Pi$, but would never introduce new answer sets [14]. However, very recent research [19] reveals that the GL-semantics may miss some desired answer sets that violate constraint monotonicity (see Section 4.1 in [19]). As an example, consider the following non-epistemic program:

   	$\displaystyle\Pi_{2}:\quad$	$\displaystyle a\mid b$		($r_{1}$)
   		$\displaystyle a\leftarrow b$		($r_{2}$)
   		$\displaystyle\bot\leftarrow\neg b$		($C$)

   where $C$ is a constraint. Intuitively, the rule $r_{1}$ presents two alternatives for answer set construction, namely $a$ or $b$, and the rule $r_{2}$ infers $a$ if $b$ has already been derived. We distinguish between the following two cases.

         First, suppose that we choose $a$ from $r_{1}$. As $b$ is not inferred from $r_{1}$, the rule $r_{2}$ is not applicable; so rules $r_{1}$ and $r_{2}$ together infer a possible answer set $I_{1}=\{a\}$. As $I_{1}$ does not satisfy the constraint $C$, it is not a candidate answer set for $\Pi_{2}$.

         Alternatively, suppose that we choose $b$ from $r_{1}$; then by $r_{2}$ we obtain a possible answer set $I_{2}=\{a,b\}$. $I_{2}$ satisfies the constraint $C$, so it is a candidate answer set for $\Pi_{2}$.

         As $I_{2}=\{a,b\}$ is the only model of $\Pi_{2}$, it is the only candidate answer set and thus we expect $I_{2}$ to be an answer set of $\Pi_{2}$. However, as $\Pi_{2}\setminus\{C\}$ has only one answer set $\{a\}$, this desired answer set $I_{2}$ for $\Pi_{2}$ violates the constraint monotonicity property.

2. 2.

   For epistemic programs, the requirement of subjective constraint monotonicity (resp. epistemic splitting) may also exclude some world views that are reasonably acceptable. As an example, consider the above program $\Pi_{1}$ again. As the rule $r_{1}=p\mid q$ offers two alternatives for answer set construction, namely $p$ or $q$, we can generate from $r_{1}$ two possible answer sets: $\{p\}$ and $\{q\}$. Then we can construct from the two possible answer sets three possible world views: ${\cal A}_{1}=\{\{p\}\}$, ${\cal A}_{2}=\{\{q\}\}$ and ${\cal A}_{3}=\{\{p\},\{q\}\}$. As ${\cal A}_{2}$ and ${\cal A}_{3}$ do not satisfy the constraint $\bot\leftarrow\neg{\bf K}p$, ${\cal A}_{1}$ is the only candidate world view and thus we expect it to be a world view of $\Pi_{1}$. However, this desired world view will be excluded if we enforce subjective constraint monotonicity.

3. 3.

   The above defined constraint monotonicity, which requires world views of $\Pi\cup\{C\}$ to be world views of $\Pi$ satisfying $C$, amounts in essence to interpreting the constraint $C$ as a query in the tradition of logic programming; that is, in order to answer a goal query $Q$ against a logic program $P$, we add the clause $\bot\leftarrow Q$ and then seek to derive $Q$. In the context of epistemic logic programs, where multiple world views are possible in general, we may view this as follows. Let $S$ be the collection of world views of $\Pi$. A query $C$ to $\Pi$ is to find in $S$ all world views that satisfy $C$. Note that query $C$ is not involved in the computation of any world view. This essentially differs from adding a constraint $C$ to $\Pi$, which aims to play a governing role in building the collection of world views of $\Pi\cup\{C\}$; due to that $C$ is directly involved in the computation of every world view, a world view of $\Pi\cup\{C\}$ is not necessarily a world view of $\Pi$.

The foundedness property is defined in [3], where a proposal for generalizing the notion of foundedness introduced in [13] for non-epistemic programs to epistemic programs has been made. The GL-semantics [7] for non-epistemic programs also has the foundedness property. We use examples to demonstrate that the foundedness requirement is too strong and may exclude some desired answer sets/world views. For simplicity, we do not reproduce the definition of foundedness here; the reader is referred to [3].

1. 1.

   Consider again the non-epistemic program $\Pi_{2}$ from above. Note that for the construction of an answer set, the rule $r_{1}$ provides two alternatives, $a$ or $b$, for us to choose. Let $b$ be selected from $r_{1}$. Then once $b$ is established in $r_{1}$, $a$ is well-supported and thus derived from $r_{2}$. This leads to a possible answer set $I=\{a,b\}$. As $I$ satisfies the constraint $C$, it is a candidate answer set for $\Pi_{2}$. As $I$ is the only model of $\Pi_{2}$, it is the only candidate answer set for $\Pi_{2}$ and thus is a desired answer set of $\Pi_{2}$. However, this desired answer set violates the foundedness property. (It is easy to check that $\langle\{b\},I\rangle$ is an unfounded set.)

2. 2.

   Consider the following epistemic program:

   	$\displaystyle\Pi_{3}:\quad$	$\displaystyle p\mid q$		($r_{1}$)
   		$\displaystyle p\leftarrow{\bf K}q$		($r_{2}$)
   		$\displaystyle q\leftarrow{\bf K}p$		($r_{3}$)
   		$\displaystyle\bot\leftarrow\neg{\bf K}p$		($C$)

   As $p\mid q$ offers two alternatives for answer set construction, namely $p$ or $q$, we can generate from $r_{1}$ two possible answer sets: $\{p,\cdots\}$ and $\{q,\cdots\}$, where “$\cdots$” stands for possible atoms that would be derived from the rules $r_{2}$ and $r_{3}$. Then we can construct from the two possible answer sets three possible world views: ${\cal A}_{1}=\{\{p,\cdots\}\}$, ${\cal A}_{2}=\{\{q,\cdots\}\}$, and ${\cal A}_{3}=\{\{p,\cdots\},\{q,\cdots\}\}=\{\{p\},\{q\}\}$. Note that the two answer sets in ${\cal A}_{3}$ must be different and no one is a proper subset of the other. We distinguish among the following three cases.

         First, suppose that we choose ${\cal A}_{1}=\{\{p,\cdots\}\}$. Note that $p$ in ${\cal A}_{1}$ is established in $r_{1}$. Then, as ${\cal A}_{1}$ satisfies ${\bf K}p$, $q$ is well-supported in $r_{3}$ and thus ${\cal A}_{1}=\{\{p,q\}\}$. ${\cal A}_{1}$ also satisfies $r_{2}$ and $C$, so it is a candidate world view for $\Pi_{3}$.

         Second, suppose that we choose ${\cal A}_{2}=\{\{q,\cdots\}\}$. Note that $q$ in ${\cal A}_{2}$ is established in $r_{1}$. Then, as ${\cal A}_{2}$ satisfies ${\bf K}q$, $p$ is well-supported in $r_{2}$ and thus ${\cal A}_{2}=\{\{p,q\}\}$. ${\cal A}_{2}$ satisfies $r_{3}$ and $C$, so it is further shown that $\{\{p,q\}\}$ is a candidate world view for $\Pi_{3}$.

         Finally, suppose that we choose ${\cal A}_{3}=\{\{p\},\{q\}\}$. ${\cal A}_{3}$ does not satisfy $C$, so it is not a candidate world view for $\Pi_{3}$.

         Consequently, $\{\{p,q\}\}$ is the only candidate world view for $\Pi_{3}$, so we may expect it to be a world view of $\Pi_{3}$. However, this desired world view violates the foundedness property. (It is easy to check that $[\langle\{p\},\{p,q\}\rangle,\langle\{q\},\{p,q\}\rangle]$ is an unfounded set.)

The above examples demonstrate that the properties of subjective constraint monotonicity, epistemic splitting and foundedness are too strong and may exclude some desired answer sets/world views. It was specifically emphasized in [9, 12, 18] that the focus of research on answer set semantics for epistemic programs is how to handle the two basic problems:

1. 1.

   The problem of unintended world views caused by recursion through K;

2. 2.

   The problem of unintended world views caused due to recursion through M.

In fact, by introducing the epistemic negation operator $\mathbf{\mathop{not}\,}$ and applying the principle of knowledge minimization with epistemic negation, Shen and Eiter [18] has presented a principled way to handle the two problems. For example, the desired answer sets respectively world views of the above programs $\Pi_{1}-\Pi_{3}$ can all be obtained by applying the general semantics of Definition 8 in [18], where the base answer set semantics ${\cal X}$ for a non-epistemic program is the one according to Definition 10 in [19]. This is not to say, however, that the Shen-Eiter approach in [18] is superior to the others. Similar as for the extension of answer-set program with aggregates (cf. [1] for a brief survey), there is a spectrum of possibilities with a range of properties and features. We believe that like for that extension, understanding the landscape of diverse approaches for answer set semantics of epistemic logic programs is a valuable goal, and that properties of universal validity may need comprehensive examinations.

We thank the anonymous reviewers from the TAASP 2020 workshop for their helpful comments. This work has been supported in part by NSFC grants 61976205 and 61379043, the Austrian Science Fund (FWF) grant W1255, and the EU grant HumanE-AI-Net (ICT-48-2020-RIA 952026).