# Epistemic Logic Programs:
a study of some properties ††thanks: Research partially performed within the
activities of the Action COST CA17124 “DigForASP”, the Interdepartmental
Project on AI (Strategic Plan UniUD–22-25), and the INdAM-GNCS project CUP
E53C22001930001.

Stefania Costantini
DISIM - Università dell’Aquila  via Vetoio  L’Aquila  Italy
Gruppo Nazionale per il Calcolo Scientifico - INdAM  Roma  Italy
<EMAIL_ADDRESS>Andrea Formisano
DMIF - Università di Udine  via delle Scienze 206  Udine  Italy
Gruppo Nazionale per il Calcolo Scientifico - INdAM  Roma  Italy
<EMAIL_ADDRESS>
###### Abstract

Epistemic Logic Programs (ELPs), extend Answer Set Programming (ASP) with
epistemic operators. The semantics of such programs is provided in terms of
_world views_ , which are sets of belief sets, i.e., syntactically, sets of
sets of atoms. Different semantic approaches propose different
characterizations of world views. Recent work has introduced semantic
properties that should be met by any semantics for ELPs, like the _Epistemic
Splitting Property_ , that, if satisfied, allows to modularly compute world
views in a bottom-up fashion, analogously to “traditional” ASP. We analyze the
possibility of changing the perspective, shifting from a bottom-up to a top-
down approach to splitting. We propose a basic top-down approach, which we
prove to be equivalent to the bottom-up one. We then propose an extended
approach, where our new definition: (i) is provably applicable to many of the
existing semantics; (ii) operates similarly to “traditional” ASP; (iii)
provably coincides under any semantics with the bottom-up notion of splitting
at least on the class of _Epistemically Stratified Programs_ (which are,
intuitively, those where the use of epistemic operators is stratified); (iv)
better adheres to common ASP programming methodology.

Under consideration in Theory and Practice of Logic Programming (TPLP)

###### keywords:

Answer Set Programming, Epistemic Logic Programs, Epistemic Splitting

##  1 Introduction

Epistemic Logic programs (ELPs, in the following just _programs_ , if not
explicitly stated differently), were first introduced in [Gelfond and
Przymusinska (1991), Gelfond (1994)], and extend Answer Set Programs, defined
under the Answer Set Semantics [Gelfond and Lifschitz (1988)], with _epistemic
operators_ that are able to introspectively “look inside” a program’s own
semantics, which is defined in terms of its _answer sets_ (cf. [Fandinno et
al. (2022)] for a historical review of research on this topic). In fact,
$\mbox{{K}}A$ means that (ground) atom $A$ is true in every answer set of the
program $\Pi$ where $\mbox{{K}}A$ occurs. Related operators that can be
defined in terms of K are the _possibility operator_ M (not treated in this
paper) where $\mbox{{M}}A$ means that $A$ is true in some of the answer sets
of $\Pi$, and the _epistemic negation operator_ not  , where
$\mbox{{not\,}}\,A$ expresses that $A$ _is not provably true_ , meaning that
$A$ is false in at least one answer set of $\Pi$.

The semantics of ELPs is provided in terms of _world views_ : instead of a
unique set of answer sets (a unique “world view” in the new terminology) like
in Answer Set Programming (ASP), there is now a set of such sets. Each world
view consistently satisfies (according to a given semantics) the epistemic
expressions that appear in a given program. Many semantic approaches for ELPs
have been introduced beyond the seminal work of Gelfond and Przymusinska
[Gelfond and Przymusinska (1991)], among which we mention [Gelfond (2011),
Truszczynski (2011), Fariñas del Cerro et al. (2015), Shen and Eiter (2016),
Kahl and Leclerc (2018), Su (2019), Cabalar et al. (2019), Costantini and
Formisano (2022), Su (2021)].

Recent work extends to Epistemic Logic Programming notions that have already
been defined for ASP, and that might prove useful in ELPs as well. In
particular, Cabalar et al. consider _splitting_ (introduced for ASP in
[Lifschitz and Turner (1994)]), which allows a program to be seen as divided
(“split”) into two parts, the “top” and “bottom” in a principled way, i.e.,
atoms occurring in the bottom can occur only in the body of rules in the top.
This allows the answer sets of the program to be computed incrementally, in
the following way: compute the answer sets of the bottom part, and use them
(one by one) to simplify the top part; then, compute the answer sets of the
simplified top part; finally, the answer sets of the overall program are
obtained as the union of each answer set of the bottom with the corresponding
answer sets of the simplified top (such a procedure can be iterated, i.e., the
top and the bottom could in turn be split). Cabalar et al. then extend to ELPs
the concept of splitting and the method of incremental calculation of the
semantics (here, it is the world views that must be calculated). This is
achieved by defining a notion of _Epistemic Splitting_ , where top and bottom
are defined with respect to the occurrence of epistemic operators, and a
corresponding _Epistemic Splitting Property_ , which is fulfilled by a
semantics if it allows the world views to be computed bottom-up (a precise
definition is seen below). Further, Cabalar et al. adapt properties of ASP to
ELPs, which are implied by this property, namely, the fact that adding
constraints leads to reduce the number of answer sets (_Subjective Constraint
Monotonicity_), and _Foundedness_ , meaning that atoms composing answer sets
cannot have been derived through cyclic positive dependencies. Finally, they
define the class of _Epistemically Stratified Programs_ that, according to
[Cabalar et al. (2021), Th. 2], admit a unique world view (these programs are
those where, intuitively, the use of epistemic operators is stratified). In
substance, Cabalar et al. establish the properties that in their view a
semantics should fulfill, and then they compare the existing semantics with
respect to these properties.

In this paper, we explore a different stance: we analyze the possibility of
changing the perspective about how to exploit a splitting, shifting from a
bottom-up to a top-down approach. This applies in the first place to the
Epistemic Splitting Property, of which we propose a reformulation allowing
world views to be computed top-down. We then propose a substantial extension
of the Epistemic Splitting Property, leading to a new approach that:

  * (i)

is applicable to many of the existing semantics, while few of them fulfill the
Epistemic Splitting Property as originally formulated;

  * (ii)

operates similarly to splitting in “traditional” ASP;

  * (iii)

provably coincides under any semantics with the bottom-up notion of splitting
on a significant class of programs, including at least those which are
_epistemically stratified_ ;

  * (iv)

is compatible with common ASP programming practice, where one defines a
problem solution (that would constitute the top) that will be merged with a
problem instance (that would constitute the bottom).

The paper is organized as follows. In Sections 2 and 3 we recall ASP and ELPs.
Section 4 reports some definitions from [Cabalar et al. (2021)] concerning
useful properties of ELPs. In Section 5 we introduce some observations on ELPs
that lead to formulate our proposal, treated in detail in Section 6. In
Section 7 we state our main theorem and a relevant corollary. Finally, in
Section 8 we conclude.

##  2 Answer Set Programming and Answer Set Semantics

One can see an answer set program (for short, ASP program) as a set of
statements that specify a problem, where each answer set represents a solution
compatible with this specification. A _consistent_ ASP program has one or more
answer sets, while an _inconsistent_ one has no answer sets, meaning that no
solution can be found. Several well-developed freely available _answer set
solvers_ exist that compute the answer sets of a given program. Syntactically,
an ASP program $\Pi$ is a collection of _rules_ of the form

$A_{1}|\ldots|A_{g}\leftarrow\;L_{1},\ldots,L_{n}.$

where each $A_{i}$, $0\leq i\leq g$, is an atom and $|$ indicates disjunction,
and the $L_{i}$s, $0\leq i\leq n$, are literals (i.e., atoms or negated atoms
of the form $not\,\,A$). The left-hand side and the right-hand side of the
rule are called _head_ and _body_ , respectively.

A rule with an empty body is called a _fact_. As usual, the symbols $\top$ and
$\bot$ denote the true and the false Boolean constants, respectively. The
notation $A\,|\,B$ indicates disjunction, usable only in rule heads and, so,
in facts.

A rule with an empty head (or, equivalently, with head $\bot$), of the form
$\leftarrow L_{1},...,L_{n}.$ or $\bot\leftarrow L_{1},...,L_{n}.$ , is a
_constraint_ , stating that literals $L_{1},\ldots,L_{n}$ are not allowed to
be simultaneously true in any answer set; the impossibility of fulfilling such
kind of requirement is one of the reasons that makes a program inconsistent.

All extensions of ASP not explicitly mentioned above are not considered in
this paper. We implicitly refer to the _ground_ version of $\Pi$, which is
obtained by replacing in all possible ways the variables occurring in $\Pi$
with the constants occurring in $\Pi$ itself, and is thus composed of ground
atoms, i.e., atoms that contain no variables.

The _answer set_ (or _stable model_) semantics can be defined in several ways
[Lifschitz (2010), Costantini and Formisano (2015)]. However, answer sets of a
program $\Pi$, if any exists, are the supported minimal classical models of
the program interpreted as a first-order theory in an obvious way. The
original definition from [Gelfond and Lifschitz (1988)], introduced for
programs where rule heads were limited to be single atoms, was in terms of the
_GL-Operator_ $\Gamma$. Given set of atoms $I$ and program $\Pi$,
$\Gamma_{\Pi}(I)$ is defined as the least Herbrand model of the program
$\Pi^{I}$, namely, the Gelfond-Lifschitz reduct of $\Pi$ w.r.t. $I$. The
program $\Pi^{I}$ is obtained from $\Pi$ by:

  * 1.

removing all rules which contain a negative literal $not\,{}A$ such that $A\in
I$; and

  * 2.

removing all negative literals from the remaining rules.

Since $\Pi^{I}$ is a positive program, the least Herbrand model is guaranteed
to exist and can be computed via the standard immediate consequence operator
[Lloyd (1987)]. Then, $I$ is an answer set whenever $\Gamma_{\Pi}(I)=I$.

This definition is then extended to the general case, involving disjunctive
heads, by defining $I$ to be an answer set of $\Pi$ if it is a minimal model
(w.r.t. set inclusion) of $\Pi^{I}$.

##  3 Epistemic Logic Programs

Epistemic Logic Programs (ELPs) extend the syntax of ASP programs by
introducing, in the body of rules, so-called _subjective literals_ (w.r.t. the
usual  _objective literals_).111Nesting of subjective literals is not
considered here. Such new literals are constructed via the _epistemic
operator_ K (disregarding without loss of generality the other epistemic
operators). An ELP program is called _objective_ if no subjective literals
occur therein, i.e., it is an ASP program. A constraint involving (also)
subjective literals is called a _subjective constraint_ , whereas one
involving objective literals only is an _objective constraint_.

Let $At$ be the set of atoms occurring (within either objective or subjective
literals) in a given program $\Pi$, and $\mathit{Atoms}(r)$ be the set of
atoms occurring in rule $r$. By some abuse of notation, we denote by
$\mathit{Atoms}(X)$ the set of atoms occurring in $X$, whatever $X$ is (a
rule, a program, an expression, etc.). Let $\mathit{Head}(r)$ be the head of
rule $r$ and $\mathit{Body_{obj}}(r)$ (resp., $\mathit{Body_{subj}}(r)$) be
the (possibly empty) set of objective (resp., subjective) literals occurring
in the body of $r$. For simplicity, we often write $\mathit{Head}(r)$ and
$\mathit{Body_{obj}}(r)$ in place of $\mathit{Atoms}(\mathit{Head}(r))$ and
$\mathit{Atoms}(\mathit{Body_{obj}}(r))$, respectively, when the intended
meaning is clear from the context. We call _subjective rules_ those rules
whose body is made of subjective literals only.

Literal $\mbox{{K}}A$ intuitively means that the (ground) atom $A$ is true in
every answer set of the given program $\Pi$ (it is a _cautious consequence_ of
$\Pi$). Since, as it turns out, whatever the semantic account one will choose
there can be several sets of answer sets (called _world views_), the actual
meaning of $\mbox{{K}}A$ is that $A$ is true in every answer set of some world
view of $\Pi$. Each world view thus determines the truth value of all
subjective literals in a program. There are several semantic approaches to
ELPs, dictating in different ways how one finds the world views of a given
program. Although all such approaches provide the same results in a set of
basic examples, they (obviously) differ in others.

Formally, a semantics $\cal{S}$ is a function mapping an ELP program into sets
of world views, i.e., sets of sets of objective literals, where if $\Pi$ is an
objective program, then the unique member of ${\cal{S}}(\Pi)$ is the set of
stable models of $\Pi$. Otherwise, each member of ${\cal{S}}(\Pi)$ is an
_${\cal{S}}$ -world view_ of $\Pi$. (We will often write “world view” in place
of “${\cal{S}}$-world view” whenever mentioning the specific semantics will be
irrelevant.) For an ${\cal{S}}$-world view $W$ and a literal $\mbox{{K}}L$, we
write $W\models\mbox{{K}}L$ if $L$ is true in all elements of $W$.

For instance, for program
$\\{a{\,\leftarrow\,}not\,b,~{}b{\,\leftarrow\,}not\,a,~{}e{\,\leftarrow\,}not\,\mbox{{K}}f,~{}f{\,\leftarrow\,}not\,\mbox{{K}}e\\}$,
every semantics returns two world views: $\\{\\{a,e\\},\\{b,e\\}\\}$, where
$\mbox{{K}}e$ is true and $\mbox{{K}}f$ is false, and
$\\{\\{a,f\\},\\{b,f\\}\\}$ where $\mbox{{K}}f$ is true and $\mbox{{K}}e$ is
false. The presence of two answer sets in each world view is due to the cycle
on objective atoms, whereas the presence of two world views is due to the
cycle on subjective atoms (in general, the existence and number of world views
are related to such cycles, see [Costantini (2019)] for a detailed
discussion).

##  4 Epistemic Logic Programs: Useful Properties

As argued by Cabalar et al., it would be useful if ELPs would enjoy, _mutatis
mutandis_ , properties similar to those of ASP programs. Hence, in their
works, such useful properties are outlined and adapted, as we report (almost
literally) below.

Drawing inspiration from the _Splitting Theorem_ [Lifschitz and Turner
(1994)], an analogous property is defined for ELPs:

######  Definition 4.1 (Epistemic splitting set [Cabalar et al. (2021), Def.
4])

A set of atoms $U\subseteq At$ is said to be an epistemic splitting set of a
program $\Pi$ if for any rule $r$ in $\Pi$ one of the following conditions
hold:

  1. 1.

$\mathit{Atoms}(r)\subseteq U$;

  2. 2.

$(\mathit{Body_{obj}}(r)\cup\mathit{Head}(r))\ \cap\ U=\emptyset$.

An epistemic splitting of $\Pi$ is a pair $\langle
B_{U}(\Pi),T_{U}(\Pi)\rangle$ such that $B_{U}(\Pi)\cap T_{U}(\Pi)=\emptyset$
and $B_{U}(\Pi)\cup T_{U}(\Pi)=\Pi$, and also, such that all rules in
$B_{U}(\Pi)$ satisfy condition (1) and all rules in $T_{U}(\Pi)$ satisfy
condition (2).

Intuitively, condition (2) means that the top program $T_{U}(\Pi)$ may refer
to atoms in $U$ which occur as heads of rules in the bottom $B_{U}(\Pi)$, only
through epistemic operators.

Epistemic splitting can be used, similarly to “traditional” Lifschitz&Turner
splitting, for iterative computation of world views. Indeed, Cabalar et al.
2021 propose to compute first the world views of the bottom program
$B_{U}(\Pi)$ and, for each of them, simplify the corresponding subjective
literals in the top part. Given an epistemic splitting set $U$ for $\Pi$ and a
set of interpretations $W$, they define the subjective reduct of the top with
respect to $W$ and signature $U$, denoted by $E_{U}(\Pi,W)$. This operator
considers all subjective literals $L$ occurring in $T_{U}(\Pi)$, such that the
atoms occurring in them belong to $B_{U}(\Pi)$. In particular, $L$ will be
substituted by $\top$ in $E_{U}(\Pi,W)$ if $W\models L$, and by $\bot$
otherwise. Thus, $E_{U}(\Pi,W)$ is a version of $T_{U}(\Pi)$ where some
subjective literal, namely those referring to the bottom part of the program,
have been simplified as illustrated.

######  Definition 4.2 ((Cabalar et al., 2021, Def. 5))

Given a semantics $\cal{S}$, a pair $\langle W_{b},W_{t}\rangle$ is said to be
an $\cal{S}$-solution of $\Pi$ with respect to an epistemic splitting set $U$
if $W_{b}$ is an $\cal{S}$-world view of $B_{U}(\Pi)$ and $W_{t}$ is an
$\cal{S}$-world view of $E_{U}(\Pi,W_{b})$.

The definition is parametric w.r.t. $\cal{S}$, as each different semantics
$\cal{S}$ will define in its own way the $\cal{S}$-solutions for a given $U$
and $\Pi$.

###### Definition 4.3

The WBT operation $W_{b}\sqcup W_{t}$ on sets of propositional interpretations
$W_{b}$ and $W_{t}$ is defined as follows:

$W_{b}\sqcup W_{t}=\\{I_{b}\cup I_{t}|I_{b}\in W_{b}\wedge I_{t}\in W_{t}\\}.$

We report from Cabalar et al. (2021) the definition of the following property:

######  Property 4.1 (Epistemic Splitting Property (ESP))

A semantics $\cal{S}$ satisfies the epistemic splitting property if for any
epistemic splitting set $U$ of any program $\Pi$: $W$ is an $\cal{S}$-world
view of $\Pi$ iff there is an $\cal{S}$-solution $\langle W_{b},W_{t}\rangle$
of $\Pi$ w.r.t. $U$ such that $W=W_{b}\sqcup W_{t}$.

Then, under a semantics that satisfies ESP, world views of the entire program
are obtainable as the union of world views of the bottom with world views of a
simplified version of the top. The Epistemic Splitting Property implies
_Subjective Constraint Monotonicity_ , i.e., for any epistemic program $\Pi$
and any subjective constraint $r$, $W$ is a world view of $\Pi\cup\\{r\\}$ iff
both $W$ is a world view of $\Pi$ and $W$ satisfies $r$.

As discussed in Cabalar et al. (2021), many semantics do not satisfy the ESP
property, which is in fact satisfied only by the very first semantics of ELPs,
proposed in Gelfond and Przymusinska (1991) and thus called G91 (and in some
of its generalizations), and by Founded Autoepistemic Equilibrium Logic
(FAEEL), defined in Cabalar et al. (2019).

Another interesting property is _foundedness_. Again, such a notion has been
extended from objective programs (see (Cabalar et al., 2021, Def. 15)).
Intuitively, a set $X$ of atoms is _unfounded_ w.r.t. an (objective) program
$\Pi$ and an interpretation $I$, if for every $A\in X$ there is no rule $r$ in
$\Pi$ by which $A$ might be derived, without incurring in positive
circularities and without forcing the derivation of more than one atom from
the head of a disjunctive rule (see, e.g., Leone et al. (1997) for a formal
definition). For ELPs, one has to consider that unfoundedness can originate
also from positive dependencies on positive subjective literals, like, e.g.,
in the program $A\leftarrow\mbox{{K}}A$. Among the existing semantics, only
FAEEL satisfies foundedness.

An interesting class of programs admitting a unique world view is
characterized by the following definition.

######  Definition 4.4 (Epistemic Stratification (Cabalar et al., 2021, Def.
6))

We say that an ELP $\Pi$ is epistemically stratified if we can assign an
integer mapping $\lambda:At\rightarrow N$ to each atom (occurring in the
program) such that:

  * •

$\lambda(a)=\lambda(b)$ for any rule $r\in\Pi$ and atoms
$a,b\in(\mathit{Atoms}(r)\setminus\mathit{Body_{subj}}(r))$, and

  * •

$\lambda(a)>\lambda(b)$ for any pair of atoms $a,b$ for which there exists a
rule $r\in\Pi$ with $a\in(\mathit{Head(r)}\cup\mathit{Body_{obj}}(r))$ and
$b\in\mathit{Body_{subj}}(r)$.

##  5 Observations

The subdivision of an ELP into layers suggests that, in the upper layer,
epistemic literals referring to the lower layer may be aimed at performing
some kind of meta-reasoning about that layer. If the epistemic splitting
property is enforced, however, meta-level reasoning is in practice prevented.
This is so because if the semantics satisfies such property, then, it is the
lower layer that determines the truth value of the subjective literals that
connect the two layers. In fact, according to Property 4.1, through the
simplification w.r.t. the answer sets of the lower layer, the upper layer is
strongly (maybe sometimes too strongly) constrained.

For instance, let us consider the program $\Pi_{0}=\\{a\,|\,b,\
\bot\leftarrow{not\,}\mbox{{K}}a\\}$. We can see that, while the lower level
$\\{a\,|\,b\\}$, considered as a program _per se_ , has the unique world view
$\\{\\{a\\},\\{b\\}\\}$, the overall program has no world views. In fact,
$\mbox{{K}}a$ does not hold in $\\{\\{a\\},\\{b\\}\\}$, thus the constraint is
violated.

Notice, however, that the world view $\\{\\{a\\}\\}$ is instead accepted by
some semantics, such as those defined in Gelfond (2011) and in Shen and Eiter
(2016), that do not satisfy the epistemic splitting property. This world view
may be seen as corresponding to an approach where the upper layer, in order to
retain consistency, “requires” the lower layer to entail $a$, which is
absolutely feasible by choosing $a$ over $b$ in the disjunction.

From this perspective, the knowledge modeled by the upper layer is not just
used to reject potential world views of the bottom level, but, instead, can
affect the way in which they are composed, by filtering out some of the answer
sets. This situation is reminiscent of what actually happens for ASP: consider
the plain ASP program $\\{a\,|\,b,\ c\leftarrow a,\ \leftarrow{not\,}c\\}$,
which has unique answer set $\\{a,c\\}$, originating from the answer set
$\\{a\\}$ of the lower layer $\\{a\,|\,b\\}$.

We follow (for a long time) the line, amply represented in the literature, in
which meta-reasoning is aimed not only at “observing” lower layer(s) but also
at trying to influence them (cf. Costantini (2002) for a survey on meta-
reasoning in Computational Logic); this by suitably enlarging and/or
restricting, as an effect of meta-rules application, the set of possible
consequences of such layer(s). We discuss at length this point of view, also
proposing technical solutions and several examples, in Costantini and
Formisano (2021).

In addition, let us notice that a common approach in logical declarative
modeling of a problem consists of formalizing the problem domain as the “top”
part of a program/theory. Then, such top part will be joined with a specific
“bottom”, representing the problem instance at hand, that may vary and might
be, in general, unknown while defining the top.

Below is an example of what we mean (over-simplified and in “skeletal form”
for the sake of conciseness), taken from the realm of digital investigations,
that the authors have been studying in the context of the Action COST CA17124
DIGital FORensics: evidence Analysis via intelligent Systems and Practices
(DigForASP). In the example, an investigation must be concluded with a
judgment, that can be:

  * •

of innocence if in no plausible scenario (i.e., in no answer set) evidence can
be found of an involvement;

  * •

of demonstrable guilt if in every possible scenario, the evidence of guilt can
be found;

  * •

of presumed innocence otherwise.

Clearly, the specification of the legal rules that can be used to draw
conclusions, and then the details of each specific case will be modularly
added whenever needed to this general “top” part. Thus, one can see a program
composed of three layers: the top, and a bottom that can be further split into
a middle layer containing legal rules, and the lowest layer with details of
the case (see Costantini (2019) for more examples taken from this field).

The top layer is as follows:

$~{}~{}\begin{array}[]{l}\mathit{judgement}\leftarrow\mathit{guilty}.\\\
\mathit{judgement}\leftarrow\mathit{presumed\\_innocent}.\\\
\mathit{judgement}\leftarrow\mathit{innocent}.\\\ \leftarrow not\ \mbox{{K}}\
\mathit{judgement}.\\\ \mathit{guilty}\leftarrow\mathit{provably\\_guilty}.\\\
\mathit{presumed\\_innocent}\leftarrow not\,\mathit{provably\\_guilty}.\\\
\mathit{provably\\_guilty}\leftarrow\mbox{{K}}\
\mathit{sufficient\\_evidence\\_against}.\\\
\mathit{innocent}\leftarrow\mbox{{K}}\
not\,\mathit{sufficient\\_evidence\\_against}.\end{array}$

Hence, a study of how the semantics of any resulting overall program might be
built is in order here, as in many other practical cases: think, for example,
of a top part comprising ontological definitions reusable in several
application contexts. In fact, being able to compute and check a program’s
semantics only in dependence on each specific instance, does not seem to be
elaboration-tolerant.

Therefore, we tried to understand whether the concept of splitting might be
applied top-down, and how the existing semantics would behave in the new
perspective.

##  6 Our Proposal

Let us proceed step by step towards the new definition of _Top-down Epistemic
Splitting Property_. We first reformulate definitions related to ESP so that
it can be applied also top-down, to obtain what we call Top-down Epistemic
Splitting Property - Basic (TDESPB), showing that a semantics satisfies TDESPB
if and only if it satisfies ESP. Thus, TDESPB provides a way of coping with
incremental computation of world views more suitable to the examples mentioned
earlier. We then perform some extensions, to obtain a more general Top-down
Epistemic Splitting Property (TDESP) that holds for a wider range of semantic
approaches.

###  6.1 Preliminaries and Key Definitions

In our approach, the notion of splitting set remains the same, save for some
details concerning subjective constraints. We need, in fact, to introduce
preliminary assumptions on constraints. Notice that subjective literals may
either occur in a subjective constraint directly or affect constraint’s
satisfaction through indirect dependencies, such as, e.g., in the program
$\bot\leftarrow a.\ a\leftarrow\mbox{{K}}p$ (see Dix (1995) for a formal
definition of direct and indirect dependencies). Without loss of generality,
we exclude here indirect dependencies concerning subjective literals involved
in constraints. Also, notice that, as it is well-known, a constraint can be
represented as a unary odd cycle, that, e.g., for $\bot\leftarrow\mbox{{K}}p$
would be of the form $a\leftarrow not\,a,\mbox{{K}}p$ (with $a$ introduced as
a fresh atom), or even (as discussed in depth in Costantini (2006)) as an odd
cycle of any arity, of which $\mbox{{K}}p$ is the unique _handle_. For the
sake of simplicity, we consider subjective constraints in their plain form,
namely, as in $\bot\leftarrow\mbox{{K}}p$. Notice also that, according to the
definition of splitting provided in Cabalar et al. (2021), subjective
constraints can be placed at either of two adjacent levels. For convenience
concerning definitions that will be introduced later, we impose, again without
loss of generality, that both subjective rules satisfying condition (2) of the
definition of Epistemic Splitting Set (Definition 4.1) and subjective
constraints are put in $T_{U}(\Pi)$.

We now proceed to introduce the key definitions on which our approach is
based.

###### Definition 6.1

Let be given a semantics $\cal{S}$, a program $\Pi$, and an epistemic
splitting $\langle B_{U}(\Pi),T_{U}(\Pi)\rangle$ of $\Pi$, according to the
definition of Epistemic Splitting Set. Let $F_{U}(\Pi)$ denote the set of all
subjective literals $\mbox{{K}}L$ occurring in $T_{U}(\Pi)$ (even in negative
form $not\,\mbox{{K}}L$) and referring to $B_{U}(\Pi)$ (in the sense that the
atom involved in $\mbox{{K}}L$ occurs in $B_{U}(\Pi)$ but not in
$T_{U}(\Pi)$), together with their negations $not\,\mbox{{K}}L$.

Intuitively, subjective literals in $F_{U}(\Pi)$ constitute the “interface”
between the top and bottom parts. Notice that
$\mathit{Atoms}(F_{U}(\Pi))\subseteq U$.

###### Definition 6.2

Let $\Pi$ be a program and let
$F_{U}(\Pi)=\\{\mbox{{K}}L_{1},\ldots,\mbox{{K}}L_{z},not\,\mbox{{K}}L_{1},\ldots,not\,\mbox{{K}}L_{z}\\}$.
Let, moreover, $f_{U}(\Pi)=\\{kl_{1},\ldots,kl_{z},nkl_{1},\ldots,nkl_{z}\\}$
be a set of fresh atoms. The _detached version_ $T^{\prime}_{U}(\Pi)$ of
$T_{U}(\Pi)$ is the program consisting of:

  * •

the rules obtained from rules in $T_{U}(\Pi)$ by substituting each occurrence
of the subjective literal $\mbox{{K}}L_{i}\in F_{U}(\Pi)$ or
$not\,\mbox{{K}}L_{i}\in F_{U}(\Pi)$ by the corresponding fresh atom
$kl_{i}\in f_{U}(\Pi)$ or $nkl_{i}\in f_{U}(\Pi)$, for each
$i\in\\{1,\ldots,z\\}$ (where $kl_{i}$ and $nkl_{i}$ are in turn called the
_detached form_ of $\mbox{{K}}L_{i}$ and $not\,\mbox{{K}}L_{i}$, resp.); and

  * •

the facts $kl_{i}\ |\ nkl_{i}$, for each $i\in\\{1,\ldots,z\\}$.

We introduced $T^{\prime}_{U}(\Pi)$ in order to model the connection between
$T_{U}(\Pi)$ and $B_{U}(\Pi)$ w.r.t. the top-down perspective. Thus, we need
to define the notion of _world views of the detached version
$T^{\prime}_{U}(\Pi)$ of a program_ under the assumption that the fresh atoms
$kl_{i}$ and $nkl_{i}$ represent the epistemic literals connecting the top and
bottom parts of the program. As seen below, these world views not necessarily
coincide with the world views of $T^{\prime}_{U}(\Pi)$ if considered as an
epistemic program by itself.

Recall that a disjunction between an epistemic literal $\mbox{{K}}L$ and its
negation $not\,\mbox{{K}}L$ determines, as discussed in Costantini (2019), two
world views, one entailing $\mbox{{K}}L$ and the other one entailing
$not\,\mbox{{K}}L$. With respect to the subjective literals in $F_{U}(\Pi)$,
in defining the detached version $T^{\prime}_{U}(\Pi)$ of a program
$T_{U}(\Pi)$ we encoded the potential existence of such alternative world
views by means of the disjunctions $kl_{i}\ |\ nkl_{i}$, for
$i\in\\{1,\ldots,z\\}$.

In computing the world views of the detached version $T^{\prime}_{U}(\Pi)$, we
start by considering $T^{\prime}_{U}(\Pi)$ as a regular epistemic program
(forgetting for the moment that the fresh atoms $kl_{i}$ and $nkl_{i}$ stand
for epistemic literals) thus obtaining the corresponding collection of world
views $\mathcal{W}$. Note in fact that $T^{\prime}_{U}(\Pi)$ does not contain
subjective literals referring to the bottom $B_{U}(\Pi)$, but it may contain
“local” epistemic literals that may determine the existence of several world
views (or just one if there are no such local epistemic literals). The answer
sets in each $W\in\mathcal{W}$ might however contain some of the atoms
$kl_{i}$s and $nkl_{i}$s. In this case, each $W\in\mathcal{W}$ has to be split
into two world views, say $W_{1}$ and $W_{2}$, the former composed of the
answer sets in $W$ that contain $kl_{1}$, and the latter composed by those
answer sets of $W$ that contain $nkl_{1}$. This step must be repeated by
considering the pair $kl_{2}$/$nkl_{2}$ in order to split both $W_{1}$ and
$W_{2}$, and so on, for each $i\in\\{1,\ldots,z\\}$. (Observe that the order
of splits does not matter.) We consider the resulting collection of sets of
atoms as the world views of the detached version $T^{\prime}_{U}(\Pi)$. An
example of this process will be given at the end of Section 6.2. In summary:

######  Definition 6.3 (World views of $T^{\prime}_{U}(\Pi)$, or Interface
World Views)

Let $W^{1},\ldots,W^{n}$ be the world views of $T^{\prime}_{U}(\Pi)$ according
to a given semantics $\cal{S}$. The Interface World Views of
$T^{\prime}_{U}(\Pi)$ are obtained as follows: for every $W^{j}$, $j\leq n$,
$W^{j}=\\{S^{j}_{1},\ldots,S^{j}_{v}\\}$ for some $v\geq 0$, and for every
disjunction $kl_{i}\ |\ nkl_{i}$, $i\in\\{1,\ldots,z\\}$ occurring in
$T^{\prime}_{U}(\Pi)$, split $W^{j}$ into $W^{j}_{1}$ and $W^{j}_{2}$, the
former composed of the sets $S^{j}_{h}\in W^{j}$ such that $kl_{i}\in
S^{j}_{h}$, the latter composed of the of the sets $S^{j}_{f}\in W^{j}$ such
that $nkl_{i}\in S^{j}_{f}$, $f\in\\{1,\ldots,v\\}$. Repeat the splitting over
the resulting world views, and iterate the process until splitting is no
longer possible, i.e., no resulting world view contains both $kl_{r}$ and
$nkl_{r}$, for some $r\in\\{1,\ldots,z\\}$.

The denomination “Interface World Views” indicates that they have been
obtained in the perspective of a merge with world views of the bottom, as seen
below. For the sake of conciseness though by some abuse of notation, we will
call Interface World Views simply ‘world views’.

###### Proposition 6.1

There exists a bijection between world views of $T_{U}(\Pi)$ and world views
of $T^{\prime}_{U}(\Pi)$.

######  Proof 6.1.

Given a world view (Interface World View, to be precise) $W^{\prime}_{j}$ of
the epistemic program $T^{\prime}_{U}(\Pi)$, a world view $W_{j}$ for
$T_{U}(\Pi)$ is equal to $W_{j}=\\{X\setminus f_{U}(\Pi)\,|\,X\in
W^{\prime}_{j}\\}$. In fact, the procedure for obtaining Interface World Views
takes into account the fact that each epistemic literal represented by an atom
in $f_{U}(\Pi)$ can be potentially either true or false. Vice versa,
$W^{\prime}_{j}$ is obtained from $W_{j}$ by adding to it some subset of
$f_{U}(\Pi)$.

For each of such world views $W_{j}$ of $T_{U}(\Pi)$, Def. 6.2 below
identifies the set of subjective literals that are relevant in extending
$W_{j}$ to a world view of the entire $\Pi$. These are those that in the
detached version of $T_{U}(\Pi)$ have been assumed to be true to obtain
$W_{j}$ as a world view.

######  Definition 6.2 (Epistemic Top-down Requisite Set).

Let $\langle B_{U}(\Pi),T_{U}(\Pi)\rangle$ be an epistemic splitting for a
program $\Pi$, $W^{\prime}_{j}$ be a world view of $T^{\prime}_{U}(\Pi)$, and
let $W_{j}=\\{X\setminus f_{U}(\Pi)\,|\,X\in W^{\prime}_{j}\\}$.

The set $ES_{T_{U}(\Pi)}(W_{j})=\\{\mbox{{K}}L_{h}\,|\,W^{\prime}_{j}\models
kl_{h}\\}\cup\\{not\,\mbox{{K}}L_{h}\,|\,W^{\prime}_{j}\not\models kl_{h}\\}$
is the _(epistemic top-down) requisite set_ for $W_{j}$ (w.r.t. $\langle
B_{U}(\Pi),T_{U}(\Pi)\rangle$).

Now we partition the _requisite set_ , identifying two relevant subsets
(technical reasons for doing so will be seen below).

######  Definition 6.3.

Given $f_{U}(\Pi)=\\{kl_{1},\ldots,kl_{z},nkl_{1},$ $\ldots,nkl_{z}\\}$ and
the above definition of requisite set $ES_{T_{U}(\Pi)}(W_{j})$, w.r.t. an
epistemic splitting $\langle B_{U}(\Pi),T_{U}(\Pi)\rangle$, let set $S$
include those $kl_{i}/nkl_{i}$ that occur in some constraints in
$T^{\prime}_{U}(\Pi)$.
We split the requisite set $ES_{T_{U}(\Pi)}(W_{j})$ as the union of the
following two (disjoint) sets:

  * •

the _epistemic top-down constraint set_ :

$EC_{T_{U}(\Pi)}(W_{j})=(\\{\mbox{{K}}L_{i}\ |kl_{i}\in
S\\}\cup\\{not\,\mbox{{K}}L_{i}\ |nkl_{i}\in S\\})\cap ES_{T_{U}(\Pi)}(W_{j})$

  * •

the _requirement set_ :

$RQ_{T_{U}(\Pi)}(W_{j})=\big{(}\\{\mbox{{K}}L_{i}\ |kl_{i}\in
f_{U}(\Pi){\setminus}S\\}\cup\\{not\,\mbox{{K}}L_{i}\ |nkl_{i}\in
f_{U}(\Pi){\setminus}S\\}\big{)}\cap ES_{T_{U}(\Pi)}(W_{j}).$

There is an important reason for distinguishing these two subsets. Namely, the
literals in $EC_{T_{U}(\Pi)}(W_{j})$, if not entailed in some world view of
the bottom part of the program, lead to a constraint violation and cause the
non-existence of world views of $\Pi$ extending $W_{j}$. Thus,
$EC_{T_{U}(\Pi)}(W_{j})$ expresses prerequisites on which epistemic literals
must be entailed in a world view of $B_{U}(\Pi)$, so that such world view can
be merged with $W_{j}$ in order to obtain a world view of $\Pi$. Instead,
literals in $RQ_{T_{U}(\Pi)}(W_{j})$, can be usefully exploited, as seen
below, to drive the selection of which world view of the bottom can be
combined with a given world view of the top.

For all the three sets (requisite set, constraint set, and requirement set)
one can possibly list only the epistemic literals of $F_{U}(\Pi)$ required to
be true, all the others implicitly required to be false.

Given a world view $W$ of $T_{U}(\Pi)$ and considering literals belonging to
$EC_{T_{U}(\Pi)}(W)$ which occur in the bodies of rules in $B_{U}(\Pi)$, we
introduce a simplification that can be performed and will turn out to be
useful later on.

######  Definition 6.4 (Top-down Influence).

Given a world view $W$ of $T_{U}(\Pi)$, and its corresponding top-down
constraint set $EC_{T_{U}(\Pi)}(W)$, the $W$-tailored version $B_{U}^{W}(\Pi)$
of $B_{U}(\Pi)$ is obtained by substituting in $B_{U}(\Pi)$ all literals
$\mbox{{K}}L\in EC_{T_{U}(\Pi)}(W)$ by $L$.

The intuition behind the above definition is that, if $\mbox{{K}}A$ is in
$EC_{T_{U}(\Pi)}(W)$, then $A$ must necessarily belong to every answer set of
a world view of the bottom that can be possibly merged with $W$ in order to
obtain a world view of the overall program $\Pi$. Hence, it is indifferent
that in the body of rules of $B_{U}(\Pi)$ it occurs $A$ rather than
$\mbox{{K}}A$, if $\mbox{{K}}A\in EC_{T_{U}(\Pi)}(W)$. Substituting
$\mbox{{K}}A$ with $A$ can, however, be useful, as discovered during the
development of the G11 Gelfond (2011) and K15 semantics Kahl et al. (2015), to
“break” unwanted positive cycles among subjective literals, that might lead to
_unfounded_ world views (cf. (Cabalar et al., 2021, Def. 15)).

In our approach, the notion of top-down influence provides, as seen by
examples in the next section, an alternative perspective on how a world view
of the bottom is obtained, and, in a sense, a re-interpretation of the notion
of foundedness (to be formally elaborated in future work).

In the top-down approach that we are going to propose, the world views of a
given program $\Pi$ are obtained as a combination of world views of the top
and world views of the bottom, like in the bottom-up approach. In the basic
version of the Top-down Epistemic Splitting Property, presented in Section
6.2, there is only a change of perspective and a simple condition to drive the
combination via the WBT operation (cf. Definition 4.3).

In the definition of the more general Top-down Epistemic Splitting Property,
presented in Section 6.3, one can notice two relevant changes: (i) the notion
of top-down influence is exploited in the definition of candidate world views;
(ii) a subset of a world view of the bottom (i.e., some of the answer sets
occurring therein) may be cut out, so as to enable the merging via WBT with a
“compatible” world view of the top.

Preliminarily:

######  Definition 6.5.

Given a set $E$ of epistemic literals and a set of sets of atoms $W$, we say
that $W$ _fulfills_ $E$ iff $\forall\,\mbox{{K}}L\in E,W\models L$ and
$\forall\,not\,\mbox{{K}}L\in E,W\not\models L$.

###  6.2 Top-down Epistemic Splitting Property - Basic (TDESPB)

######  Definition 6.6 (Candidate World View - Basic Version).

Given an epistemic splitting $\langle B_{U}(\Pi),T_{U}(\Pi)\rangle$ for a
program $\Pi$, let $W_{T}$ be a world view of $T_{U}(\Pi)$ and let $W_{B}$ be
a world view of $B_{U}(\Pi)$ that fulfills $EC_{T_{U}(\Pi)}(W_{T})$ such that
$W_{B}$ also fulfills $RQ_{T_{U}(\Pi)}(W_{T})$ (overall, $W_{B}$ fulfills the
requisite set $ES_{T_{U}(\Pi)}(W_{T})$). Then,

$W=W_{B}\sqcup W_{T}=\\{I_{b}\cup I_{t}|I_{b}\in W_{B}\wedge I_{t}\in
W_{T}\\}$

is a _candidate world view_ for $\Pi$ (obtained from $W_{T}$ and $W_{B}$).

It is possible that no world views of the bottom comply with the conditions
posed by world views of the top: in such case, $\Pi$ has no candidate world
views.

We can now state a property that, if satisfied by a semantics, allows world
views to be computed top-down:

######  Definition 6.7 (Top-down Epistemic Splitting Property - Basic Version
(TDESPB)).

A semantics $\cal{S}$ satisfies _basic top-down epistemic splitting_ if any
candidate world view of $\Pi$ according to Definition 6.6 is indeed a world
view of $\Pi$ under $\cal{S}$.

Below we show that TDESPB is equivalent to the Epistemic Splitting Property by
Cabalar et al. (2021), in the sense that both definitions are satisfied by the
same semantic approaches and thus characterize the same world views.

######  Theorem 6.8 (Equivalence ESP - TDESPB).

A semantics $\cal{S}$ satisfies TDESPB if and only if $\cal{S}$ satisfies the
Epistemic Splitting Property ESP as defined in Definition 4.1.

######  Proof 6.9.

_If part._ Assume that a given semantics $\cal{S}$ satisfies TDESPB. To show
that $\cal{S}$ satisfies ESP as well, it suffices to observe that the couple
$\langle W_{B},W_{T}\rangle$ according to Definition 6.6 is a
$\cal{S}$-solution as required by the definition of ESP. In fact, $W_{B}$ is
an $\cal{S}$-world view of the bottom $B_{U}(\Pi)$. It remains to be seen that
$W_{T}$ is an $\cal{S}$-world view of $E_{U}(\Pi,W_{B})$, i.e., that, after
simplifying $T_{U}(\Pi)$ w.r.t. the subjective literals entailed by $W_{B}$,
one would have $W_{T}$ among the world views. By Definition 6.6, $W_{B}$
fulfills the requisite set $ES_{T_{U}(\Pi)}(W_{T})$, leading $W_{B}\sqcup
W_{T}$ to be a world view of the overall program. This means, according to
Definition 6.2, that $W_{B}$ entails all the subjective literals of the form
$\mbox{{K}}A$ and $not\,\mbox{{K}}A$, that, in the detached version of
$T_{U}(\Pi)$ (Definition 6.2) have been assumed to be true (in their detached
form) in order to obtain $W_{T}$ as a world view (according to $\cal{S}$).
Thus, if one would simplify $T_{U}(\Pi)$ into $E_{U}(\Pi,W_{B})$ by
considering exactly those subjective literals as true and all the others as
false, one would trivially obtain $W_{T}$ as the world view of
$E_{U}(\Pi,W_{B})$.

_Only if part._ Assume that a given semantics $\cal{S}$ satisfies ESP. This
means that there exists a $\cal{S}$-solution $\langle W_{B},W_{T}\rangle$
that, via WBT, gives rise to the world views of the program. To be an
$\cal{S}$-solution, $W_{B}$ must be a world view of the bottom, and $W_{T}$ a
world view of $E_{U}(\Pi,W_{B})$, i.e., of the top simplified w.r.t. $W_{B}$.
To find the correspondence with TDESPB, we have to ascertain that $\langle
W_{B},W_{T}\rangle$ gives rise to candidate world views in the sense of
Definition 6.6. To do so, we put into $ES_{T_{U}(\Pi)}(W_{T})$ the subjective
literals, among those entailed by $W_{B}$, that are employed to perform such
simplification, so as to exactly fulfill the conditions posed in Definition
6.2.

The equivalence stated by Theorem 6.8 implies that the world views of a
program can be determined by composing the world views of the various layers
into which the program can be split, by proceeding either bottom-up, according
to the original definition, or top-down, according to our new definition. We
will now illustrate the approach, and its similarities and differences w.r.t.
ASP, by means of an example.

Consider the following sample ASP program.

$\begin{array}[]{ll}f\leftarrow a.\\\ e\leftarrow c.\\\ \bot\leftarrow
not\,p.\\\ a\leftarrow p.\\\ a\leftarrow q.\\\ p\leftarrow not\,q.\\\
q\leftarrow not\,p.\\\ c.\end{array}$

A possible split according to Lifschitz & Turner can be:

$\begin{array}[]{ll}\mathit{Top\ part}\\\ f\leftarrow a.\\\ e\leftarrow c.\\\
\bot\leftarrow not\,p.\\\ \\\ \mathit{Bottom\ part}\\\ a\leftarrow p.\\\
a\leftarrow q.\\\ p\leftarrow not\,q.\\\ q\leftarrow not\,p.\\\ c.\end{array}$

Notice that the unique answer set of this program is $S=\\{c,p,a,e,f\\}$. The
answer sets of the bottom part are: $S1=\\{c,p,a\\}$, $S2=\\{c,q,a\\}$. The
answer set of the top part, assuming $p$ true (otherwise the constraint is
violated), is $S3?=\\{e?,f?\\}$, the question mark meaning that any of the two
atoms can be true, according to the selected answer set of the bottom. In this
simple case, we have to choose $S2$, which makes $p$ true, and, by imagining
adding atoms in $S2$ as new facts in the top part, we get both $e$ and $f$,
thus obtaining the answer set $S$. Let us now consider the top part as a
standalone program:

$\begin{array}[]{ll}f\leftarrow a.\\\ e\leftarrow c.\\\ \bot\leftarrow
not\,p.\end{array}$

This program in itself is inconsistent, but knowing that it is intended as the
top part of a wider program, we can set the requirements for any bottom part,
in the form of what we can call _Epistemic top-down Constraint set_
$EC=\\{p\\}$, i.e., $p$ must be true in an answer set of the bottom, for the
top to be consistent. If we enrich the top as follows:

$\begin{array}[]{ll}f\leftarrow a.\\\ e\leftarrow c.\\\ \bot\leftarrow
not\,p.\\\ \\\ p\ |\ nop.\\\ a\ |\ noa.\\\ c\ |\ noc.\end{array}$

We can compute all possible answer sets for the top part, by simulating
possible values for atoms coming from the (still unknown) bottom. Each such
simulation, e.g., assuming $a$ true and $c$ false, gives rise to a _Requisite
Set_ $RQ$. Then, given a specific bottom program that one intends to add to
the top, each answer set $M$ of the bottom that fulfills $EC$ can be combined
with all the answer sets of the top that are compatible, in the sense that $M$
entails all literals in the corresponding $RQ$.

Let us now consider an ELP with a very similar structure.

$\begin{array}[]{ll}\mathit{Top\ part}\\\ f\leftarrow\mbox{{K}}a.\\\
e\leftarrow\mbox{{K}}c.\\\ \bot\leftarrow not\,\mbox{{K}}p\\\ \\\
\mathit{Bottom\ part}\\\ a\leftarrow p.\\\ a\leftarrow q.\\\ p\leftarrow
not\,\mbox{{K}}q.\\\ q\leftarrow not\,\mbox{{K}}p.\\\ c.\end{array}$

Let us first proceed bottom-up, as dictated by the ESP definition. The world
views of the bottom, according to any existing semantics, are:
$W1=\\{\\{c,p,a\\}\\}$, $W2=\\{\\{c,q,a\\}\\}$.

Below is the top part simplified w.r.t. $W1$, with a unique resulting world
view $\\{\\{e,f\\}\\}$.

$\begin{array}[]{ll}f.\\\ e.\end{array}$

The top part simplified w.r.t. $W2$ is reported below, with no world views as
the constraint is violated:

$\begin{array}[]{ll}\mathit{Top\ part\ w.r.t.\ W2}\\\ f.\\\ e.\\\
\bot\leftarrow\top\end{array}$

Therefore, the unique world view of the overall program is, by the WBT
operation which reduces here to a simple union, $W=\\{\\{c,p,a,e,f\\}\\}$.

Let us now apply the notions related to the top-down splitting property TDESPB
that we presented above. We have the following detached version of the top
part:

$\begin{array}[]{ll}f\leftarrow ka.\\\ e\leftarrow kc.\\\ \bot\leftarrow
nkp\\\ ka\ |\ nka.\\\ kc\ |\ nkc.\\\ kp\ |\ nkp.\\\ \end{array}$

Seen as an epistemic program by itself, this program has a unique world view
(indeed, it is a standard ASP program), which is

$\\{\\{kp,nka,nkc\\},~{}\\{kp,ka,nkc,f\\},~{}\\{kp,nka,kc,e\\},~{}\\{kp,ka,kc,e,f\\}\\}.$

By splitting this set of sets three times (w.r.t. the pairs $ka/nka$,
$kc/nkc$, and $kp/nkp$) as described in Section 6.1, Definition 6.3, we obtain
the world views of the detached version: $\\{\\{kp,nka,nkc\\}\\}$,
$\\{\\{kp,nka,kc,e\\}\\}$, $\\{\\{kp,ka,nkc,f\\}\\}$, and
$\\{\\{kp,ka,kc,e,f\\}\\}$.

From them, one determines the _epistemic top-down constraint set_ which is,
clearly, $EC=\\{\mbox{{K}}p\\}$, stating that the unique constraint must be
satisfied. Any compatible world view of a bottom should satisfy one of the
$RQ^{i}$’s, $i\leq 4$, i.e., the requirement sets, listed below (cf.
Definitions 6.2 and 6.3). To each $RQ^{i}$ it corresponds a world view of the
top (indicated on the right) to be united to those world views of the bottom
that satisfy $RQ^{i}$ (if any).

$\begin{array}[]{ll}RQ^{1}=\emptyset,&\mathit{determines}\hskip
22.76219ptW_{t}^{1}=\\{\emptyset\\}\\\
RQ^{2}=\\{\mbox{{K}}c\\},&\mathit{determines}\hskip
22.76219ptW_{t}^{2}=\\{\\{e\\}\\}\\\
RQ^{3}=\\{\mbox{{K}}a\\},&\mathit{determines}\hskip
22.76219ptW_{t}^{3}=\\{\\{f\\}\\}\\\
RQ^{4}=\\{\mbox{{K}}c,\mbox{{K}}a\\},&\mathit{determines}\hskip
22.76219ptW_{t}^{4}=\\{\\{e,f\\}\\}\end{array}$

Given the world views of the bottom, i.e., $W1=\\{\\{c,p,a\\}\\}$,
$W2=\\{\\{c,q,a\\}\\}$, we can see that $W2$ does not fulfill $EC$ and so must
be discarded, while $W1$ fulfills $EC$ and also $RQ^{4}$, thus leading, by the
WBT operation which reduces here to a simple union, the to (unique) world view
of the overall program $W=\\{\\{c,p,a,e,f\\}\\}$.

It is immediate to verify that the result obtained via the bottom-up and the
top-down approach is indeed the same.

###  6.3 Top-down Epistemic Splitting Property (TDESP)

In this subsection, we will extend previous definitions to a more general
form, so as to be able to characterize in a top-down fashion the world views
obtained according to many semantic approaches presented in the literature,
other than G91 and FAAEL, such as, e.g., those proposed by Shen and Eiter
(2016); Kahl and Leclerc (2018); Su (2019); in fact, they do not enjoy the
basic property TDESPB illustrated above. We introduce a different way of
computing candidate world views, where, in the absence of a world view of the
bottom that fulfills the set $EC$ relative to the top, one can select a subset
of such a world view. This, as we will demonstrate in our running example, is
analogous to what is customarily done in ASP.

######  Definition 6.10 (Candidate World View).

Given an epistemic splitting $\langle B_{U}(\Pi),T_{U}(\Pi)\rangle$ for a
program $\Pi$, let $W_{T}$ be a world view of $T_{U}(\Pi)$ and let $W_{B}$ be
a subset of a world view of $B_{U}^{W_{T}}(\Pi)$ that fulfills
$EC_{T_{U}(\Pi)}(W_{T})$ (where, if $EC$ is empty, $W_{B}$ is the entire world
view of the bottom) such that $W_{B}$ fulfills $RQ_{T_{U}(\Pi)}(W_{T})$. Then,

$W=W_{B}\sqcup W_{T}=\\{I_{b}\cup I_{t}|I_{b}\in W_{B}\wedge I_{t}\in
W_{T}\\}$

is a _candidate world view_ for $\Pi$ (obtained from $W_{T}$ and $W_{B}$).

Note that, candidate world views are now computed after applying top-down
influence. It is possible that no subset of any world view of the bottom
complies with the conditions posed by world views of the top. In such case,
$\Pi$ has no candidate world views.

We can now state another property concerning top-down epistemic splitting that
a semantics might obey:

######  Definition 6.11 (Top-down Epistemic Splitting Property (TDESP)).

A semantics $\cal{S}$ satisfies _top-down epistemic splitting_ if any
candidate world view of $\Pi$ according to Definition 6.10 is indeed a world
view of $\Pi$ under $\cal{S}$.

We can state the relationship among TDESP and ESP/TDESPB (that, as seen, are
equivalent).

######  Theorem 6.12.

Given a semantics $\cal{S}$ satisfies both foundedness and ESP/TDESPB, then
$\cal{S}$ satisfies TBDESP.

######  Proof 6.13.

If $\cal{S}$ satisfies TDESPB, this means that for every world view of given
program $\Pi$ obtained via the WBT operation, and thus composed of a world
view $W_{T}$ of the top and a world view $W_{B}$ of the bottom, every
$\mbox{{K}}L\in EC_{T_{U}(\Pi)}(W)$ is entailed by $W_{B}$ and, if $\cal{S}$
satisfies foundedness, this equates to say that $L$ is entailed by the bottom
part of the program. Thus, the application of Top-down Influence is
irrelevant. We then notice that, according to Definitions 6.10 and 6.3 a
candidate world view for TDESP can be obtained from an entire world view of
the bottom, as done for TDESPB. This concludes the proof, showing that for
this class of semantics TDESP and TDESPB are indeed equivalent.

The above theorem is immediately applicable to the FAAEL semantics. For
semantics which do not enjoy foundedness things are different, as seen in the
examples below. We will now, in fact, experiment with our methodology on some
relevant examples proposed in recent literature. Consider program $\Pi_{1}$,
taken from Shen and Eiter (2020):

$\begin{array}[]{llcll}p\ |\ q&~{}(r1)\\\ \bot\leftarrow
not\,\mbox{{K}}p&~{}(C)\end{array}$

Here, $B_{U}(\Pi_{1})$ consists of rule (r1), and $T_{U}(\Pi_{1})$ consists of
constraint (C). So, $T^{\prime}_{U}(\Pi_{1})$ is (where $kp$ and $nkp$ are
fresh atoms):

$\begin{array}[]{llcll}kp\ |\ nkp&~{}(r1)\\\ \bot\leftarrow nkp&\end{array}$

whose unique world view is $\\{\\{kp\\}\\}$. After canceling $kp$, we obtain
$W_{T}=\\{\emptyset\\}$ for $T_{U}(\Pi_{1})$, with
$ES_{T_{U}(\Pi_{1})}(W_{T})=EC_{T_{U}(\Pi_{1})}(W_{T})=\\{\mbox{{K}}p\\}$ and
$RQ_{T_{U}(\Pi_{1})}(W_{T})=\emptyset$. Regardless of the epistemic semantics
$\cal{S}$, as no subjective literals occur therein, the unique world view of
$B_{U}(\Pi_{1})$ is $\hat{W}=\\{\\{p\\},\\{q\\}\\}$. Since
$W_{B}=\\{\\{p\\}\\}$ is the only subset of $\hat{W}$ fulfilling
$EC_{T_{U}(\Pi_{1})}(W_{T})$ (cf. Definition 6.10), then it is the one
selected. It is also a world view for $\Pi_{1}$, as the unique world view of
the top part is empty. This world view violates subjective constraint
monotonicity, still, it is the one delivered by the semantics proposed in Shen
and Eiter (2016) and, as noticed in Shen and Eiter (2020), by those proposed
in Kahl and Leclerc (2018); Su (2019).

In our opinion the world view $\\{\\{p\\}\\}$ captures the “intended meaning”
of the program $\Pi_{1}$, where the top layer “asks” the bottom layer to
support, if possible, $\mbox{{K}}p$ (in order not to make the overall program
inconsistent). Let us, in fact, introduce a simple variation, by adding a
fact, say $c$, to the program, where $c$ also occurs in the constraint,
obtaining:

$\begin{array}[]{llcll}p\ |\ q&~{}(r1)\\\ c.&~{}(f1)\\\ \bot\leftarrow
c,not\,\mbox{{K}}p&~{}(C)\end{array}$

We would obtain, in this case, the world view $\\{\\{c,p\\}\\}$. Let us now
reinterpret this program within the work of the COST Action DigForASP, i.e.,
in the realm of investigations. A rephrasing could be the following:

$\begin{array}[]{llcll}at\\_crime\\_scene\ |\
not\\_at\\_crime\\_scene&~{}(r1)\\\
reliable\\_witness\\_recognizes.&~{}(f1)\\\ \bot\leftarrow
reliable\\_witness\\_recognizes,not\,\mbox{{K}}\,at\\_crime\\_scene&~{}(C)\end{array}$

The meaning underlying the schematic formulation is that it is uncertain
whether a suspect was or not at the crime scene. However, if a reliable
witness recognized the suspect, then investigators can be certain that the
suspect was indeed at the crime scene. The constraint could in fact be
rephrased (although this is not legal syntax) into:

$\begin{array}[]{llcll}\mbox{{K}}\,at\\_crime\\_scene\leftarrow
reliable\\_witness\\_recognizes.\end{array}$

The use of the K is crucial here because one wants to distinguish between
facts collected by the investigators and reliable conclusions derived by these
facts. Thus, the world view
$\\{\\{reliable\\_witness\\_recognizes,at\\_crime\\_scene\\}\\}$ makes perfect
sense here.

In addition, one might consider the very similar ASP program:

$\begin{array}[]{llcll}p\ |\ q&~{}(r1)\\\ c.&~{}(f1)\\\ \bot\leftarrow
c,not\,p&~{}(C)\end{array}$

with unique answer set $\\{c,p\\}$. The “bottom” program fragment consisting
of (r1)+(f1) would also have answer set $\\{c,q\\}$, which is discarded since
it would lead to violating the constraint. We may consider this program as an
ELP, with unique world view $\\{\\{c,p\\}\\}$ obtained from a subset of the
world view $\\{\\{c,p\\},\\{c,q\\}\\}$ of the bottom (union the empty world
view of the top), exactly as specified in Definition 6.10.

Consider now the following program $\Pi_{2}$.

$\begin{array}[]{ll}p\ |\ q&~{}~{}~{}(r1)\\\ \bot\leftarrow
not\,\mbox{{K}}p&~{}~{}~{}(C)\\\ p\leftarrow\mbox{{K}}q&~{}~{}~{}(r2)\\\
q\leftarrow\mbox{{K}}p&~{}~{}~{}(r3)\end{array}$

Here, $B_{U}(\Pi_{2})$ consists of rules (r1-r3), and $T_{U}(\Pi_{2})$
consists of constraint (C). So, $T^{\prime}_{U}(\Pi_{2})$ is (where $kp$ and
$nkp$ are fresh atoms):

$\begin{array}[]{ll}kp\ |\ nkp\\\ \bot\leftarrow nkp\end{array}$

whose unique world view is $\\{\\{kp\\}\\}$. After canceling $kp$, we obtain
world view $W_{T}=\\{\emptyset\\}$ for $T_{U}(\Pi_{2})$ where
$ES_{T_{U}(\Pi_{2})}(W_{T})=EC_{T_{U}(\Pi_{2})}(W_{T})=\\{\mbox{{K}}p\\}$ and
set $RQ$ is empty. Regardless of the semantics $\cal{S}$, the potential world
views of $B_{U}(\Pi_{2})$ are $W_{1}=\\{\\{p\\}\\}$, $W_{2}=\\{\\{q\\}\\}$,
$W_{3}=\\{\\{p\\},\\{q\\}\\}$, $W_{4}=\\{\\{p,q\\}\\}$. Actually, $W_{4}$ is
the only one fulfilling $ES_{T_{U}(\Pi_{2})}(W_{T})$; $W_{1}$ has the problem
that, having $p$ and fulfilling $\mbox{{K}}p$, (r3) might be applied thus
getting $q$. Note that $W_{4}$ is in fact the world view returned by semantics
proposed, for instance, in Kahl et al. (2015) and Shen and Eiter (2016). It is
easy to see that $W_{4}$ violates foundedness. However, in our approach $q$ is
not derived via the positive cycle (extended to subjective literals), but from
the $\mbox{{K}}p$ “forced” by the upper layer via top-down influence, which
substitutes $\mbox{{K}}p$ with $p$ in rule (r3) of $B_{U}(\Pi_{2})$. This in a
sense guarantees a form of foundedness, though not the formal one introduced
in (Cabalar et al., 2021, Def. 15). Since the unique world view for the top is
empty, then the unique world view of the overall program is, indeed, according
to our method, $W=W_{4}=\\{\\{p,q\\}\\}$.

Let us now consider $\Pi_{3}$ to be the seminal example introduced in Gelfond
and Przymusinska (1991), which is discussed in virtually every paper on ELP.
$\Pi_{3}$ is epistemically stratified (see Definition 4.4 and (Cabalar et al.,
2021, Def. 6)). This formulation (variations have appeared over time) is from
Cabalar et al. (2021).

$\begin{array}[]{ll}\mathit{eligible(X)}\leftarrow\mathit{high(X)}&~{}(r1)\phantom{\overline{\overline{|}}}\\\
\mathit{eligible(X)}\leftarrow\mathit{minority(X)},\mathit{fair(X)}&~{}(r2)\\\
\mathit{noeligible(X)}\leftarrow
not\,\mathit{fair(X)},not\,\mathit{high(X)}&~{}(r3)\\\ \mathit{fair(mike)}\ |\
\mathit{high(mike)}&~{}(f1)\\\ \mathit{interview(X)}\leftarrow
not\,\mbox{{K}}\,\mathit{eligible(X)},not\,\mbox{{K}}\,\mathit{noeligible(X)}&~{}(r4)\\\
\mathit{appointment(X)}\leftarrow\mbox{{K}}\,\mathit{interview(X)}&~{}(r5)\phantom{\underline{\underline{|}}}\end{array}$

Since in this version of the program we have only $\mathit{mike}$ as an
individual, we may obtain the following ground abbreviated version:

$\begin{array}[]{lc}e\leftarrow h&~{}(r1)\\\ e\leftarrow m,f&~{}(r2)\\\
ne\leftarrow not\,f,not\,h&~{}(r3)\\\ f\ |\ h&~{}(f1)\\\ in\leftarrow
not\,\mbox{{K}}e,\;not\,\mbox{{K}}ne&~{}(r4)\\\
a\leftarrow\mbox{{K}}in&~{}(r5)\end{array}$

Here, we consider (r5) as the top $T_{U}(\Pi_{3})$, and (r1-r4) plus (f1) as
the bottom, which can be however in turn divided into the top
$T1_{U}(\Pi_{3})$ including (r4), and the bottom $B_{U}(\Pi_{3})$, made of
(r1-r3) and (f1). So, $T^{\prime}_{U}(\Pi_{3})$ is (with fresh atoms $kin$,
$nkin$):

$\begin{array}[]{llcll}a\leftarrow kin&~{}(r5^{\prime})\\\ kin\ |\ nkin\\\
\end{array}$

with two answer sets: $\\{a,kin\\},\\{nkin\\}$. As explained in Section 6.1,
$kin\ |\ nkin$ stands for a disjunction between the epistemic literal
$\mbox{{K}}in$ and its negation $not\,\mbox{{K}}in$. This determines the
existence of two world views, each entailing only one of these atoms, i.e.
epistemic literals, where atom $a$ can, however, be derived only from the
former. Thus, we have $W_{11}=\\{\\{a\\}\\}$ with
$ES_{T_{U}(\Pi_{3})}(W_{11})=\\{\mbox{{K}}in\\}$, and $W_{12}=\\{\emptyset\\}$
with $ES_{T_{U}(\Pi_{3})}(W_{12})=\\{not\,\mbox{{K}}in\\}$.
$EC_{T1_{U}(\Pi_{3})}$ is empty for all world views, as no constraint is
present in $\Pi_{3}$. Then, $T1^{\prime}_{U}(\Pi_{3})$ is (with
$ke,nke,kne,nkne$ fresh atoms):

$\begin{array}[]{llcllcll}in\leftarrow nke,nkne&~{}(r4^{\prime})\\\ ke\ |\
nke\\\ kne\ |\ nkne.\end{array}$

By the same reasoning as above, since there are two disjunctions among fresh
atoms representing epistemic literals, four world views can be found. After
canceling the fresh atoms, in fact we have $W_{21}=\\{\\{in\\}\\}$, with
$ES_{T1^{\prime}_{U}(\Pi_{3})}(W_{21})=\\{not\,\mbox{{K}}e,not\,\mbox{{K}}ne\\}$,
and three empty world views $W_{22}=W_{23}=W_{24}=\\{\emptyset\\}$, with
requisite sets $\\{\mbox{{K}}e,\mbox{{K}}ne\\}$,
$\\{\mbox{{K}}ne,not\,\mbox{{K}}e\\}$, and
$\\{not\,\mbox{{K}}ne,\mbox{{K}}e\\}$, respectively. Clearly, also
$EC_{T1^{\prime}_{U}(\Pi_{3})}$ is empty.

Finally, $B_{U}(\Pi_{3})$, which is made of the rules (r1-r3) and (f1), has
the world view $W_{3}=\\{\\{h,e\\},\\{f\\}\\}$. Since the requirement set
relative to world view $W_{21}$ for the immediately upper level is satisfied
in both answer sets of $W_{3}$, we can obtain an intermediate world view
$W_{{213}}=\\{\\{h,e,in\\},\\{f,in\\}\\}$ for the part of the program
including (r1-r4). Considering also the top, it is easily seen that
$W_{{213}}$ is compliant with the requirement set of $W_{11}=\\{a\\}$. So, we
can obtain for the overall program the unique candidate world view
$W=\\{\\{h,e,in,a\\},\\{f,in,a\\}\\}$, which is indeed a world view. Notice
that, in fact, the world views that are part of the union, corresponding to
the various sub-programs, would be the same under all known semantics for
ELPs.

Assume now that, instead of $f\ |\ h$, the program contains the bare fact $h$.
Then, the world view of the bottom becomes $W_{3}=\\{\\{h,e\\}\\}$. This world
view implies $\mbox{{K}}e$, so it can be combined with a world view
$\\{\emptyset\\}$ of the middle layer, and since it also implies
$not\,\mbox{{K}}in$, the further combination is with world view
$W_{12}=\\{\emptyset\\}$ of the top. So, $W_{3}=\\{\\{h,e\\}$ is in this case
the unique world view of the overall program.

##  7 Main Result

It is at this point interesting to try to assess formally which semantics (if
any) satisfy the top-down epistemic splitting property TDESP.

We examine now the case of the semantics introduced in Kahl et al. (2015),
that we call for short K15. The reason for choosing K15 is that in Cabalar et
al. (2021) it is noticed that K15 slightly generalizes the semantics proposed
in Gelfond (2011) (called G11 for short) and can be seen as a basis for the
semantics proposed in Shen and Eiter (2016) (called S16 for short). In
particular, S16 (which considers instead of K the operator not  $A$ which
means $not\,\mbox{{K}}A$) treats K15 world views as candidate solutions, to be
pruned in a second step, where some unwanted world views are removed by
maximizing what is not known. Thus, should K15 satisfy the top-down epistemic
splitting property, S16 would do as well, and so would G11, the latter however
only for the (wide) class of programs where its world views coincide with
those of K15.

######  Definition 7.1 (K15-world views).

The K15-reduct of $\Pi$ with respect to a non-empty set of interpretations $W$
is obtained by:

  * (i)

replacing by $\bot$ every subjective literal $L\in\mathit{Body_{subj}}(r)$
such that $W\not\models L$, and

  * (ii)

replacing all other occurrences of subjective literals of the form
$\mbox{{K}}L$ by $L$.

A non-empty set of interpretations $W$ is a K15-world view of $\Pi$ iff $W$ is
the set of all stable models of the K15-reduct of $\Pi$ with respect to $W$.

We are able to prove the following:

######  Theorem 7.2 (K15 TDESP).

The K15 semantics satisfies the Top-down Epistemic Splitting Property. I.e.,
given an ELP $\Pi$, and set of sets $W$, where each set is composed of atoms
occurring in $\Pi$, $W$ is a K15 world view for $\Pi$ if and only if it is a
candidate world view for $\Pi$ according to Definition 6.10.

######  Proof 7.3.

Assume an Epistemic Splitting of given program $\Pi$ into two layers, top
$T_{U}(\Pi)$ and bottom $B_{U}(\Pi)$ (where the reasoning below can, however,
be iterated over a subdivision into an arbitrary number of levels). Notice
that, given a K15 world view $W$, since each atom $A$ that occurs in the sets
composing $W$ is derived in the part of the program including rules with head
$A$, then $W$ can be divided into two parts, $W_{T}$, and $W_{B}$ which are
world views of $T_{U}(\Pi)$ and $B_{U}(\Pi)$, resp., each one composed of
stable models of the K15-reduct of that part of the program.

_If part._ Given a K15 world view $W$, let $Sl^{T}$ be the subjective literals
occurring in $T_{U}(\Pi)$ which are entailed by the bottom, i.e., either of
the form $\mbox{{K}}A$, for which $W_{B}\models A$, or of the form
$not\,\mbox{{K}}A$, for which $W_{B}\not\models A$. Let such a set of literals
form the set $ES_{T_{U}(\Pi)}(W_{T})$. (As mentioned, the subset of $Sl^{T}$
that consists of literals involved in constraints in $T_{U}(\Pi)$ will form
set $EC_{T_{U}(\Pi)}(W_{T})$, and the remaining ones will form set
$RQ_{T_{U}(\Pi)}(W_{T})$.) Therefore, we can conclude that $W$, which is a K15
world view, is indeed a candidate world view according to Definition 6.10.

_Only if part._ Consider a candidate world view $W$ w.r.t. the K15 semantics,
obtained by combining a subset $W_{B}$ of a K15 world view of $B_{U}(\Pi)$
with a K15 world view $W_{T}$ of $T_{U}(\Pi)$ after top-down influence.
According to Definition 6.10, the combination is possible only if for each
epistemic literal $\mbox{{K}}A\in ES_{T_{U}(\Pi)}(W_{T})$, $W_{B}\models A$,
and for each epistemic literal $not\,\mbox{{K}}A\in ES_{T_{U}(\Pi)}(W_{T})$,
$W_{B}\not\models A$. If any such literal belongs to $EC_{T_{U}(\Pi)}(W_{T})$,
if this is not the case then there would be a constraint violation in
$T_{U}(\Pi)$, so there would be no world views for $T_{U}(\Pi)$, and for the
overall program $\Pi$. Considering a subjective literal in
$RQ_{T_{U}(\Pi)}(W_{T})$, if it were not the case that $W_{B}$ entails such
literal, then by definition of K15 it would have been substituted by $\bot$,
so $W_{T}$ would have been a different set. The top-down influence step can be
disregarded since it performs in advance on elements of
$ES_{T_{U}(\Pi)}(W_{T})$, that are required to be entailed by $W_{B}$ anyway,
the same transformation performed by K15, step (ii). Then, a candidate world
view $W$ obtained according to Definition 6.10 is indeed a K15 world view.

In (Cabalar et al., 2021, Th. 2) it is proved that, for any semantics obeying
epistemic splitting, an epistemically stratified program has a unique world
view. Actually, it can be seen that epistemically stratified programs admit
one (and the same) world view under any existing semantics, and in particular
under those considered here: as it is well-known (see, e.g. Gelfond (1994);
Shen and Eiter (2016); Costantini (2019)), multiple world views arise in
consequence of negative cycles involving epistemic literals, clearly not
present in such programs. So, the unique world view of an epistemically
stratified program is, in particular, a K15 world view. Thus, we have the
following.

######  Corollary 7.4.

Epistemically Stratified Programs satisfy both the Top-down and Bottom-up
Epistemic Splitting Properties under any semantics.

##  8 Conclusions

In this paper, we have provided a way of exploiting the splitting of Epistemic
Logic Programs in a top-down fashion, adequate for those situations where the
top part of a program is well-established as it represents a problem
formulation, where the bottom part (representing a problem instance) may vary
and is in general not known in advance.

We defined formal conditions for the combination of world views of the top
with world views of the bottom into world views of the overall program. In
addition, potential world views of the top can be pre-computed, thus
simplifying the combination with the world views of each problem instance. We
provide a version that is the top-down declination of the well-established
approach by Cabalar et al., and a more general version that is applicable to a
wider range of semantic approaches.

A question that may arise concerns the efficiency of the top-down approach,
even though in many cases it will be an almost inevitable choice. If the
subjective literals “connecting” adjacent layers are in small numbers (as it
seems reasonable), then efficiency might not be a concern.

It remains to be seen in more depth for which kinds of applications the
different approaches to splitting (top-down and bottom-up) might be most
profitably exploited. As an example, we can go back to the suggestion proposed
in Kahl et al. (2015) to encode the problem of finding a conformant plan as
the task of obtaining a world view. As emphasized in Cabalar et al. (2021),
splitting allows one to separate the planner definition (the “top”) from the
generation of alternative plans (an intermediate layer, we might say “the top
of the bottom”) from, in turn, the domain description (the “bottom”). The top-
down perspective would allow one to analyze the top part independently from
the other layers, so as to identify in advance the prerequisites it poses to
them.

An investigation of which other semantics might satisfy the Top-down Epistemic
Splitting Property is also a subject of future work.

## References

  * Cabalar et al. (2021) Cabalar, P., Fandinno, J., and del Cerro, L. F. 2021\.  Splitting epistemic logic programs.  Theory Pract. Log. Program. 21, 3, 296–316.
  * Cabalar et al. (2019) Cabalar, P., Fandinno, J., and Fariñas del Cerro, L. 2019\.  Splitting epistemic logic programs.  In Proc. of LPNMR’19, M. Balduccini, Y. Lierler, and S. Woltran, Eds. Lecture Notes in Computer Science, vol. 11481. Springer, 120–133.
  * Costantini (2002) Costantini, S. 2002\.  Meta-reasoning: A survey.  In Computational Logic: Logic Programming and Beyond, Essays in Honour of Robert A. Kowalski, Part II, A. C. Kakas and F. Sadri, Eds. Lecture Notes in Computer Science, vol. 2408. Springer, 253–288.
  * Costantini (2006) Costantini, S. 2006\.  On the existence of stable models of non-stratified logic programs.  Theory and Practice of Logic Programming 6, 1-2, 169–212.
  * Costantini (2019) Costantini, S. 2019\.  About epistemic negation and world views in epistemic logic programs.  Theory Pract. Log. Program. 19, 5-6, 790–807.
  * Costantini and Formisano (2015) Costantini, S. and Formisano, A. 2015\.  Negation as a resource: a novel view on answer set semantics.  Fundamenta Informaticae 140, 3-4, 279–305.
  * Costantini and Formisano (2021) Costantini, S. and Formisano, A. 2021\.  Adding metalogic features to knowledge representation languages.  Fundamenta Informaticae 181, 1, 71–98.
  * Costantini and Formisano (2022) Costantini, S. and Formisano, A. 2022\.  Epistemic logic programs: a novel perspective and some extensions.  In Proceedings of the International Conference on Logic Programming 2022 Workshops co-located with the 38th International Conference on Logic Programming (ICLP) 2022, Haifa, Israel, July 31st - August 1st, 2022, J. Arias, R. Calegari, L. Dickens, W. Faber, J. Fandinno, G. Gupta, M. Hecher, D. Inclezan, E. LeBlanc, M. Morak, E. Salazar, and J. Zangari, Eds. CEUR Workshop Proceedings, vol. 3193\. CEUR-WS.org.
  * Dix (1995) Dix, J. 1995\.  A classification theory of semantics of normal logic programs I-II.  Fundamenta Informaticae 22, 3, 227–255 and 257–288.
  * Fandinno et al. (2022) Fandinno, J., Faber, W., and Gelfond, M. 2022\.  Thirty years of epistemic specifications.  Theory Pract. Log. Program. 22, 6, 1043–1083.
  * Fariñas del Cerro et al. (2015) Fariñas del Cerro, L., Herzig, A., and Su, E. I. 2015\.  Epistemic equilibrium logic.  In Proc. of IJCAI 2015, Q. Yang and M. Wooldridge, Eds. AAAI Press, 2964–2970.
  * Gelfond (1994) Gelfond, M. 1994\.  Logic programming and reasoning with incomplete information.  Ann. Math. Artif. Intell. 12, 1-2, 89–116.
  * Gelfond (2011) Gelfond, M. 2011\.  New semantics for epistemic specifications.  In Proc. of LPNMR’11, J. P. Delgrande and W. Faber, Eds. LNCS, vol. 6645. Springer, 260–265.
  * Gelfond and Lifschitz (1988) Gelfond, M. and Lifschitz, V. 1988\.  The stable model semantics for logic programming.  In Proc. of the 5th Intl. Conf. and Symp. on Logic Programming, R. Kowalski and K. Bowen, Eds. MIT Press, 1070–1080.
  * Gelfond and Przymusinska (1991) Gelfond, M. and Przymusinska, H. 1991\.  Definitions in epistemic specifications.  In Proc. of the 1st Intl. Workshop on Logic Programming and Non-monotonic Reasoning, A. Nerode, V. W. Marek, and V. S. Subrahmanian, Eds. The MIT Press, 245–259.
  * Kahl et al. (2015) Kahl, P., Watson, R., Balai, E., Gelfond, M., and Zhang, Y. 2015\.  The language of epistemic specifications (refined) including a prototype solver.  J. Log. Comput. 30, 4, 953–989.
  * Kahl and Leclerc (2018) Kahl, P. T. and Leclerc, A. P. 2018\.  Epistemic logic programs with world view constraints.  In Tech. Comm. of ICLP 2018, A. D. Palù, P. Tarau, N. Saeedloei, and P. Fodor, Eds. OASIcs, vol. 64. Schloss Dagstuhl, 1:1–1:17.
  * Leone et al. (1997) Leone, N., Rullo, P., and Scarcello, F. 1997\.  Disjunctive stable models: Unfounded sets, fixpoint semantics, and computation.  Inf. Comput. 135, 2, 69–112.
  * Lifschitz (2010) Lifschitz, V. 2010\.  Thirteen definitions of a stable model.  In Fields of Logic and Computation, A. Blass, N. Dershowitz, and W. Reisig, Eds. LNCS, vol. 6300. Springer, 488–503.
  * Lifschitz and Turner (1994) Lifschitz, V. and Turner, H. 1994\.  Splitting a logic program.  In Proc. of ICLP’94. MIT Press, 23–37.
  * Lloyd (1987) Lloyd, J. W. 1987\.  Foundations of Logic Programming.  Springer-Verlag.
  * Shen and Eiter (2016) Shen, Y. and Eiter, T. 2016\.  Evaluating epistemic negation in answer set programming.  Artificial Intelligence 237, 115–135.
  * Shen and Eiter (2020) Shen, Y. and Eiter, T. 2020\.  Constraint monotonicity, epistemic splitting and foundedness are too strong in answer set programming.  CoRR abs/2010.00191, 1–6.
  * Su (2019) Su, E. I. 2019\.  Epistemic answer set programming.  In Proc. of JELIA’19, F. Calimeri, N. Leone, and M. Manna, Eds. LNCS, vol. 11468. Springer, 608–626.
  * Su (2021) Su, E. I. 2021\.  Refining the semantics of epistemic specifications.  In Proceedings 37th International Conference on Logic Programming (Technical Communications), ICLP Technical Communications 2021, Porto (virtual event), 20-27th September 2021, A. Formisano, Y. A. Liu, B. Bogaerts, A. Brik, V. Dahl, C. Dodaro, P. Fodor, G. L. Pozzato, J. Vennekens, and N. Zhou, Eds. Electronic Proceedings in Theoretical Computer Science, vol. 345. EPTCS, 113–126.
  * Truszczynski (2011) Truszczynski, M. 2011\.  Revisiting epistemic specifications.  In Logic Programming, Knowledge Representation, and Nonmonotonic Reasoning, M. Balduccini and T. C. Son, Eds. LNCS, vol. 6565. Springer, 315–333.


# Packing and Covering Triangles in Bilaterally- Complete Tripartite Graphs

Naivedya Amarnani $\boldsymbol{\cdot}$ Amaury De Burgos $\boldsymbol{\cdot}$
Wayne Broughton

###### Abstract

We use Menger’s Theorem and König’s Line Colouring Theorem to show that in any
tripartite graph with two complete (bipartite) sides the maximum number of
pairwise edge-disjoint triangles equals the minimum number of edges that meet
all triangles. This generalizes the corresponding result for complete
tripartite graphs given by Lakshmanan, et al.

Keywords: Maximum Packing, Tripartite Graphs, Minimum T-Transversal,
Triangles, Complete Bipartite Graph

##  Introduction

††The first author was supported by Mitacs through a Mitacs Globalink Research
Internship while visiting UBC Okanagan. The second author was supported by an
Undergraduate Research Award from the I.K. Barber Faculty of Science at UBC
Okanagan.

N. Amarnani
Mathematics and Statistics, Indian Institute of Technology Kanpur
Kanpur, Uttar Pradesh, India

A. De Burgos, W. Broughton
Mathematics, University of British Columbia - Okanagan
Kelowna, British Columbia, Canada
E-mail<EMAIL_ADDRESS>
For standard graph-theoretic terms or notation, refer to [11]. All graphs will
be finite, simple and undirected unless indicated otherwise. An edge with
endpoints $u$ and $v$ will generally be denoted $uv$. In graph $G=(V,E)$, if
$X\subseteq V$ or $Y\subseteq E$ then $G[X]$ denotes the subgraph of $G$
induced by $X$ and $G[Y]$ denotes the subgraph edge-induced by $Y$.

A triangle in a graph $G$ is a subgraph isomorphic to $K_{3}$, consisting of 3
vertices that are all joined by edges. Most of the following definitions and
notation are from [9] and [5].

Let $\mathcal{T}$ denote the set of all triangles in $G=(V,E)$. A subset
$E^{\prime}\subseteq E$ is said to be a $\mathcal{T}$-transversal if every
triangle in $\mathcal{T}$ has an edge in $E^{\prime}$.

A subset $\mathcal{T}^{\prime}\subseteq\mathcal{T}$ is said to be a packing in
$G$ if all the triangles in $\mathcal{T}^{\prime}$ are pairwise edge-disjoint.

We denote the cardinality of the smallest $\mathcal{T}$-transversal in $G$ by
$\tau_{\triangle}(G)$ and the cardinality of the largest packing by
$\nu_{\triangle}(G)$. It is not difficult to see that
$\nu_{\triangle}(G)\leq\tau_{\triangle}(G)\leq 3\nu_{\triangle}(G)$.

In 1981 Zsolt Tuza conjectured ([10]) that $\tau_{\triangle}(G)\leq
2\nu_{\triangle}(G)$ for every graph $G$. The general case is still open, but
when $G$ is a tripartite graph an even stronger bound was proved by Haxell and
Kohayakawa ([3]). In 2012, Lakshmanan et al. ([5]) proved that in fact the
equality $\tau_{\triangle}(G)=\nu_{\triangle}(G)$ holds for certain classes of
tripartite graphs. Their results can be viewed as extensions to these
tripartite graphs of the König-Egerváry Theorem, equating the minimum size of
a vertex cover and the maximum matching size in bipartite graphs. In
particular, it is observed in [5] that
$\tau_{\triangle}(G)=\nu_{\triangle}(G)$ always holds for complete tripartite
graphs. In this paper, we show that this equality also holds for tripartite
graphs with only two complete bipartite sides.

If $G=(V,E)$ is a tripartite graph whose vertex set is partitioned into
$V=A\cup B\cup C$, then we write $G=(A,B,C;E)$ and we call the induced
bipartite subgraphs $G[A\cup B]$, $G[A\cup C]$, and $G[B\cup C]$ the sides of
$G$. The sets of edges on the sides are written $E_{AB}$, $E_{AC}$, and
$E_{BC}$, respectively. More generally, if $M,W\subseteq V$ then
$E_{MW}\subseteq E$ denotes the set of edges with one endpoint in each of $M$
and $W$ (abusing notation slightly if $M$ or $W$ is just a single vertex).

######  Definition 1 (Bilaterally-Complete Tripartite Graph):

Let $G=(A,B,C;E)$ be a tripartite graph. If (at least) two of the sides of $G$
are complete bipartite graphs, then we call $G$ a bilaterally-complete
tripartite graph.

Our main result is the following:

######  Theorem 1:

If $G$ is a bilaterally-complete tripartite graph, then
$\tau_{\triangle}(G)=\nu_{\triangle}(G)$.

Note: It is possible to derive a proof of this fact from a complicated chain
of results in some old papers (particularly [1], [2] and [8]), but we give a
straightforward proof relying only on classical theorems. The alternative
approach will be discussed in the last section of this paper.

##  Characterization of Minimum $\boldsymbol{\mathcal{T}}$-transversals

Let $G=(A,B,C;E)$ be a bilaterally-complete tripartite graph with complete
sides $G[A\cup B]\cong K_{p,q}$ and $G[A\cup C]\cong K_{p,r}$, where $|A|=p$,
$|B|=q$, $|C|=r$. We will describe the structure of a minimum
$\mathcal{T}$-transversal of $G$ in terms of vertices and edges of $G[B\cup
C]$.

For each vertex $a\in A$, the triangles in $G$ containing $a$ are in one-to-
one correspondence with the edges in $E_{BC}$, since $G$ is bilaterally-
complete. Likewise, edges in $E_{aB}$ and $E_{aC}$ can be identified with
vertices in $B$ and $C$, respectively.

Now let $E^{\prime}$ be a $\mathcal{T}$-transversal in $G$, and fix $a\in A$.
If we let $E^{\prime}_{BC}=E^{\prime}\cap E_{BC}$, then the triangles
containing $a$ and corresponding to edges in $E_{BC}\setminus E^{\prime}_{BC}$
must be covered by $E^{\prime}$ using edges in $E_{aB}\cup E_{aC}$. This means
the corresponding vertices in $B\cup C$ must cover all the edges in
$E_{BC}\setminus E^{\prime}_{BC}$; that is, they form a vertex cover $W_{a}$
of $G[E_{BC}\setminus E^{\prime}_{BC}]$ for each $a\in A$.

Conversely, if we choose a set of edges $E^{\prime}_{BC}\subseteq E_{BC}$ and
a vertex cover $W_{a}$ of $G[E_{BC}\setminus E^{\prime}_{BC}]$ for each $a\in
A$, then

$E^{\prime}=E^{\prime}_{BC}\cup\bigcup_{a\in A}E_{aW_{a}}$

will be a $\mathcal{T}$-transversal of $G$ with size
$|E^{\prime}|=|E^{\prime}_{BC}|+\sum_{a\in A}|W_{a}|$.

If $W_{a}=W$ is the same vertex cover for all $a\in A$ we will call this a
_uniform_ $\mathcal{T}$-transversal. Without loss of generality, a minimum
$\mathcal{T}$-transversal can be assumed to be uniform by choosing
$E^{\prime}_{BC}\subseteq E_{BC}$ and a minimum vertex cover $W$ of
$G[E_{BC}\setminus E^{\prime}_{BC}]$, such that the value of
$|E^{\prime}_{BC}|+p|W|$ is minimized. Hence,

$\displaystyle\tau_{\triangle}(G)=\min_{E^{\prime}_{BC}\subseteq
E_{BC}}\\{|E^{\prime}_{BC}|+p|W|\\},$

where $W$ is a minimum vertex cover of $G[E_{BC}\setminus E^{\prime}_{BC}]$.

It is worth pointing out that in bilaterally-complete tripartite graphs, the
edges of the smallest side do not always form a minimum
$\mathcal{T}$-transversal. In fact, there exist bilaterally-complete
tripartite graphs whose minimum $\mathcal{T}$-transversals must have an edge
in every side of the graph. Such a graph is pictured in Figure 1. This makes
the bilaterally-complete case more complicated than the complete tripartite
case, where the smallest side is always a minimum $\mathcal{T}$-transversal
and the maximum packing can be described explicitly as a selection of one
triangle on each edge in the smallest side of the graph.

$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$

Figure 1: A bilaterally-complete tripartite graph $G=(A,B,C;E)$ with $G[A\cup
B]\cong G[A\cup C]\cong K_{2,4}$. The smallest side has seven edges, but the
only minimum $\mathcal{T}$-transversal is the one of size five shown in
boldface, with an edge in every side of the graph. In this example
$E^{\prime}_{BC}$ is just the singleton $\\{38\\}$ and $W=\\{2,9\\}$.

##  Network Graph H(G)

As before, let $G=(A,B,C;E)$ be a bilaterally-complete tripartite graph with
complete sides $G[A\cup B]\cong K_{p,q}$ and $G[A\cup C]\cong K_{p,r}$, where
$|A|=p$, $|B|=q$, $|C|=r$. The network graph $H(G)=(\mathcal{V},\mathcal{E})$
is a directed graph constructed from $G[B\cup C]$ as follows:

  1. 1.

Make $p$ copies of each of the vertex sets $B$ and $C$, labelled
$B_{1},\ldots,B_{p}$ and $C_{1},\ldots,C_{p}$.

  2. 2.

Create a vertex for each edge in $E_{BC}$, and denote this set of vertices by
$V_{BC}$.

  3. 3.

Create a source vertex $s$ and a sink vertex $t$.

  4. 4.

For each edge $uv$ in $E_{BC}$ ($u\in B$), make a directed arc from every copy
of $u$ in $B_{1},\ldots,B_{p}$ to the vertex in $V_{BC}$ corresponding to the
edge $uv$, and an arc from that same vertex in $V_{BC}$ to every copy of $v$
in $C_{1},\ldots,C_{p}$.

  5. 5.

Make a directed arc from $s$ to each vertex in $B_{1}\cup\cdots\cup B_{p}$,
and from every vertex in $C_{1}\cup\cdots\cup C_{p}$ to $t$.

As an example, let $G$ be the bilaterally-complete tripartite graph shown in
Figure 1. Its induced bipartite graph $G[B\cup C]$ is shown in Figure 2 and
the resulting network graph $H(G)$ is shown in Figure 3. The general
representation of $H(G)$ is shown in Figure 4.

$2$$3$$4$$5$$6$$7$$8$$9$

Figure 2: The induced bipartite graph $G[B\cup C]$ of the graph in Figure 1.

$2$$3$$4$$5$s$2^{\prime}$$3^{\prime}$$4^{\prime}$$5^{\prime}$$6$$7$$8$$9$t$6^{\prime}$$7^{\prime}$$8^{\prime}$$9^{\prime}$$38$$28$$27$$26$$39$$49$$59$$s$$t$

Figure 3: The network graph $H(G)$ constructed from $G[B\cup C]$ in Figure 2.

${b_{1}}^{(1)}$${b_{2}}^{(1)}$$\vdots$${b_{q}}^{(1)}$${b_{1}}^{(2)}$${b_{2}}^{(2)}$$\vdots$${b_{q}}^{(2)}$$\vdots$${b_{1}}^{(p)}$${b_{2}}^{(p)}$$\vdots$${b_{q}}^{(p)}$$B_{1}$$B_{2}$$B_{p}$$s$${c_{1}}^{(1)}$${c_{2}}^{(1)}$$\vdots$${c_{r}}^{(1)}$${c_{1}}^{(2)}$${c_{2}}^{(2)}$$\vdots$${c_{r}}^{(2)}$$\vdots$${c_{1}}^{(p)}$${c_{2}}^{(p)}$$\vdots$${c_{r}}^{(p)}$$C_{1}$$C_{2}$$C_{p}$$t$$\vdots$$e_{2}$$e_{1}$$e_{m}$$V_{BC}$

Figure 4: General representation of $H(G)$, as described in Section 3.
(Internal arcs omitted.) Note that $m=|E_{BC}|$.

##  Minimum $\boldsymbol{\mathcal{T}}$-transversal and Maximum Packing
Equality

Before proving our main result, we recall two classical theorems that we will
use. Menger’s Theorem for Digraphs [6] Let $D$ be a finite directed graph and
$s$ and $t$ be two vertices of $D$ with no arc from $s$ to $t$. Then the
minimum size of an $(s,t)$-separator (that is, the minimum number of vertices,
distinct from $s$ and $t$, whose removal breaks all directed paths from $s$ to
$t$ in $D$) is equal to the maximum number of pairwise internally vertex-
disjoint directed paths from $s$ to $t$ in $D$.

König’s Line Colouring Theorem [4] The minimum number of disjoint matchings
that partition the edges of a bipartite graph equals the maximum degree of the
graph.

We now prove Theorem 1: If $G$ is a bilaterally-complete tripartite graph,
then $\tau_{\triangle}(G)=\nu_{\triangle}(G)$.

Proof Let $G=(A,B,C;E)$ be a bilaterally-complete tripartite graph with
$G[A\cup B]\cong K_{p,q}$ and $G[A\cup C]\cong K_{p,r}$, where $|A|=p$,
$|B|=q$, $|C|=r$. We first show that every uniform $\mathcal{T}$-transversal
of $G$ corresponds to an $(s,t)$-separator of $H(G)$ of the same size, and
every $(s,t)$-separator of $H(G)$ corresponds to a (not necessarily uniform)
$\mathcal{T}$-transversal of $G$ of the same size. Let
$E^{\prime}=E^{\prime}_{BC}\cup E_{AB^{\prime}}\cup E_{AC^{\prime}}$ be a
uniform $\mathcal{T}$-transversal of $G$, where (as described in Section 2)
$E^{\prime}_{BC}\subseteq E_{BC}$, $B^{\prime}\subseteq B$,
$C^{\prime}\subseteq C$, and $W=B^{\prime}\cup C^{\prime}$ is a vertex cover
of $G[E_{BC}\setminus E^{\prime}_{BC}]$. Then we construct an
$(s,t)$-separator of size $|E^{\prime}|$ in the network graph $H(G)$ as
follows: Let $V^{\prime}_{BC}\subseteq V_{BC}$ be the vertices in $H(G)$
corresponding to $E^{\prime}_{BC}$, and for $1\leq i,j\leq p$ let
$B^{\prime}_{i}\subseteq B_{i}$ and $C^{\prime}_{j}\subseteq C_{j}$ be the
vertices in each copy of $B$ and $C$ corresponding to $B^{\prime}$ and
$C^{\prime}$, respectively. Example: The minimum $\mathcal{T}$-transversal
shown in Figure 1 corresponds in Figure 3 to the $(s,t)$-separator
$\\{2,2^{\prime},38,9,9^{\prime}\\}$. Claim:
$\displaystyle\mathcal{V}^{\prime}=V^{\prime}_{BC}\cup\bigcup_{i=1}^{p}B^{\prime}_{i}\cup\bigcup_{j=1}^{p}C^{\prime}_{j}$
is an $(s,t)$-separator of $H(G)$ of size $|E^{\prime}|$. To see why this is
true, note that every directed path from $s$ to $t$ in $H(G)$ contains one
vertex in $B_{i}$, one vertex in $V_{BC}$, and one vertex in $C_{j}$, for some
$i$ and $j$. Since $W=B^{\prime}\cup C^{\prime}$ covers all edges in
$E_{BC}\setminus E^{\prime}_{BC}$ (in $G$), every vertex of $H(G)$ in
$V_{BC}\setminus V^{\prime}_{BC}$ must be adjacent to at least one vertex in
$B^{\prime}_{i}\cup C^{\prime}_{j}$, and therefore every path from $s$ to $t$
contains a vertex in $\mathcal{V}^{\prime}$. We also have
$|\mathcal{V}^{\prime}|=|V^{\prime}_{BC}|+\sum_{i=1}^{p}|B^{\prime}_{i}|+\sum_{j=1}^{p}|C^{\prime}_{j}|=|E^{\prime}_{BC}|+p|B^{\prime}|+p|C^{\prime}|=|E^{\prime}|.$
Conversely, let
$\displaystyle\mathcal{V}^{\prime}=V^{\prime}_{BC}\cup\bigcup_{i=1}^{p}B^{\prime}_{i}\cup\bigcup_{j=1}^{p}C^{\prime}_{j}$
be any $(s,t)$-separator in $H(G)$, with $V^{\prime}_{BC}\subseteq V_{BC}$,
$B^{\prime}_{i}\subseteq B_{i}$, and $C^{\prime}_{j}\subseteq C_{j}$. Every
$s$–$t$ path in $\\{s\\}\cup B_{i}\cup V_{BC}\cup C_{j}\cup\\{t\\}$ must be
cut by $\mathcal{V}^{\prime}$, so in particular (when $i=j$), every vertex in
$V_{BC}\setminus V^{\prime}_{BC}$ must be adjacent to a vertex in
$B^{\prime}_{i}\cup C^{\prime}_{i}$ for each $i=1,\ldots,p$. By slightly
abusing notation we will write $B^{\prime}_{i}\subseteq B$ and
$C^{\prime}_{i}\subseteq C$ (in $G$) as well. (Note that we are not assuming
that all of the $B^{\prime}_{i}$ are the same set of vertices in $B$, for
example.) Let $E^{\prime}_{BC}$ be the edges in $E_{BC}$ corresponding to the
vertices in $V^{\prime}_{BC}$. Then $W_{i}=B^{\prime}_{i}\cup C^{\prime}_{i}$
must cover all the edges in $E_{BC}\setminus E^{\prime}_{BC}$. So, labelling
the vertices in $A$ as $a_{1},\ldots,a_{p}$, we see that $\displaystyle
E^{\prime}=E^{\prime}_{BC}\cup\bigcup_{i=1}^{p}E_{a_{i}W_{i}}$ is a
$\mathcal{T}$-transversal of $G$, and
$|E^{\prime}|=|E^{\prime}_{BC}|+\sum_{i=1}^{p}|W_{i}|=|V^{\prime}_{BC}|+\sum_{i=1}^{p}\left(|B^{\prime}_{i}|+|C^{\prime}_{i}|\right)=|\mathcal{V}^{\prime}|.$
Since there always exists a minimum $\mathcal{T}$-transversal of $G$ that is
uniform, the above correspondences show that the smallest size of an
$(s,t)$-separator in $H(G)$ equals $\tau_{\triangle}(G)$, the minimum
$\mathcal{T}$-transversal size of $G$. Thus Menger’s Theorem guarantees that
there exists a set $P$ of $\tau_{\triangle}(G)$ pairwise internally vertex-
disjoint $s$–$t$ paths in the network graph $H(G)$. Once again, each $s$–$t$
path in $H(G)$ contains one vertex from each of $B_{i}$, $V_{BC}$, and $C_{j}$
(for some $i,j$), which correspond to an edge in $E_{BC}$ and its endpoints.
Let $F$ denote the subgraph of the bipartite graph $G[B\cup C]$ consisting of
these edges and vertices corresponding to all paths in $P$. Because the paths
in $P$ are internally vertex-disjoint, $F$ contains exactly
$\tau_{\triangle}(G)$ edges. $F$ also has maximum degree at most $p$, because
any vertex in $B$ or $C$ corresponds to only $p$ vertices in $H(G)$ and none
of those vertices in $H(G)$ can appear more than once in the paths in $P$.
Therefore by König’s Line Colouring Theorem, the edges of $F$ can be
partitioned into $p$ or fewer matchings, say $M_{1},\ldots,M_{k}$ ($k\leq p$).
We then join the edges in each matching $M_{i}$ to the vertex $a_{i}\in A$ for
$1\leq i\leq k$, and the resulting set of triangles is clearly a packing in
$G$. Since the number of edges in the graph $F$ was $\tau_{\triangle}(G)$, we
have obtained a packing of size $\tau_{\triangle}(G)$ in $G$, which proves
that $\tau_{\triangle}(G)=\nu_{\triangle}(G)$. ∎

##  Alternative Derivation

The key step in our proof above is the existence of (up to) $p$ pairwise
disjoint matchings in $G[B\cup C]$ that consist of a total of
$\tau_{\triangle}(G)$ edges. This could actually be derived easily from
Theorem 6 in Mao Cheng’s 1983 paper [1] (in Chinese), as we show below. But
that short paper gives only a brief proof based on Theorem 8 in the 1971 paper
[2], whose proof in turn relies on (essentially) Theorem 2.2 in the 1968 paper
[8] (itself proved in a more general form from Menger’s Theorem) and an
unspecified result in [7]. It was due to the difficulty of tracing this
convoluted logical route that we decided to present our own direct and self-
contained proof above.

The statement of Mao Cheng’s Theorem 6 is given below, with notation adjusted
to correspond more closely with the present paper. Note that when $X$ is a set
of vertices in a graph, $\partial(X)$ refers to the set of all edges in the
graph that are incident on vertices in $X$.

Theorem 6 ([1], translated)  Let $p,t\in\mathbb{N}^{+}$ and let $G[B\cup C]$
be a bipartite graph with parts $B$ and $C$. There exist $p$ pairwise edge-
disjoint matchings in $G[B\cup C]$ such that the sum of their cardinalities
equals $t$ if and only if for all $B^{\prime\prime}\subseteq B$ and for all
$C^{\prime\prime}\subseteq C$,

$\displaystyle|\partial(B^{\prime\prime})\cap\partial(C^{\prime\prime})|+p\left(|B|+|C|-|B^{\prime\prime}|-|C^{\prime\prime}|\right)\geq
t.$

This result implies that $G[B\cup C]$ admits $p$ pairwise disjoint matchings
with a total number of edges equal to the minimum value of

$\displaystyle|\partial(B^{\prime\prime})\cap\partial(C^{\prime\prime})|+p\left(|B|+|C|-|B^{\prime\prime}|-|C^{\prime\prime}|\right)$

over all $B^{\prime\prime}\subseteq B$ and $C^{\prime\prime}\subseteq C$. We
now show that this minimum value equals $\tau_{\triangle}(G)$ in the context
of our tripartite graph $G=(A,B,C;E)$, which would allow us to complete the
proof of Theorem 1 by constructing a packing as before.

It was shown in Section 2 that a (uniform) $\mathcal{T}$-transversal of $G$
corresponds to a set of edges $E^{\prime}_{BC}\subseteq E_{BC}$ and subsets
$B^{\prime}\subseteq B$, $C^{\prime}\subseteq C$ such that $W=B^{\prime}\cup
C^{\prime}$ is a vertex cover of $G[E_{BC}\setminus E^{\prime}_{BC}]$. If we
let $B^{\prime\prime}=B\setminus B^{\prime}$ and $C^{\prime\prime}=C\setminus
C^{\prime}$, then
$E_{B^{\prime\prime}C^{\prime\prime}}=\partial(B^{\prime\prime})\cap\partial(C^{\prime\prime})\subseteq
E^{\prime}_{BC}$ is precisely the set of edges in $G[B\cup C]$ that are _not_
covered by $B^{\prime}\cup C^{\prime}$, so
$E_{B^{\prime\prime}C^{\prime\prime}}\cup E_{AW}$ is a
$\mathcal{T}$-transversal of $G$ of size

$|E_{B^{\prime\prime}C^{\prime\prime}}|+p|W|\leq|E^{\prime}_{BC}|+p|W|.$

Conversely, for any $B^{\prime\prime}\subseteq B$ and
$C^{\prime\prime}\subseteq C$, define $B^{\prime}=B\setminus
B^{\prime\prime}$, $C^{\prime}=C\setminus C^{\prime\prime}$, and
$W=B^{\prime}\cup C^{\prime}$. So $W$ is a vertex cover of $E_{BC}\setminus
E_{B^{\prime\prime}C^{\prime\prime}}$, and
$E_{B^{\prime\prime}C^{\prime\prime}}\cup E_{AW}$ is a uniform
$\mathcal{T}$-transversal of $G$.

Therefore the minimum value of

$|\partial(B^{\prime\prime})\cap\partial(C^{\prime\prime})|+p\left(|B|+|C|-|B^{\prime\prime}|-|C^{\prime\prime}|\right)=|E_{B^{\prime\prime}C^{\prime\prime}}|+p|B^{\prime}\cup
C^{\prime}|$

over all $B^{\prime\prime}\subseteq B$ and $C^{\prime\prime}\subseteq C$ is
the minimum size of a uniform $\mathcal{T}$-transversal, which is
$\tau_{\triangle}(G)$.

Acknowledgements  We would like to thank You Rao for her translation of Mao
Cheng’s paper into English, and Donovan Hare for helpful comments on this
manuscript.

Conflict of interest  The authors declare that they have no conflict of
interest.

## References

  * [1] Cai, Mao Cheng: Edge-disjoint Matchings in a Bipartite Graph. (Chinese) J. Systems Sci. Math. Sci. 3, no. 1, 71–73 (1983)
  * [2] De Sousa, J.: Disjoint Common Transversals. In: Bose, R. C., Dowling, T. A. Combinatorial Mathematics and its Applications, pp. 87–94. Academic Press, London (1971)
  * [3] Haxell, P. E., Kohayakawa, Y.: Packing and Covering Triangles in Tripartite Graphs. Graphs Combin. 14, no. 1, 1–10 (1998)
  * [4] König, Dénes.: Graphok és alkalmazásuk a determinánsok és a halmazok elméletére. Mathematikai És Természettudományi Értesitö. 34, 104–119 (1916)
  * [5] Lakshmanan, S. A., Bujtás, Cs., Tuza, Zs.: Small Edge Sets Meeting All Triangles of a Graph. Graphs Combin. 28, no. 3, 381–392 (2012)
  * [6] Menger, K.: Zur Allgemeinen Kurventheorie. Fund. Math. 10, 96–115 (1927)
  * [7] Ore, O.: Theory of Graphs. American Mathematical Society Colloquium Publications, vol. 38. American Mathematical Society, Providence, RI (1962)
  * [8] Perfect, H.: Applications of Menger’s Graph Theorem. J. Math. Anal. Appl. 22, 96–111 (1968)
  * [9] Rao, Y.: Maximum Packings in Tripartite Graphs. Master’s thesis, University of British Columbia (2017)
  * [10] Tuza, Zs.: Conjecture in: finite and infinite sets. In: Proc. Colloq. Math. Soc. J. Bolyai (Eger, Hungary, 1981), vol. 37, p.888. North-Holland, Amsterdam (1984)
  * [11] West, D. B.: Introduction to Graph Theory. Prentice Hall, Upper Saddle River (1996)