Sequential composition of propositional logic programs

Christian Antić [email protected]
Vienna, Austria

Abstract.

This paper introduces and studies the sequential composition and decomposition of propositional logic programs. We show that acyclic programs can be decomposed into single-rule programs and provide a general decomposition result for arbitrary programs. We show that the immediate consequence operator of a program can be represented via composition which allows us to compute its least model without any explicit reference to operators. This bridges the conceptual gap between the syntax and semantics of a propositional logic program in a mathematically satisfactory way.

1. Introduction

Rule-based reasoning is an essential part of human intelligence prominently formalized in artificial intelligence research via logic programs (cf. ?, ?, ?, ?, ?, ?). Logic programming is a well-established subfield of theoretical computer science and AI with applications to such diverse fields as expert systems, database theory, diagnosis, planning, learning, natural language processing, and many others (cf. ?, ?, ?, ?).

The propositional Horn fragment studied in this paper is particularly relevant in database theory via the query language datalog (cf. ?) and in answer set programming (?), a prominent and successful dialect of logic programming incorporating negation as failure (?) and many other constructs such as aggregates (cf. ?, ?), external sources (?), and description logic atoms (?).

Describing complex programs as the composition of simpler ones is a common strategy in computer programming and logic programming is no exception as is witnessed by the large amount of research on modular logic programming in the 1980s and 1990s (e.g. ?, ?, ?, ?, ?, ?, ?, ?, ?, ?, ?), and more recently on modular answer set programming (e.g. ?, ?, ?).

The purpose of this paper is to add to the logic programmer’s repertoire another modularity operation in the form of the sequential composition of propositional logic programs, which is naturally induced by their rule-like structure. The close relationship to the modularity operations introduced in ? (?) and ? (?) is discussed in detail in §7.

The motivation for introducing a novel operation is because we feel the need for a syntactic composition operation complementing the semantic ones from the literature¹¹1This is partly motivated by recent work on algebraic logic program synthesis via analogical proportions in ? (?). — in §7 we show that the semantic composition operators can be recovered from the syntactic one (but not vice versa which is evident from their definition). Thus, in a sense, syntactic composition is more fundamental than its semantic counterpart.

The main results of this paper can be summarized as follows:

(1)

We introduce the sequential composition of propositional logic programs and show that the space of all propositional logic programs over some fixed alphabet is closed under composition which means that composition is a total function defined for all pairs of programs. Composition is in general non-associative (Example 10). The composition of propositional Krom programs consisting only of rules with at most one body atom is associative and gives rise to the algebraic structure of a monoid, and the restricted class of proper propositional Krom programs consisting only of rules with exactly one body atom yields an idempotent semiring (Theorem 12).
(2)

In §5, we study decompositions of programs. The main results here are that acyclic programs (cf. ?) can be decomposed into a product of single-rule programs (Theorem 31), followed by some general results on decompositions of programs in §5.4.
(3)

On the semantic side, the van Emden-Kowalski immediate consequence operator $T_{P}$ is at the core of logic programming and we show that it can be represented via composition (Theorem 35), which allows us to compute its least model semantics without any explicit reference to operators (Theorem 40). This bridges the conceptual gap between the syntax and semantics of a propositional logic program in a mathematically satisfactory way.

In a broader sense, this paper is a further step towards an algebra of logic programs and in the future we plan to adapt and generalize the methods of this paper to wider classes of programs, most importantly to first-, and higher-order logic programs (?, ?, ?, ?), and non-monotonic logic programs under the stable model (?) or answer set semantics and extensions thereof (cf. ?, ?, ?, ?) — see ? (?).

2. Preliminaries

In this section, we first recall the algebraic structures occurring in the rest of the paper, and then we recall the syntax and semantics of propositional logic programs.

2.1. Algebraic Structures

We recall some basic algebraic notions and notations by mainly following the lines of ? (?).

Given two sets $A$ and $B$ , we write $A\subseteq_{k}B$ in case $A$ is a subset of $B$ with $k$ elements, for some non-negative integer $k$ .We denote the identity function on a set $A$ by $Id_{A}$ . A permutation of a set $A$ is any mapping $A\to A$ which is one-to-one and onto. We denote the composition of two functions $f:A\to A$ and $g:A\to A$ by $f\circ g$ with the usual definition $(f\circ g)(x)=f(g(x))$ .

We call a binary relation $\leq$ reflexive if $x\leq x$ , anti-symmetric if $x\leq y$ and $y\leq x$ implies $x=y$ , and transitive if $x\leq y$ and $y\leq z$ implies $x\leq z$ , for all $x,y,z$ . A partially ordered set (or poset) is a set $L$ together with a reflexive, transitive, and anti-symmetric binary relation $\leq$ on $L$ . A prefixed point of an operator $f$ on a poset $L$ is any element $x\in L$ such that $f(x)\leq x$ ; moreover, we call any $x\in L$ a fixed point of $f$ if $f(x)=x$ .

A magma is a set $M$ together with a binary operation $\cdot$ on $M$ . We call $(M,\cdot,1)$ a unital magma if it contains a unit element 1 such that $1x=x1=x$ holds for all $x\in M$ . A semigroup is a magma $(S,\cdot)$ in which $\cdot$ is associative. A monoid is a semigroup containing a unit element 1 such that $1x=x1=x$ holds for all $x$ . A group is a monoid which contains an inverse $x^{-1}$ for every $x$ such that $xx^{-1}=x^{-1}x=1$ . A left (resp., right) zero is an element $0$ such that $0x=0$ (resp., $x0=0$ ) holds for all $x\in S$ . An ordered semigroup is a semigroup $S$ together with a partial order $\leq$ that is compatible with the semigroup operation, meaning that $x\leq y$ implies $zx\leq zy$ and $xz\leq yz$ for all $x,y,z\in S$ . An ordered monoid is defined in the obvious way. A non-empty subset $I$ of $S$ is called a left (resp., right) ideal if $SI\subseteq I$ (resp., $IS\subseteq I$ ), and a (two-sided) ideal if it is both a left and right ideal. An element $x\in S$ is idempotent if $x\cdot x=x$ .

A seminearring is a set $S$ together with two binary operations $+$ and $\cdot$ on $S$ , and a constant $0\in S$ , such that $(S,+,0)$ is a monoid and $(S,\cdot)$ is a semigroup satisfying the following laws:

(1)

$(x+y)\cdot z=x\cdot z+y\cdot z$ for all $x,y,z\in S$ (right-distributivity); and
(2)

$0\cdot x=0$ for all $x\in S$ (left zero).

We say that $S$ is idempotent if $x+x=x$ holds for all $x\in S$ . Typical examples of seminearrings are given by the set of all mappings on a monoid together with composition of mappings, point-wise addition of mappings, and the zero function.

A semiring is a seminearring $(S,+,\cdot,0)$ such that $+$ is commutative and additionally to the laws of a seminearring the following laws are satisfied:

(1)

$x\cdot(y+z)=x\cdot y+x\cdot z$ for all $x,y,z\in S$ (left-distributivity); and
(2)

$x\cdot 0=0$ for all $x\in S$ (right zero).

For example, $(\mathbb{N},+,\cdot,0)$ and $(2^{A},\cup,\cap,\emptyset)$ are semirings.

2.2. Propositional Logic Programs

We recall the syntax and semantics of propositional logic programs.

2.2.1. Syntax

In the rest of the paper, $A$ denotes a finite alphabet of propositional atoms.

A (propositional Horn logic) program over $A$ is a finite set of rules of the form

(1)

\displaystyle a_{0}\leftarrow a_{1},\ldots,a_{k},\quad k\geq 0,

where $a_{0},\ldots,a_{k}\in A$ are propositional atoms. It will be convenient to define, for a rule $r$ of the form (1),

\displaystyle h(r):=\{a_{0}\}\quad\text{and}\quad b(r):=\{a_{1},\ldots,a_{k}\}

extended to programs by

\displaystyle h(P):=\bigcup_{r\in P}h(r)\quad\text{and}\quad b(P):=\bigcup_{r\in P}b(r).

In this case, the size of $r$ is $k$ and denoted by $sz(r)$ .

A fact is a rule with empty body and a proper rule is a rule which is not a fact. We denote the facts and proper rules in $P$ by $f(P)$ and $p(P)$ , respectively.

We call a rule $r$ of the form (1) Krom²²2Krom rules were first introduced and studied by (?) and are sometimes called “binary” in the literature; we prefer “Krom” here since we reserve “binary” for programs with two body atoms. if it has at most one body atom, and we call $r$ binary if it contains at most two body atoms. A tautology is any Krom rule of the form $a\leftarrow a$ , for $a\in A$ . We call a program Krom if it contains only Krom rules, and we call it binary if it consists only of binary rules.

A program is called a single-rule program if it contains exactly one non-tautological rule.

We call a program minimalist if it contains at most one rule for each rule head.

Given two programs $P$ and $R$ , we say that $P$ depends on $R$ if the intersection of $b(P)$ and $h(R)$ is not empty.

We call $P$ acyclic if there is a mapping $\ell:A\to\{0,1,2,\ldots\}$ such that for each rule $r\in P$ , we have $\ell(h(r))>\ell(b(r))$ , and in this case we call $\ell$ a level mapping for $P$ . Of course, every level mapping $\ell$ induces an ordering on rules via $r\leq_{\ell}s$ if $\ell(h(r))\leq\ell(h(s))$ . We can transform this ordering into a total ordering by arbitrarily choosing a particular linear ordering within each level, that is, if $\ell(a)=\ell(b)$ then we can choose between $a<_{\ell}b$ or $b<_{\ell}a$ .

Example 1.

The program

\displaystyle P:=\left\{\begin{array}[]{l}a\\ b\leftarrow a\\ c\leftarrow a,b\end{array}\right\}

is acyclic with level mapping $\ell(a)=0$ , $\ell(b)=1$ , $\ell(c)=2$ . Adding the rule $a\leftarrow c$ to $P$ yields a non-acyclic program since $\ell(a)\not>\ell(c)$ .

Define the dual of $P$ by

\displaystyle P^{d}:=f(P)\cup\{b\leftarrow h(r)\mid r\in p(P),b\in b(r)\}.

Roughly, we obtain the dual of a program by reversing all the arrows of its proper rules.

2.2.2. Semantics

An interpretation is any set of atoms from $A$ . We define the entailment relation, for every interpretation $I$ , inductively as follows: (i) for an atom $a$ , $I\models a$ if $a\in I$ ; (ii) for a set of atoms $B$ , $I\models B$ if $B\subseteq I$ ; (iii) for a rule $r$ of the form (1), $I\models r$ if $I\models b(r)$ implies $I\models h(r)$ ; and, finally, (iv) for a propositional logic program $P$ , $I\models P$ if $I\models r$ holds for each rule $r\in P$ . In case $I\models P$ , we call $I$ a model of $P$ . The set of all models of $P$ has a least element with respect to set inclusion called the least model of $P$ and denoted by $LM(P)$ . We say that $P$ and $R$ are equivalent if $LM(P)=LM(R)$ .

Define the van Emden-Kowalski operator of $P$ , for every interpretation $I$ , by

\displaystyle T_{P}(I):=\{h(r)\mid r\in P:I\models b(r)\}.

The van Emden-Kowalski operator is at the core of logic programming since we have the following well-known operational characterization of models (?):

Proposition 2.

An interpretation $I$ is a model of $P$ iff $I$ is a prefixed point of $T_{P}$ .

We call an interpretation $I$ a supported model of $P$ if $I$ is a fixed point of $T_{P}$ . We say that $P$ and $R$ are subsumption equivalent (?) if $T_{P}=T_{R}$ , denoted by $P\equiv_{ss}R$ .

The least fixed point computation of $T_{P}$ is defined by

	$\displaystyle T_{P}^{0}=\emptyset,$
	$\displaystyle T_{P}^{n+1}=T_{P}(T_{P}^{n}),$
	$\displaystyle T_{P}^{\infty}=\bigcup_{n\geq 0}T_{P}^{n}.$

The following constructive characterization of least models is due to (?).

Proposition 3.

The least model of a propositional logic program coincides with the least fixed point of its associated van Emden-Kowalski operator, that is, for any program $P$ we have

(2)

\displaystyle LM(P)=T_{P}^{\infty}.

Example 4.

Reconsider the program $P$ of Example 1. Intuitively, we expect the least model of $P$ to include all the atoms $a,b,$ and $c$ . The following least fixed point computation shows that this is indeed the case:

	$\displaystyle T_{P}(\emptyset)=\{a\}$
	$\displaystyle T_{P}(\{a\})=\{a,b\}$
	$\displaystyle T_{P}(\{a,b\})=\{a,b,c\}$
	$\displaystyle T_{P}(\{a,b,c\})=\{a,b,c\}.$

3. Sequential Composition

We are interested in the algebraic structure of the space of all propositional logic programs. For this we define the sequential composition operation on programs and show in Theorem 9 that the so-obtained space is closed under such compositions. This will allow us later to decompose programs into simpler ones (§5), to represent the immediate consequence operator on syntactic level (§6.1), and to define an algebraic semantics of programs without any explicit reference to operators (§6.2).

Notation 5.

In the rest of the paper, $P$ and $R$ denote propositional logic programs over some joint alphabet $A$ .

We are ready to introduce the main notion of the paper.

Definition 6.

We define the (sequential) composition of $P$ and $R$ by

\displaystyle P\circ R=\left\{h(r)\leftarrow b(S)\;\middle|\;r\in P,S\subseteq_{sz(r)}R,h(S)=b(r)\right\}.

We will write $PR$ in case the composition operation is understood.

Roughly, we obtain the composition of $P$ and $R$ by resolving all body atoms in $P$ with ‘matching’ rule heads of $R$ . The following example shows why we use $\subseteq_{sz(r)}$ instead of $\subseteq$ in the above definition.

Example 7.

Let $r$ and $R$ be given by

\displaystyle r:=a\leftarrow b\quad\text{and}\quad R:=\left\{\begin{array}[]{l}b\leftarrow c\\ b\leftarrow d\end{array}\right\}.

Since $r$ consists of a single body atom, we have $sz(r)=1$ . This means that $\{r\}\circ R$ consists of all rules $a\leftarrow b(S)$ so that $S\subseteq_{1}R$ (i.e., $S$ consists of a single rule) and $h(S)=\{b\}$ . This yields

\displaystyle\{r\}\circ R=\left\{\begin{array}[]{l}a\leftarrow c\\ a\leftarrow d\end{array}\right\}.

This coincides with what we intuitively expect from the composition of $r$ and $R$ . On the other hand, if we define composition using $\subseteq$ instead of $\subseteq_{sz(r)}$ , then the above requirement changes to $S\subseteq R$ such that $h(S)=\{b\}$ , which means that we can now put $S=R$ adding the undesired rule $a\leftarrow b(S)=a\leftarrow c,d$ to $\{r\}\circ R$ .

Notice that we can reformulate sequential composition as

(3)

\displaystyle P\circ R=\bigcup_{r\in P}(\{r\}\circ R),

which directly implies right-distributivity of composition, that is,

(4)

\displaystyle(P\cup Q)\circ R=(P\circ R)\cup(Q\circ R)\quad\text{holds for all propositional logic programs }P,Q,R.

Example 8.

The following counter-example shows that left-distributivity fails in general:

\displaystyle\{a\leftarrow b,c\}\circ(\{b\}\cup\{c\})=\{a\}\quad\text{whereas}\quad(\{a\leftarrow b,c\}\circ\{b\})\cup(\{a\leftarrow b,c\}\circ\{c\})=\emptyset.

We can write $P$ as the union of its facts and proper rules, that is,

(5)

\displaystyle P=f(P)\cup p(P).

Hence, we can rewrite the composition of $P$ and $R$ as

(6)

\displaystyle PR

\displaystyle=(f(P)\cup p(P))R\stackrel{{\scriptstyle(\ref{equ:(P_cup_Q)_circ_R})}}{{=}}f(P)R\cup p(P)R=f(P)\cup p(P)R,

which shows that the facts in $P$ are preserved by composition, that is, we have

(7)

\displaystyle f(P)\subseteq f(PR).

The facts of the composition of to two programs is given by

\displaystyle f(PR)\stackrel{{\scriptstyle(\ref{equ:facts_proper})}}{{=}}f(f(P)\cup p(P)R)=f(f(P))\cup f(p(P)R)=f(P)\cup p(P)f(R).

We can compute the heads and bodies via

(8)

\displaystyle h(P)=PA\quad\text{and}\quad b(P)=p(P)^{d}A.

Moreover, we have

\displaystyle h(PR)\subseteq h(P)\quad\text{and}\quad b(PR)\subseteq b(R).

Define the unit program (over $A$ ) by the propositional Krom program

\displaystyle 1_{A}:=\{a\leftarrow a\mid a\in A\}.

In the sequel, we will often omit the reference to $A$ .

We are now ready to state the main structural result of the paper:

Theorem 9.

The space of all propositional logic programs over some fixed alphabet forms a finite unital magma with respect to composition ordered by set inclusion with the neutral element given by the unit program. Moreover, the empty program is a left zero and composition distributes from the right over union, that is, for any programs $P,Q,R$ we have

(9)	$\displaystyle P1$	$\displaystyle=1P=P$
(10)	$\displaystyle\emptyset P$	$\displaystyle=\emptyset$
(11)	$\displaystyle(P\cup R)Q$	$\displaystyle=(PQ)\cup(RQ).$

Proof.

The space of all propositional logic programs is obviously closed under composition, which shows that it forms a magma.

We proceed by proving that 1 is neutral with respect to composition. By definition of composition, we have

\displaystyle P1

\displaystyle=\{h(r)\leftarrow b(S)\mid r\in P,S\subseteq_{sz(r)}1,h(S)=b(r)\}.

Now, by definition of 1 and $S\subseteq_{sz(r)}1$ , we have $h(S)=b(S)$ and therefore $b(S)=b(r)$ . Hence,

\displaystyle P1=P.

Similarly, we have

\displaystyle 1P

\displaystyle=\{h(r)\leftarrow b(S)\mid r\in 1,S\subseteq_{1}P,h(S)=b(r)\}.

As $S$ is a subset of $P$ with a single element, $S$ is a singleton $S=\{s\}$ , for some rule $s$ with $h(s)=b(r)$ and, since $b(r)=h(r)$ holds for every rule in 1, $h(s)=h(r)$ . Hence,

	$\displaystyle 1P$	$\displaystyle=\{h(r)\leftarrow b(s)\mid r\in 1,s\in P,h(s)=b(r)\}$
		$\displaystyle=\{h(s)\leftarrow b(s)\mid s\in P\}$
		$\displaystyle=P.$

This shows that 1 is neutral with respect to composition. That composition is ordered by set inclusion is obvious. We now turn our attention to the operation of union. In (4) we argued for the right-distributivity of composition. That the empty set is a left zero is obvious. As union is idempotent, the set of all propositional logic programs forms the structure of a finite idempotent seminearring. ∎

The following example shows that, unfortunately, composition is not associative.³³3In Theorem 11 we will see that composition is associative for minimalist programs and in Corollary 36 we will see that it is associative modulo subsumption equivalence.

Example 10.

Consider the rule

\displaystyle r:=a\leftarrow b,c

and the programs

\displaystyle P:=\left\{\begin{array}[]{l}b\leftarrow b\\ c\leftarrow b,c\end{array}\right\}\quad\text{and}\quad R:=\left\{\begin{array}[]{l}b\leftarrow d\\ b\leftarrow e\\ c\leftarrow f\end{array}\right\}.

Let us compute $(\{r\}P)R$ . We first compute $\{r\}P$ by noting that the rule $r$ has two body atoms and has therefore size 2, which means that there is only a single choice of subprogram $S$ of $P$ with two rules, namely $S=P$ ; this yields

\displaystyle\{r\}P=\{h(r)\leftarrow b(P)\}=\{a\leftarrow b,c\}=\{r\}.

Next we compute $(\{r\}P)R=\{r\}R$ by noting that now there are two possible $S_{1},S_{2}\subseteq_{2}R$ with $h(S_{1})=h(S_{2})=b(r)$ , given by

\displaystyle S_{1}=\left\{\begin{array}[]{l}b\leftarrow d\\ c\leftarrow f\end{array}\right\}\quad\text{and}\quad S_{2}=\left\{\begin{array}[]{l}b\leftarrow e\\ c\leftarrow f\end{array}\right\}.

This yields

\displaystyle\{r\}R=\left\{\begin{array}[]{l}h(r)\leftarrow b(S_{1})\\ h(r)\leftarrow b(S_{2})\end{array}\right\}=\left\{\begin{array}[]{l}a\leftarrow d,f\\ a\leftarrow e,f\end{array}\right\}.

Let us now compute $\{r\}(PR)$ . We first compute $PR$ . By (3) we have

\displaystyle PR=\{b\leftarrow b\}R\cup\{c\leftarrow b,c\}R.

We easily obtain

\displaystyle\{b\leftarrow b\}R=\left\{\begin{array}[]{l}b\leftarrow d\\ b\leftarrow e\end{array}\right\}.

Similar computations as above show

\displaystyle\{c\leftarrow b,c\}R=\left\{\begin{array}[]{l}c\leftarrow d,f\\ c\leftarrow d,e\end{array}\right\}.

So in total we have

\displaystyle PR=\left\{\begin{array}[]{l}b\leftarrow d\\ b\leftarrow e\\ c\leftarrow d,f\\ c\leftarrow d,e\end{array}\right\}.

To compute $\{r\}(PR)$ , we therefore see that there are four two rule subprograms $S_{1},S_{2},S_{4},S_{4}\subseteq_{2}PR$ with $b$ or $c$ in their heads given by

\displaystyle S_{1}=\left\{\begin{array}[]{l}b\leftarrow d\\ c\leftarrow d,f\end{array}\right\}\qquad S_{2}=\left\{\begin{array}[]{l}b\leftarrow d\\ c\leftarrow d,e\end{array}\right\}\qquad S_{3}=\left\{\begin{array}[]{l}b\leftarrow e\\ c\leftarrow d,f\end{array}\right\}\qquad S_{4}=\left\{\begin{array}[]{l}b\leftarrow e\\ c\leftarrow d,f\end{array}\right\}.

Hence, we have

\displaystyle\{r\}PR=\left\{\begin{array}[]{l}h(r)\leftarrow b(S_{1})\\ h(r)\leftarrow b(S_{2})\\ h(r)\leftarrow b(S_{3})\\ h(r)\leftarrow b(S_{4})\end{array}\right\}=\left\{\begin{array}[]{l}a\leftarrow d,f\\ a\leftarrow d,e\\ a\leftarrow d,e,f\end{array}\right\}.

We have thus shown

\displaystyle\{r\}(PR)=\left\{\begin{array}[]{l}a\leftarrow d,f\\ a\leftarrow e,f\\ a\leftarrow d,e,f\\ \end{array}\right\}\neq\left\{\begin{array}[]{l}a\leftarrow d,f\\ a\leftarrow e,f\end{array}\right\}=(\{r\}P)R.

4. Restricted Classes of Programs

Now that we have a basic understanding of the sequential composition of programs, we continue by studying composition in some restricted classes of programs like minimalist (§4.1) and Krom programs (§4.2) where we find that associativity holds. Having a basic understanding of those restricted classes of programs will be useful later when we deal with decompositions of programs where factors of programs often have one of those restricted forms.

4.1. Minimalist Programs

Recall that we call a program minimalist if it contains at most one rule for each head atom. Theorem 11 shows that minimalist programs satisfy a form of associativity.

Given a minimalist program $M$ , in the computation of $P\circ M$ we can omit the reference to $r$ in $\subseteq_{sz(r)}$ in Definition 6, that is, we have

\displaystyle P\circ M=\{h(r)\leftarrow b(S)\mid r\in P,S\subseteq M,h(S)=b(r)\}.

In Example 10 we have seen that composition is not associative in general. The situation changes for minimalist programs.

Theorem 11.

For any programs $P,M,N$ if $M$ and $N$ are minimalist, then

(12)

\displaystyle(PM)N=P(MN).

Proof.

As a consequence of (3), a rule $r$ is in $(PM)N$ iff

(19)

\displaystyle\{r\}=\left(\{a_{0}\leftarrow a_{1},\ldots,a_{k}\}\circ\left\{\begin{array}[]{l}a_{1}\leftarrow B_{1}\\ \vdots\\ a_{k}\leftarrow B_{k}\end{array}\right\}\right)\circ\left\{\begin{array}[]{l}b_{1}\leftarrow C_{1}\\ \vdots\\ b_{m}\leftarrow C_{m}\end{array}\right\},

for some rules $a_{0}\leftarrow a_{1},\ldots,a_{k}\in P$ , $k\geq 0$ , $b_{1}\leftarrow B_{1},\ldots,b_{k}\leftarrow B_{k}\in M$ , $b_{1}\leftarrow C_{1},\ldots,b_{m}\leftarrow C_{m}\in N$ , and $B_{1}\cup\ldots\cup B_{k}=\{b_{1},\ldots,b_{m}\}$ , $m\geq 0$ . Since

\displaystyle\left\{\begin{array}[]{l}a_{1}\leftarrow B_{1}\\ \vdots\\ a_{k}\leftarrow B_{k}\end{array}\right\}\quad\text{and}\quad\left\{\begin{array}[]{l}b_{1}\leftarrow C_{1}\\ \vdots\\ b_{m}\leftarrow C_{m}\end{array}\right\}

are minimalist, we can rewrite (19) as

\displaystyle\{r\}=\{a_{0}\leftarrow a_{1},\ldots,a_{k}\}\circ\left(\left\{\begin{array}[]{l}a_{1}\leftarrow B_{1}\\ \vdots\\ a_{k}\leftarrow B_{k}\end{array}\right\}\circ\left\{\begin{array}[]{l}b_{1}\leftarrow C_{1}\\ \vdots\\ b_{m}\leftarrow C_{m}\end{array}\right\}\right),

which shows $r\in P(MN)$ . The proof that every rule in $P(MN)$ is in $(PM)N$ is analogous. ∎

4.2. Krom Programs

Recall that we call a program Krom if it contains only rules with at most one body atom. This includes interpretations, unit programs, and permutations. Krom programs often appear as factors in decompositions of programs and it is therefore beneficial to know their basic algebraic properties (Theorem 12). First notice that for any Krom program $K$ and any program $P$ , composition simplifies to

\displaystyle K\circ P=f(K)\cup\{a\leftarrow B\mid a\leftarrow b\in p(K)\text{ and }b\leftarrow B\in P\}.

We have the following structural result as a specialization of Theorem 9:

Theorem 12.

The space of all propositional Krom programs forms a monoid with respect to composition with the neutral element given by the unit program, and it forms a seminearring with respect to sequential composition and union. More generally, we have

(20)

\displaystyle K(PR)=(KP)R,

for arbitrary programs $P$ and $R$ . Moreover, Krom programs distribute from the left, that is, for any programs $P$ and $R$ , we have

(21)

\displaystyle K(P\cup R)=KP\cup KR.

This implies that the space of proper propositional Krom programs forms a finite idempotent semiring.

Proof.

We first prove (20), which implies associativity for propositional Krom programs. A rule $r$ is in $K(PR)$ iff either $r=a\in K$ , in which case we have $r\in(KP)R$ , or

\displaystyle\{r\}=\{a\leftarrow b\}\circ\left(\{b\leftarrow b_{1},\ldots,b_{k}\}\circ\left\{\begin{array}[]{l}b_{1}\leftarrow B_{1}\\ \vdots\\ b_{k}\leftarrow B_{k}\end{array}\right\}\right),

for some $a\leftarrow b\in K$ , $b\leftarrow b_{1},\ldots,b_{k}\in P$ , and $b_{1}\leftarrow B_{1},\ldots,b_{k}\leftarrow B_{k}\in R$ , in which case we have $r=a\leftarrow B_{1}\cup\ldots\cup B_{k}$ . A simple computation shows

\displaystyle\{r\}=(\{a\leftarrow b\}\circ\{b\leftarrow b_{1},\ldots,b_{k}\})\circ\left\{\begin{array}[]{l}b_{1}\leftarrow B_{1}\\ \vdots\\ b_{k}\leftarrow B_{k}\end{array}\right\}.

The proof that every rule in $(KP)R$ is in $K(PR)$ is analogous.

We now want to prove (21). For any proper Krom rule $r=a\leftarrow b$ , we have

	$\displaystyle\{a\leftarrow b\}\circ(P\cup R)$	$\displaystyle=\{a\leftarrow B\mid b\leftarrow B\in P\cup R,B\subseteq A\}$
		$\displaystyle=\{a\leftarrow B\mid b\leftarrow B\in P\}\cup\{a\leftarrow B\mid b\leftarrow B\in R\}$
		$\displaystyle=(\{a\leftarrow b\}\circ P)\cup(\{a\leftarrow b\}\circ R).$

Hence, we have

	$\displaystyle K(P\cup R)$	$\displaystyle\stackrel{{\scriptstyle(\ref{equ:facts_proper})}}{{=}}f(K)\cup p(K)(P\cup R)$
		$\displaystyle\stackrel{{\scriptstyle(\ref{equ:bigcup})}}{{=}}f(K)\cup\bigcup_{r\in p(K)}\{r\}(P\cup R)$
		$\displaystyle=f(K)\cup\bigcup_{r\in p(K)}(\{r\}P\cup\{r\}R)$
		$\displaystyle=f(K)\cup\bigcup_{r\in p(K)}\{r\}P\cup\bigcup_{r\in p(K)}\{r\}R$
		$\displaystyle=f(K)\cup p(K)P\cup p(K)R$
		$\displaystyle=(f(K)\cup p(K)P)\cup(f(K)\cup p(K)R)$
		$\displaystyle=KP\cup KR$

where the sixth identity follows from the idempotency of union. This shows that Krom programs distribute from the left which implies that the space of all proper⁴⁴4If $K$ contains facts, then $K\emptyset=f(K)\neq\emptyset$ violates the last axiom of a semiring (cf. Section 2.1). Krom programs forms a semiring (cf. Theorem 9). ∎

4.2.1. Interpretations

Notice that, formally, interpretations are Krom programs containing only rules with empty bodies called facts, which gives interpretations a special compositional meaning.

Fact 13.

Every interpretation $I$ is a left zero, that is, for any program $P$ , we have

(22)

\displaystyle IP=I.

Consequently, the space of interpretations forms a right ideal.⁵⁵5See Corollary 38.

Corollary 14.

A program $P$ commutes with an interpretation $I$ iff $I$ is a supported model of $P$ , that is,

\displaystyle PI=IP\quad\Leftrightarrow\quad I\in Supp(P).

Proof.

A direct consequence of Fact 13 and the forthcoming Theorem 35 (which is not depending on this result). ∎

4.2.2. Permutations

With every permutation $\pi:A\to A$ , we associate the propositional Krom program

\displaystyle\pi=\{\pi(a)\leftarrow a\mid a\in A\}.

We adopt here the standard cycle notation for permutations. For instance, we have

\displaystyle\pi_{(a\,b)}=\left\{\begin{array}[]{l}a\leftarrow b\\ b\leftarrow a\end{array}\right\}\quad\text{and}\quad\pi_{(a\,b\,c)}=\left\{\begin{array}[]{l}a\leftarrow b\\ b\leftarrow c\\ c\leftarrow a\end{array}\right\}.

The inverse $\pi^{-1}$ of $\pi$ translates into the language of programs as

\displaystyle\pi^{-1}=\pi^{d}.

Interestingly, we can rename the atoms occurring in a program via permutations and composition by

\displaystyle\pi\circ P\circ\pi^{d}=\{\pi(h(r))\leftarrow\pi(b(r))\mid r\in P\}.

We have the following structural result as a direct instance of the more general result for permutations:

Fact 15.

The space of all permutation programs forms a group.

4.3. Reducts

Reducing a program to a restricted alphabet is a fundamental operation on programs which we will often use in the rest of the paper, especially in §5. For example, in Corollary 18 we will see that the computation of composition can be simplified using reducts. This motivates the following definition.

Definition 16.

We define the left and right reduct⁶⁶6Our notion of right reduct coincides with the FLP reduct (?) well-known in answer set programming. of a program $P$ , with respect to some interpretation $I$ , respectively by

{}^{I}P:=\{r\in P\mid I\models h(r)\}\quad\text{and}\quad P^{I}:=\{r\in P\mid I\models b(r)\}.

Our first observation is that we can compute the facts of $P$ via the right reduct with respect to the empty set, that is, we have

(23)

\displaystyle f(P)=P^{\emptyset}=P\emptyset.

On the contrary, computing the left reduct with respect to the empty set yields

(24)

\displaystyle^{\emptyset}P=\emptyset.

Moreover, for any interpretations $I$ and $J$ , we have

(25)

\displaystyle^{J}I=I\cap J\quad\text{and}\quad I^{J}=I.

Notice that we obtain the reduction of $P$ to the atoms in $I$ , denoted $P|_{I}$ , by

(26)

\displaystyle P|_{I}={{}^{I}}(P^{I})=(^{I}P)^{I}.

As the order of computing left and right reducts is irrelevant, in the sequel we will omit the parentheses in (26). Of course, we have

{}^{A}P=P^{A}={{}^{A}}P^{A}=P.

Moreover, we have

(27)	$\displaystyle 1^{I}$	$\displaystyle={{}^{I}}1={{}^{I}}1^{I}=1_{I}=1\|_{I}$
(28)	$\displaystyle 1^{I}\circ 1^{J}$	$\displaystyle=1^{I\cap J}=1^{J}\circ 1^{I}=1^{I}\cap 1^{J}$
(29)	$\displaystyle 1^{I}\cup 1^{J}$	$\displaystyle=1^{I\cup J}.$

We now want to relate reducts to composition and union.

Proposition 17.

For any program $P$ and interpretation $I$ , we have

(30)

\displaystyle^{I}P=1^{I}\circ P\quad\text{and}\quad P^{I}=P\circ 1^{I}.

Moreover, we have

(31)

\displaystyle P|_{I}=1^{I}\circ P\circ 1^{I}.

Consequently, for any program $R$ , we have

(32)		$\displaystyle^{I}(P\cup R)={{}^{I}}P\cup{{}^{I}}R$	$\displaystyle\quad\text{and}\quad{{}^{I}}(PR)={{}^{I}}PR$
(33)		$\displaystyle(P\cup R)^{I}=P^{I}\cup R^{I}$	$\displaystyle\quad\text{and}\quad(PR)^{I}=PR^{I}.$

Proof.

We compute

	$\displaystyle 1^{I}\circ P$	$\displaystyle=\{h(r)\leftarrow b(s)\mid r\in 1^{I},s\in P,h(s)=b(r)\}$
		$\displaystyle=\{h(r)\leftarrow b(s)\mid r\in 1,s\in P,h(s)=b(r),h(r)=b(r)\in I\}$
		$\displaystyle=\{h(s)\leftarrow b(s)\mid s\in P,h(s)\in I\}$
		$\displaystyle=\{s\in P\mid I\models h(s)\}$
		$\displaystyle={{}^{I}}P.$

Similarly, we compute

(34)		$\displaystyle P\circ 1^{I}$	$\displaystyle=\{h(r)\leftarrow b(S)\mid r\in P,S\subseteq_{sz(r)}1^{I},h(S)=b(r)\}$
(38)			$\displaystyle=\left\{h(r)\leftarrow b(S)\;\middle\|\;\begin{array}[]{l}r\in P,S\subseteq_{sz(r)}1,\\ h(S)=b(r),\\ h(S)=b(S)\subseteq I\end{array}\right\}.$

By definition of $1$ , we have $b(S)=h(S)$ and therefore $b(S)=b(r)$ and $b(r)\subseteq I$ . Hence, (34) is equivalent to

\displaystyle\{h(r)\leftarrow b(r)\mid r\in P:I\models b(r)\}=P^{I}.

Finally, we have

{}^{I}(P\cup R)\stackrel{{\scriptstyle(\ref{equ:^IP})}}{{=}}1^{I}(P\cup R)\stackrel{{\scriptstyle(\ref{equ:KP_cup_R})}}{{=}}1^{I}P\cup 1^{I}R\stackrel{{\scriptstyle(\ref{equ:^IP})}}{{=}}{{}^{I}}P\cup{{}^{I}}R

and

{}^{I}(PR)\stackrel{{\scriptstyle(\ref{equ:^IP})}}{{=}}(1^{I})(PR)\stackrel{{\scriptstyle(\ref{equ:KPR})}}{{=}}((1^{I})P)R\stackrel{{\scriptstyle(\ref{equ:^IP})}}{{=}}{{}^{I}P}R

with the remaining identities in (33) holding by analogous computations. ∎

Consequently, we can simplify the computation of composition as follows.

Corollary 18.

For any programs $P$ and $R$ , we have

(39)

\displaystyle P\circ R=P^{h(R)}\circ{{}^{b(P)}}R.

4.4. Proper Programs

By equation (23), we can extract the facts of a program $P$ by computing the right reduct with respect to the empty set, $P^{\emptyset}$ , and by composing $P$ with the empty set, $P\emptyset$ . Unfortunately, there is no analogous characterization of the proper rules in terms of composition. We have therefore introduced a unary operator $p$ for that purpose and we now want to state some basic properties of that operator as it is used to characterize idempotent programs (Proposition 20). The proper rules operator satisfies the following identities, for any propositional logic programs $P$ and $R$ , and interpretation $I$ :

(40)	$\displaystyle p\circ p$	$\displaystyle=p$
(41)	$\displaystyle p\circ f$	$\displaystyle=f\circ p=\emptyset$
(42)	$\displaystyle p(1)$	$\displaystyle=1$
(43)	$\displaystyle p(I)$	$\displaystyle=\emptyset$
(44)	$\displaystyle p(P)\emptyset$	$\displaystyle\stackrel{{\scriptstyle(\ref{equ:f(P)})}}{{=}}f(p(P))\stackrel{{\scriptstyle(\ref{equ:pf})}}{{=}}\emptyset$
(45)	$\displaystyle p(P\cup R)$	$\displaystyle=p(P)\cup p(R).$

Of course, we have $p(P)=P$ iff $P$ contains no facts, that is, iff $P^{\emptyset}=\emptyset$ . The last identity says that the proper rules operator is compatible with union; however, the following counter-example shows that it is not compatible with sequential composition:

\displaystyle p\left(\{a\leftarrow b,c\}\circ\left\{\begin{array}[]{l}b\leftarrow b\\ c\end{array}\right\}\right)=\{a\leftarrow b\}

whereas

\displaystyle p(\{a\leftarrow b,c\})\circ p\left(\left\{\begin{array}[]{l}b\leftarrow b\\ c\end{array}\right\}\right)=\emptyset.

This shows that the proper rule operator fails to be a homomorphism with respect to composition.

Proposition 19.

The space of all proper propositional logic programs forms a submagma of the space of all propositional logic programs with the zero given by the empty set.

Proof.

The space of proper programs is closed under composition. It remains to show that the empty set is a zero, but this follows from the fact that it is a left zero by (22) and from the observation that for any proper program $P$ , we have $P\emptyset\stackrel{{\scriptstyle(\ref{equ:f(P)})}}{{=}}f(P)=\emptyset.$ ∎

4.5. Idempotent Programs

Recall that $P$ is called idempotent if $P\circ P=P$ . Idempotent programs have the nice property that their least models are trivial to compute as they coincide with the facts of the program. Characterizing idempotent programs on an algebraic level is therefore interesting, which is done in the next result in terms of their facts and proper rules.

Proposition 20.

A program $P$ is idempotent iff

(46)

\displaystyle p(P)f(P)\subseteq f(P)\quad\text{and}\quad p(P^{2})=p(p(P)P).

Proof.

The program $P$ is idempotent iff we have (i) $f(P^{2})=f(P)$ and (ii) $p(P^{2})=p(P)$ . For the first condition in (46), we compute

	$\displaystyle f(P^{2})$	$\displaystyle\stackrel{{\scriptstyle(\ref{equ:f(P)})}}{{=}}P^{2}\emptyset$
		$\displaystyle=P(P\emptyset)$
		$\displaystyle=P\circ f(P)$
		$\displaystyle\stackrel{{\scriptstyle(\ref{equ:P})}}{{=}}(f(P)\cup p(P))f(P)$
		$\displaystyle\stackrel{{\scriptstyle(\ref{equ:(P_cup_Q)_circ_R})}}{{=}}f(P)f(P)\cup p(P)f(P)$
		$\displaystyle\stackrel{{\scriptstyle(\ref{equ:IP=I})}}{{=}}f(P)\cup p(P)f(P).$

This yields

\displaystyle f(P^{2})=f(P)\quad\Leftrightarrow\quad p(P)f(P)\subseteq f(P).

For the second condition in (46), we compute

	$\displaystyle p(P^{2})$	$\displaystyle=p((f(P)\cup p(P))P)$
		$\displaystyle\stackrel{{\scriptstyle(\ref{equ:(P_cup_Q)_circ_R})}}{{=}}p(f(P)P\cup p(P)P)$
		$\displaystyle\stackrel{{\scriptstyle(\ref{equ:IP=I})}}{{=}}p(f(P)\cup p(P)P)$
		$\displaystyle\stackrel{{\scriptstyle(\ref{equ:proper_cup})}}{{=}}p(f(P))\cup p(p(P)P)$
		$\displaystyle\stackrel{{\scriptstyle(\ref{equ:pf})}}{{=}}p(p(P)P).$

∎

Fact 21.

Every interpretation is idempotent.

Proof.

A direct consequence of (22). ∎

5. Decomposition

It is often useful to know how a program is assembled from its simpler parts. In this section, we therefore study sequential decompositions of acyclic (§5.3) and arbitrary programs (§5.4). Before we do that we first look in §5.1 at some ways how to algebraically transform programs via composition.

5.1. Adding and Removing Body Atoms

Notice that we can manipulate rule bodies via composition on the right. For example, we have

\displaystyle\{a\leftarrow b,c\}\circ\left\{\begin{array}[]{l}b\leftarrow b\\ c\end{array}\right\}=\{a\leftarrow b\}.

The general construction here is that we add a tautological rule $b\leftarrow b$ for every body atom $b$ of $P$ which we want to preserve, and we add a fact $c$ in case we want to remove $c$ from the rule bodies in $P$ . We therefore define, for an interpretation $I$ , the minimalist program

\displaystyle I^{\ominus}=1^{A-I}\cup I.

Notice that $.^{\ominus}$ is computed with respect to some fixed alphabet $A$ . For instance, we have

\displaystyle A^{\ominus}=A\quad\text{and}\quad\emptyset^{\ominus}=1.

The first equation yields another explanation for (8), that is, we can compute the heads in $P$ by removing all body atoms of $P$ via

h(P)=PA^{\ominus}=PA.

Interestingly enough, we have

\displaystyle I^{\ominus}I=(1^{A-I}\cup I)I\stackrel{{\scriptstyle(\ref{equ:(P_cup_Q)_circ_R})}}{{=}}1^{A-I}I\cup I^{2}\stackrel{{\scriptstyle(\ref{equ:IP=I}),(\ref{equ:^JI}),(\ref{equ:^IP})}}{{=}}((A-I)\cap I)\cup I=I

and

\displaystyle I^{\ominus}P={{}^{A-I}}P\cup I.

Moreover, in the example above, we have

\displaystyle\{c\}^{\ominus}=\left\{\begin{array}[]{l}a\leftarrow a\\ b\leftarrow b\\ c\end{array}\right\}\quad\text{and}\quad\{a\leftarrow b,c\}\circ\{c\}^{\ominus}=\{a\leftarrow b\}

as desired. Notice also that the facts of a program are, of course, not affected by composition on the right, that is, we cannot expect to remove facts via composition on the right (cf. (7)).

We have the following general result:

Proposition 22.

For any $P$ and interpretation $I$ , we have

\displaystyle PI^{\ominus}=\{h(r)\leftarrow(b(r)-I)\mid r\in P\}.

In analogy to the above construction, we can add body atoms via composition on the right. For example, we have

\displaystyle\{a\leftarrow b\}\circ\{b\leftarrow b,c\}=\{a\leftarrow b,c\}.

Here, the general construction is as follows. For an interpretation $I$ , define the minimalist program

\displaystyle I^{\oplus}=\{a\leftarrow(\{a\}\cup I)\mid a\in A\}.

For instance, we have

\displaystyle A^{\oplus}=\{a\leftarrow A\mid a\in A\}\quad\text{and}\quad\emptyset^{\oplus}=1.

Interestingly enough, we have

\displaystyle I^{\oplus}I^{\ominus}=I^{\ominus}\quad\text{and}\quad I^{\oplus}I=I.

Moreover, in the example above, we have

\displaystyle\{c\}^{\oplus}=\left\{\begin{array}[]{l}a\leftarrow a,c\\ b\leftarrow b,c\\ c\leftarrow c\end{array}\right\}\quad\text{and}\quad\{a\leftarrow b\}\circ\{c\}^{\oplus}=\{a\leftarrow b,c\}

as desired. As composition on the right does not affect the facts of a program, we cannot expect to append body atoms to facts via composition on the right. However, we can add arbitrary atoms to all rule bodies simultaneously and in analogy to Proposition 22, we have the following general result:

Proposition 23.

For any program $P$ and interpretation $I$ , we have

\displaystyle PI^{\oplus}=f(P)\cup\{h(r)\leftarrow(b(r)\cup I)\mid r\in p(P)\}.

We now want to illustrate the interplay between the above concepts with an example.

Example 24.

Consider the propositional logic programs

\displaystyle P=\left\{\begin{array}[]{l}c\\ a\leftarrow b,c\\ b\leftarrow a,c\end{array}\right\}\quad\text{and}\quad\pi_{(a\,b)}=\left\{\begin{array}[]{l}a\leftarrow b\\ b\leftarrow a\end{array}\right\}.

Roughly, we obtain $P$ from $\pi_{(a\,b)}$ by adding the fact $c$ to $\pi_{(a\,b)}$ and to each body rule in $\pi_{(a\,b)}$ . Conversely, we obtain $\pi_{(a\,b)}$ from $P$ by removing the fact $c$ from $P$ and by removing the body atom $c$ from each rule in $P$ . This can be formalized as⁷⁷7Here, we have $\{c\}^{\ast}=1\cup\{c\}$ and $\{c\}^{\ast}\pi_{(a\,b)}=\pi_{(a\,b)}\cup\{c\}$ by the forthcoming equation (66).

\displaystyle P=\{c\}^{\ast}\pi_{(a\,b)}\{c\}^{\oplus}\quad\text{and}\quad\pi_{(a\,b)}=1^{\{a,b\}}P\{c\}^{\ominus}.

Remark 25.

It is important to emphasize that we cannot add arbitrary rules to a program via composition. For example, suppose we want to add the rule $r=a\leftarrow b$ to the empty program $\emptyset$ . By (22) we have $\emptyset P=\emptyset$ , for all $P$ , which means that the only reasonable thing we can do is to compute $P\emptyset$ —but $P\emptyset\stackrel{{\scriptstyle(\ref{equ:f(P)})}}{{=}}f(P)\neq\{r\}$ shows that we cannot add $r$ to the empty program via composition on the left. The intuitive reason is that in order to construct the rule $r$ via composition, we need to be able to add body atoms to facts, which is easily seen to be impossible.

5.2. Closures

The following construction will often be useful when studying decompositions:

Definition 26.

Define the closure of $P$ with respect to some alphabet $A$ by

(47)

\displaystyle c_{A}(P):=1_{A}\cup P.

Roughly, we obtain the closure of a program by adding all possible tautological rules of the form $a\leftarrow a$ , for $a\in A$ . Of course, the closure operator preserves semantic equivalence, that is,

\displaystyle P\equiv c_{A}(P),\quad\text{for all alphabets $A$.}

Lemma 27.

For any programs $P$ and $R$ , if $P$ does not depend on $R$ , we have

(48)

\displaystyle P(Q\cup R)=PQ.

Proof.

We compute

(49)

\displaystyle P(Q\cup R)\stackrel{{\scriptstyle(\ref{equ:P^head_circ_^body_R})}}{{=}}P^{h(Q\cup R)}\left({{}^{b(P)}}(Q\cup R)\right)\stackrel{{\scriptstyle(\ref{equ:^IPR})}}{{=}}P^{h(Q\cup R)}\left({{}^{b(P)}}Q\cup{{}^{b(P)}}R\right).

Since $P$ does not depend on $R$ , we have $b(P)\cap h(R)=\emptyset$ and, hence,

{}^{b(P)}R=\{r\in R\mid b(P)\models h(r)\}=\{r\in R\mid h(r)\in b(P)\}=\emptyset.

Moreover, we have

\displaystyle P^{h(Q\cup R)}=P^{h(Q)\cup h(R)}=\{r\in P\mid b(r)\subseteq h(Q)\cup h(R)\}=\{r\in P\mid b(r)\subseteq h(Q)\}=P^{h(Q)}.

Hence, (49) is equivalent to

\displaystyle\left(P^{h(Q)}\right)\left({{}^{b(P)}}Q\right)\stackrel{{\scriptstyle(\ref{equ:P^head_circ_^body_R})}}{{=}}PQ.

∎

Lemma 28.

For any programs $P$ and $R$ , in case $P$ does not depend on $R$ , we have

(50)

\displaystyle P\cup R=c_{h(R)}(P)c_{b(P)}(R)\quad\text{and}\quad c_{A}(P\cup R)=c_{A}(P)c_{A}(R).

Moreover, for any alphabets $A$ and $B$ , we have

\displaystyle c_{A}(c_{B}(P))=c_{A\cup B}(P).

Proof.

We compute

	$\displaystyle c_{h(R)}(P)c_{b(P)}(R)$	$\displaystyle=(1_{h(R)}\cup P)(1_{b(P)}\cup R)$
		$\displaystyle\stackrel{{\scriptstyle(\ref{equ:(P_cup_Q)_circ_R})}}{{=}}1_{h(R)}(1_{b(P)}\cup R)\cup P(1_{b(P)}\cup R)$
		$\displaystyle\stackrel{{\scriptstyle(\ref{equ:KP_cup_R})}}{{=}}1_{h(R)}1_{b(P)}\cup 1_{h(R)}R\cup P(1_{b(P)}\cup R)$
		$\displaystyle\stackrel{{\scriptstyle(\ref{equ:1I_circ_J}),(\ref{equ:^IP})}}{{=}}1_{h(R)\cap b(P)}\cup{{}^{h(R)}}R\cup P(1_{b(P)}\cup R)$
		$\displaystyle=R\cup P(1_{b(P)}\cup R)$
		$\displaystyle\stackrel{{\scriptstyle(\ref{equ:PQ})}}{{=}}R\cup P1_{b(P)}$
		$\displaystyle\stackrel{{\scriptstyle(\ref{equ:^IP})}}{{=}}R\cup P^{b(P)}$
		$\displaystyle=R\cup P$

where the fourth equality follows from $1_{h(R)\cap b(P)}=\emptyset$ and ${}^{h(R)}R=R$ , the fifth equality holds since $P$ does not depend on $R$ (Lemma 27), and the last equality follows from $P^{b(P)}=P$ .

For the second equality, we compute

\displaystyle c_{A}(P)c_{A}(R)=(1\cup P)(1\cup R)\stackrel{{\scriptstyle(\ref{equ:(P_cup_Q)_circ_R})}}{{=}}1\cup R\cup P(1\cup R)\stackrel{{\scriptstyle(\ref{equ:PQ})}}{{=}}1\cup R\cup P=c_{A}(P\cup R)

where the third identity follows from the fact that $P$ does not depend on $R$ (Lemma 27).

Lastly, we compute

\displaystyle c_{A}(c_{B}(P))=1_{A}\cup 1_{B}\cup B\stackrel{{\scriptstyle(\ref{equ:1^I_cup_J})}}{{=}}1_{A\cup B}\cup P=c_{A\cup B}(P).

∎

5.3. Acyclic Programs

Recall that a program is called acyclic if it has a level mapping so that the head of each rule is strictly greater than each of its body atom with respect to that mapping. Acyclic programs appear frequently in practice (?), which is the motivation for studying their decompositions in this section. The main result of this section shows that acyclic programs can be decomposed into single-rule programs (Theorem 31).

Example 29.

We define a family of acyclic programs over $A$ , which we call elevator programs, as follows: given a sequence $(a_{1},\ldots,a_{n})\in A^{n}$ , $1\leq n\leq|A|$ , of distinct atoms, let $E_{(a_{1},\ldots,a_{n})}$ be the acyclic program

\displaystyle E_{(a_{1},\ldots,a_{n})}=\{a_{1}\}\cup\{a_{i}\leftarrow a_{i-1}\mid 2\leq i\leq n\}.

So, for instance, $E_{(a,b,c)}$ is the program

\displaystyle E_{(a,b,c)}=\left\{\begin{array}[]{l}a\\ b\leftarrow a\\ c\leftarrow b\end{array}\right\}.

The mapping $\ell$ given by $\ell(a)=1$ , $\ell(b)=2$ , and $\ell(c)=3$ is a level mapping for $E_{(a,b,c)}$ and we can decompose $E_{(a,b,c)}$ into a product of single-rule programs by

	$\displaystyle E_{(a,b,c)}$	$\displaystyle=(1^{\{b,c\}}\cup\{a\})(1^{\{c\}}\cup\{b\leftarrow a\})(1^{\{a\}}\cup\{c\leftarrow b\})$
		$\displaystyle=c_{\{b,c\}}(\{a\})c_{\{c\}}(\{b\leftarrow a\})c_{\{c\}}(\{c\leftarrow b\}).$

We now want to generalize the reasoning pattern of Example 29 to arbitrary acyclic programs. For this, we will need the following lemma.

Lemma 30.

For any programs $P$ and $R$ and alphabet $B$ , if $P$ and $1_{B}$ do not depend on $R$ , we have

(51)

\displaystyle c_{B}(c_{h(R)}(P)c_{b(P)}(R))=c_{B\cup h(R)}(P)c_{B\cup b(P)}(R).

Proof.

Since $P$ does not depend on $R$ , as a consequence of Lemma 28 we have

\displaystyle c_{h(R)}(P)c_{b(P)}=P\cup R.

Hence,

	$\displaystyle c_{B}$	$\displaystyle(c_{h(R)}(P)c_{b(P)}(R))$
		$\displaystyle=c_{B}(P\cup R)$
		$\displaystyle=1_{B}\cup P\cup R$
		$\displaystyle\stackrel{{\scriptstyle(\ref{equ:P_cup_R})}}{{=}}c_{h(R)}(1_{B}\cup P)c_{b(1_{B}\cup P)}(R)\qquad(h(R)\cap B=\emptyset)$
		$\displaystyle=c_{B\cup h(R)}(P)c_{B\cup b(P)}(R).$

∎

We further will need the following auxiliary construction. Define, for any linearly ordered rules $r_{1}<\ldots<r_{n}$ , $n\geq 2$ ,

\displaystyle bh_{i}(\{r_{1}<\ldots<r_{n}\}):=b(\{r_{1},\ldots,r_{i-1}\})\cup h(\{r_{i+1},\ldots,r_{n}\}).

We are now ready to prove the following decomposition result for acyclic programs.

Theorem 31.

We can sequentially decompose any acyclic program $P=\{r_{1}<_{\ell}\ldots<_{\ell}r_{n}\}$ , $n\geq 2$ , linearly ordered by a level mapping $\ell$ , into single-rule programs as

\displaystyle P=\prod_{i=1}^{n}c_{bh_{i}(P)}(\{r_{i}\}).

This decomposition is unique up to reordering of rules within a single level.⁸⁸8See the construction of the total ordering $<_{\ell}$ in Section 2.2.1.

Proof.

The proof is by induction on the number $n$ of rules in $P$ . For the induction hypothesis $n=2$ and $P=\{r_{1}<_{\ell}r_{2}\}$ , we proceed as follows. First, we have

(52)		$\displaystyle c_{bh_{1}(P)}(\{r_{1}\})c_{bh_{2}(P)}(\{r_{2}\})$	$\displaystyle=(1_{h(\{r_{2}\})}\cup\{r_{1}\})(1_{b(\{r_{1}\})}\cup\{r_{2}\})$
(53)			$\displaystyle=1_{h(\{r_{2}\})}(1_{b(\{r_{1}\})}\cup\{r_{2}\})\cup\{r_{1}\}(1_{b(\{r_{1}\})}\cup\{r_{2}\}).$

Since Krom programs distribute from the left (Theorem 12), we can simplify (52), by applying (30) and (29), into

(54)

\displaystyle 1_{h(\{r_{2}\})\cap b(\{r_{1}\})}\cup{{}^{h(\{r_{2}\})}}\{r_{2}\}\cup\{r_{1}\}^{b(\{r_{1}\})}=1_{h(\{r_{2}\})\cap b(\{r_{1}\})}\cup\{r_{1},r_{2}\}.

Now, since $r_{1}$ does not depend on $r_{2}$ , that is, $h(r_{2})\cap b(r_{1})=\emptyset$ , the first term in (54) equals $1_{\emptyset}=\emptyset$ which implies that (54) is equivalent to $P$ as desired.

For the induction step $P=\{r_{1}<_{\ell}\ldots<_{\ell}r_{n+1}\}$ , we proceed as follows. First, by definition of $bh_{i}$ , we have

(55)		$\displaystyle\prod_{i=1}^{n+1}(c_{bh_{i}(P)}(\{r_{i}\}))$	$\displaystyle=\prod_{i=1}^{n+1}(1_{bh_{i}(P)}\cup\{r_{i}\})$
(56)			$\displaystyle=\left[\prod_{i=1}^{n}(1_{bh_{i}(\{r_{1},\ldots,r_{n}\})}\cup 1_{h(r_{n+1})}\cup\{r_{i}\})\right](1_{b(\{r_{1},\ldots,r_{n}\})}\cup\{r_{n+1}\}).$

Second, by idempotency of union we can extract the term

1_{h(r_{n+1})}=1_{h(r_{n+1})}\ldots 1_{h(r_{n+1})}\quad\text{($n$ times)}

occurring in (56) thus obtaining

(57)

\displaystyle\left[1_{h(r_{n+1})}\cup\prod_{i=1}^{n}(1_{bh_{i}(\{r_{1},\ldots,r_{n}\})}\cup 1_{h(r_{n+1})}\cup\{r_{i}\})\right](1_{b(\{r_{1},\ldots,r_{n}\})}\cup\{r_{n+1}\}).

Now, since $r_{i}$ and $1_{bh_{i}(\{r_{1},\ldots,r_{n}\})}$ do not depend on $r_{n+1}$ , we can simplify (57) further to

(58)

\displaystyle\left[1_{h(r_{n+1})}\cup\prod_{i=1}^{n}(1_{bh_{i}(\{r_{1},\ldots,r_{n}\})}\cup\{r_{i}\})\right](1_{b(\{r_{1},\ldots,r_{n}\})}\cup\{r_{n+1}\}).

By applying the induction hypothesis to (58), we obtain

\displaystyle(1_{h(r_{n+1})}\cup\{r_{1},\ldots,r_{n}\})(1_{b(\{r_{1},\ldots,r_{n}\})}\cup\{r_{n+1}\})

which, by right-distributivity of composition, is equal to

(59)

\displaystyle 1_{h(r_{n+1})}(1_{b(\{r_{1},\ldots,r_{n}\})}\cup\{r_{n+1}\})\cup\{r_{1},\ldots,r_{n}\}(1_{b(\{r_{1},\ldots,r_{n}\})}\cup\{r_{n+1}\}).

Now again since $r_{i}$ does not depend on $r_{n+1}$ , for all $1\leq i\leq n$ , as a consequence of (21), (30), (29), and (48), the term in (59) equals

(60)

\displaystyle 1_{h(r_{n+1})\cap b(\{r_{1},\ldots,r_{n}\})}\cup{{}^{h(r_{n+1})}}\{r_{n+1}\}\cup\{r_{1},\ldots,r_{n}\}^{b(\{r_{1},\ldots,r_{n}\})}.

Finally, since $1_{h(r_{n+1})\cap b(\{r_{1},\ldots,r_{n}\})}=1_{\emptyset}=\emptyset$ , (60) equals $\{r_{1},\ldots,r_{n+1}\}$ , which proves our theorem. ∎

5.4. General Decompositions

In the last subsection, we studied the decomposition of acyclic programs and showed that they are assembled of single-rule programs. In this subsection, we study decompositions of arbitrary programs (Theorem 32) which turns out to be much more difficult given that we now have to deal with circularities among the rules (Problem 34).

We first wish to generalize Lemma 28 to arbitrary propositional logic programs. For this, we define, for every interpretation $I$ and disjoint copy $I^{\prime}=\{a^{\prime}\mid a\in I\}$ of $I$ , the minimalist program (recall that $A$ is the underlying propositional alphabet)

	$\displaystyle[I\leftarrow I^{\prime}]$	$\displaystyle:=c_{A-I}(\{a\leftarrow a^{\prime}\mid a\in I\})$
		$\displaystyle\;=\{a\leftarrow a^{\prime}\mid a\in I\}\cup\{a\leftarrow a\mid a\in A-I\}.$

We have

[A\leftarrow A^{\prime}]=\{a\leftarrow a^{\prime}\mid a\in A\}

and therefore

\displaystyle P[A\leftarrow A^{\prime}]=\{h(r)\leftarrow b(r)^{\prime}\mid r\in P\},

where $b(r)^{\prime}=\{b^{\prime}\mid b\in b(r)\}$ , and

\displaystyle[A^{\prime}\leftarrow A]P=\{h(r)^{\prime}\leftarrow b(r)\mid r\in P\}.

Moreover, we have

(61)

\displaystyle[A\leftarrow A^{\prime}][A^{\prime}\leftarrow A]=1_{A}.

We are now ready to prove the main result of this subsection which shows that we can represent the union of programs via composition and closures:

Theorem 32.

For any programs $P$ and $R$ , we have

\displaystyle P\cup R=c_{h(R)}(P[A\leftarrow A^{\prime}])c_{b(P[A\leftarrow A^{\prime}])}(R)c_{A}([A^{\prime}\leftarrow A]).

Proof.

Since $P[A\leftarrow A^{\prime}]$ does not depend on $R$ , we have, as a consequence of Lemma 28,

\displaystyle P[A\leftarrow A^{\prime}]\cup R=c_{h(R)}(P[A\leftarrow A^{\prime}])c_{b(P[A\leftarrow A^{\prime}])}(R).

Finally, we have

	$\displaystyle(P[A\leftarrow A^{\prime}]\cup R)c_{A}([A^{\prime}\leftarrow A])$	$\displaystyle\stackrel{{\scriptstyle(\ref{equ:(P_cup_Q)_circ_R})}}{{=}}P[A\leftarrow A^{\prime}]c_{A}([A^{\prime}\leftarrow A])\cup R\,c_{A}([A^{\prime}\leftarrow A])$
		$\displaystyle=P[A\leftarrow A^{\prime}](1_{A}\cup[A^{\prime}\leftarrow A])\cup R(1_{A}\cup[A^{\prime}\leftarrow A])$
		$\displaystyle=P[A\leftarrow A^{\prime}][A^{\prime}\leftarrow A]\cup R$
		$\displaystyle\stackrel{{\scriptstyle(\ref{equ:A_A'})}}{{=}}P\cup R$

where the third identity follows from the fact that $P[A\leftarrow A^{\prime}]$ does not depend on $1_{A}$ and $R$ does not depend on $[A^{\prime}\leftarrow A]$ (apply Lemma 27). ∎

Example 33.

Let $A=\{a,b,c\}$ and consider the program $P=R\cup\pi_{(b\,c)}$ where

\displaystyle R=\left\{\begin{array}[]{l}a\leftarrow b,c\\ a\leftarrow a,b\\ b\leftarrow a\end{array}\right\}\quad\text{and}\quad\pi_{(b\,c)}=\left\{\begin{array}[]{l}b\leftarrow c\\ c\leftarrow b\end{array}\right\}.

We wish to decompose $P$ into a product of $R$ and $\pi_{(b\,c)}$ according to Theorem 32. For this, we first have to replace the body of $R$ with a distinct copy of its atoms, that is, we compute

\displaystyle R[A\leftarrow A^{\prime}]=\left\{\begin{array}[]{l}a\leftarrow b^{\prime},c^{\prime}\\ a\leftarrow a^{\prime},b^{\prime}\\ b\leftarrow a^{\prime}\end{array}\right\}.

Notice that $R[A\leftarrow A^{\prime}]$ no longer depends on $\pi_{(b\,c)}$ ! Next, we compute the composition of

\displaystyle c_{h(\pi_{(b\,c)})}(R[A\leftarrow A^{\prime}])=\left\{\begin{array}[]{l}a\leftarrow b^{\prime},c^{\prime}\\ a\leftarrow a^{\prime},b^{\prime}\\ b\leftarrow a^{\prime}\\ b\leftarrow b\\ c\leftarrow c\end{array}\right\}

and

\displaystyle c_{b(R[A\leftarrow A^{\prime}])}(\pi_{(b\,c)})=\left\{\begin{array}[]{l}b\leftarrow c\\ c\leftarrow b\\ a^{\prime}\leftarrow a^{\prime}\\ b^{\prime}\leftarrow b^{\prime}\\ c^{\prime}\leftarrow c^{\prime}\end{array}\right\}

\displaystyle R^{\prime}=c_{h(\pi_{(b\,c)})}(R[A\leftarrow A^{\prime}])c_{b(R[A\leftarrow A^{\prime}])}(\pi_{(b\,c)})=\left\{\begin{array}[]{l}a\leftarrow b^{\prime},c^{\prime}\\ a\leftarrow a^{\prime},b^{\prime}\\ b\leftarrow a^{\prime}\\ b\leftarrow c\\ c\leftarrow b\end{array}\right\}.

Finally, we need to replace the atoms from $A^{\prime}$ in the body of $R^{\prime}$ by atoms from $A$ , that is, we compute

\displaystyle R^{\prime}c_{A}([A^{\prime}\leftarrow A])=\left\{\begin{array}[]{l}a\leftarrow b^{\prime},c^{\prime}\\ a\leftarrow a^{\prime},b^{\prime}\\ b\leftarrow a^{\prime}\\ b\leftarrow c\\ c\leftarrow b\end{array}\right\}\circ\left\{\begin{array}[]{l}a\leftarrow a\\ b\leftarrow b\\ c\leftarrow c\\ a^{\prime}\leftarrow a\\ b^{\prime}\leftarrow b\\ c^{\prime}\leftarrow c\end{array}\right\}=P

as expected.

Problem 34.

Unfortunately, at the moment we have no such nice decomposition result for arbitrary programs as for acyclic programs (Theorem 31), not relying on auxiliary atoms in $A^{\prime}$ , which remains as future work (cf. §8).

6. Algebraic Semantics

Recall that the fixed point semantics of a propositional logic program is defined in terms of least fixed point computations of its associated van Emden-Kowalski immediate consequence operator (Proposition 3). That is, the semantics is defined operationally outside the syntactic space of the programs. In this section, we reformulate the fixed point semantics of programs in terms of sequential composition by first showing that we can express the van Emden-Kowalski operators via composition (Theorem 35), and then showing how programs (not operators) can be iterated bottom-up to obtain their least models (Theorem 40). This bridges the conceptual gap between the syntax and semantics of a program.

6.1. The van Emden-Kowalski Operator

The next results show that we can simulate the van Emden-Kowalski operators on a syntactic level without any explicit reference to operators.

Theorem 35.

For any program $P$ and interpretation $I$ , we have

(62)

\displaystyle T_{P}(I)=PI.

Moreover, we have for any program $R$ ,

(63)

\displaystyle T_{P}\cup T_{R}=T_{P\cup R}\quad\text{and}\quad T_{P}\circ T_{R}=T_{PR}\quad\text{and}\quad T_{\emptyset}=\emptyset\quad\text{and}\quad T_{1}=Id_{2^{A}}.

Proof.

All of the equations follow immediately from the definition of composition. To illustrate some of the already derived results, we compute

\displaystyle T_{P}(I)

\displaystyle=h(P^{I})\stackrel{{\scriptstyle(\ref{equ:head_P})}}{{=}}P^{I}A\stackrel{{\scriptstyle(\ref{equ:^IP})}}{{=}}(P(1^{I}))A=P((1^{I})A)\stackrel{{\scriptstyle(\ref{equ:^IP})}}{{=}}P(^{I}A)\stackrel{{\scriptstyle(\ref{equ:^JI})}}{{=}}P(I\cap A)=PI

where the last equality follows from $I$ being a subset of $A$ .

∎

Corollary 36.

Sequential composition is associative modulo subsumption equivalence, that is,

\displaystyle P(QR)\equiv_{ss}(PQ)R\quad\text{for any programs $P,Q,R$}.

This implies

(64)

\displaystyle(PR)I=P(RI),\quad\text{for any programs $P,R$ and interpretation $I$}.

Proof.

Associativity modulo subsumption equivalence is an immediate consequence of Theorem 35 which shows

\displaystyle T_{P(QR)}=T_{(PQ)R}\quad\Rightarrow\quad P(QR)\equiv_{ss}(PQ)R.

The identity is shown via (63) by

\displaystyle(PR)I=T_{PR}(I)=T_{P}(T_{R}(I))=P(RI).

∎

As a direct consequence of Proposition 2 and Theorem 35, we have the following algebraic characterization of (supported) models:

Corollary 37.

An interpretation $I$ is a model of $P$ iff $PI\subseteq I$ , and $I$ is a supported model of $P$ iff $PI=I$ .

Corollary 38.

The space of all interpretations forms an ideal.

Proof.

By Fact 13, we know that the space of interpretations forms a right ideal and Theorem 35 implies that it is a left ideal—hence, it forms an ideal. ∎

6.2. Least Models

We interpret propositional logic programs according to their least model semantics and since least models can be constructively computed by bottom-up iterations of the associated van Emden-Kowalski operators (Proposition 3), and since these operators can be represented in terms of composition (Theorem 35), we can finally reformulate the fixed point semantics of programs algebraically in terms of composition (Theorem 40).

We make the convention that for any $n\geq 3$ ,

\displaystyle P^{n}=(((PP)P)\ldots P)P\quad(n\text{ times}).

Definition 39.

Define the unary Kleene star and plus operations by

(65)

\displaystyle P^{\ast}=\bigcup_{n\geq 0}P^{n}\quad\text{and}\quad P^{+}=P^{\ast}P.

Moreover, define the omega operation by

\displaystyle P^{\omega}=P^{+}\emptyset\stackrel{{\scriptstyle(\ref{equ:f(P)})}}{{=}}f(P^{+}).

Notice that the unions in (65) are finite since $P$ is finite. For instance, for any interpretation $I$ , we have as a consequence of Fact 21,

(66)

\displaystyle I^{\ast}=1\cup I\quad\text{and}\quad I^{+}=I\quad\text{and}\quad I^{\omega}=I.

Interestingly enough, we can add the atoms in $I$ to $P$ via

(67)

\displaystyle P\cup I\stackrel{{\scriptstyle(\ref{equ:IP=I})}}{{=}}P\cup IP\stackrel{{\scriptstyle(\ref{equ:(P_cup_Q)_circ_R})}}{{=}}(1\cup I)P\stackrel{{\scriptstyle(\ref{equ:I^ast})}}{{=}}I^{\ast}P.

Hence, as a consequence of (5) and (67), we can decompose $P$ as

\displaystyle P=f(P)^{\ast}p(P),

which, roughly, says that we can sequentially separate the facts from the proper rules in $P$ .

We are now ready to characterize the least model of a program via composition as follows.

Theorem 40.

For any program $P$ , we have

\displaystyle LM(P)=P^{\omega}.

Proof.

A direct consequence of Proposition 3 and Theorem 35. ∎

Corollary 41.

Two programs $P$ and $R$ are equivalent iff $P^{\omega}=R^{\omega}$ .

To summarize, we have thus shown that we can use the syntactic sequential composition operation to capture the least model or fixed point semantics of a program algebraically within the space of programs giving rise to the algebraic characterization of the semantics of a program in Theorem 40 and the semantic equivalence of programs in Corollary 41.

7. Related Work

? (?) is probably the first to study the composition of logic programs. He first defines the denotation of $P$ by⁹⁹9For an operator $T$ , we define $T^{\ast}$ in the same way as $P^{\ast}$ in §6.2 as $T^{\ast}=Id\cup T\cup T^{2}\cup\ldots$ ; notice that ? (?) uses the notation $T^{\omega}$ instead of $T^{\ast}$ which we refuse to use here to remain consistent with the use of the symbols in §6.2. $\llbracket P\rrbracket=(T_{P}\cup Id)^{\ast}$ and then defines the semantic composition of $P$ and $R$ so that $\llbracket P\circ R\rrbracket=\llbracket P\rrbracket\circ\llbracket R\rrbracket$ (cf. ?, p. 450). That is, he defines the composition of two programs on a semantic level in terms of the compositions of their immediate consequence operators which is straightforward given that we already know how to compose functions; in contrast, in our approach of this paper we define the sequential composition of two programs explicitly on a syntactic level which allows us to distinguish algebraically between subsumption equivalent programs (at the cost of losing associativity; see Example 10 and Corollary 36).

It is important to emphasize that since we can represent the immediate consequence operator in terms of sequential composition (Theorem 35), O’Keefe’s definition can be resembled in terms of sequential composition as well via¹⁰¹⁰10Notice that the identity function $Id$ corresponds to the unit program $1$ since $Id(I)=1\circ I$ holds for all interpretations $I$ .

	$\displaystyle\llbracket P\circ R\rrbracket(I)$	$\displaystyle=(\llbracket P\rrbracket\circ\llbracket R\rrbracket)(I)$
		$\displaystyle=((T_{P}\cup Id)^{\ast}\circ(T_{R}\cup Id)^{\ast})(I)$
		$\displaystyle=(T_{P}\cup Id)^{\ast}((T_{R}\cup Id)^{\ast}(I))$
		$\displaystyle\stackrel{{\scriptstyle(\ref{equ:T_P})}}{{=}}(P\cup 1)^{\ast}\circ((P\cup 1)^{\ast}\circ I)$
		$\displaystyle\stackrel{{\scriptstyle(\ref{equ:cl})}}{{=}}c(P)^{\ast}\circ(c(R)^{\ast}\circ I)\quad\text{for all interpretations $I$.}$

? (?) study modular logic programming by defining algebraic operations on programs similar to ? (?). More formally, O’Keefe’s composition is captured in ?’s (?) framework as $\llbracket P\circ R\rrbracket=\llbracket(P\cup R^{\omega})^{\omega}\rrbracket$ , where $\llbracket P^{\omega}\rrbracket=T_{P}^{\infty}$ in our notation (cf. ?, p. 450). This shows that we can represent ?’s (?) algebraic operations in terms of sequential composition as well. The work of ? (?) is similar in spirit to the aforementioned works. Formally, ? (?) first define the admissible Herbrand model of $P$ denoted (again) by $\llbracket P\rrbracket$ and then define a semantic composition operation $\bullet$ which allows one to compute the semantics of the union of two programs in the sense that $\llbracket P\cup R\rrbracket=\llbracket P\rrbracket\bullet\llbracket R\rrbracket$ (cf. ?, Proposition 3.4).

? (?, ?) study the composition and decomposition of datalog program mappings—where datalog programs are function-free logic programs used mainly in database theory (cf. ?, ?)—for query optimization in the context of databases. ? (?, ?) employs tools from semigroup theory for query optimization. His work is similar in spirit to the work of ? (?) who map Horn rules to an relational algebra operator, where the set of all such operators forms a semiring, and answer queries via solving linear equations. The authors then study decompositions of relational algebra operators for optimization purposes. To the best of our knowledge, these are the only works utilizing semigroups and semirings in logic programming.¹¹¹¹11There are semiring-based works on weighted logic programs, where semirings are used to add probabilities and other quantitative information to rules and programs (e.g. ?).

? (?) consider the following principle of partial evaluation as a semantic preserving transformation of a given program $P$ . Let $r=a_{0}\leftarrow a_{1},\ldots,a_{k}\in P$ and choose some fixed body atom $a$ among $a_{1},\ldots,a_{k}$ ; without loss of generality, we can assume $a=a_{1}$ . If all the rules in $P$ with $a_{1}$ in the head are given by

(68)

\displaystyle a_{1}\leftarrow B_{1}\quad\ldots\quad a_{1}\leftarrow B_{n},

then we can replace $r$ by the $n$ rules

\displaystyle a_{0}\leftarrow B_{1}\cup\{a_{2},\ldots,a_{k}\}\quad\ldots\quad a_{0}\leftarrow B_{n}\cup\{a_{2},\ldots,a_{k}\}.

There is some similarity between this transformation and the computation of $P^{2}=P\circ P$ . Formally, if we add to $P$ the tautological rules

\displaystyle a_{2}\leftarrow a_{2}\quad\ldots\quad a_{k}\leftarrow a_{k},

then $P^{2}$ contains all the rules in (68); however, $P^{2}$ may contain many more rules with $a_{1}$ in its head depending on the rules in $P$ with $a_{2},\ldots,a_{k}$ as head atoms. So the main difference between the above principle and the sequential composition operation of this paper is that the former operates on single programs and on single body atoms whereas the latter is defined as a binary operation between two programs and operates on all body atoms at once.

The sequential composition and decomposition of (first-order) logic programs is used in the context of logic program synthesis via analogical proportions in ? (?) and for defining a qualitative notion of syntactic program similarity, which allows one to answer queries across different domains, in ? (?). ? (?) provides algebraic characterizations of least model and uniform equivalence of propositional Krom logic programs in terms of sequential composition.

From a purely mathematical point of view, sequential composition of propositional logic programs as introduced in this paper is very similar to composition in multicategories (cf. ?, §2.1).

8. Future Work

In the future, we plan to extend the constructions and results of this paper to wider classes of logical formalisms, most importantly to first-order and higher-order logic programs (?, ?), disjunctive programs (?), and non-monotonic logic programs under the stable model or answer set semantics (?) (see ?, ?, ?, ?). The first task is non-trivial as function symbols require the use of most general unifiers in the definition of composition and give rise to infinite algebras, whereas the non-monotonic case is more difficult to handle algebraically due to negation as failure (?) occurring in rule bodies (and heads). In ? (?), the author studies the non-monotonic case in detail by lifting the concepts and results of this paper from the Horn to the general case containing negation as failure. Some of the results of this paper are subsumed by more general results in ? (?). However, lifting the results on decompositions of programs of §5 to programs with negation turns out to be highly non-trivial and therefore remains an open problem. Even more problematic, disjunctive rules yield non-deterministic behavior which is more difficult to handle algebraically. Nonetheless, we expect interesting results in all of the aforementioned cases to follow.

Another major line of research is to study sequential decompositions of programs as was initiated in Problem 34. Specifically, we wish to compute decompositions of arbitrary propositional logic programs (and extensions thereof) into simpler programs in the vein of Theorem 31, where we expect permutation programs (§4.2.2) to play a fundamental role in such decompositions. For this, it will be necessary to resolve the issue of defining the notion of a “prime” or indecomposable program. From a practical point of view, a mathematically satisfactory theory of program decompositions is relevant to modular logic programming and optimization of reasoning.

9. Conclusion

This paper studied the (sequential) composition of propositional logic programs. We showed in our main structural result (Theorem 9) that the space of all such programs forms a finite unital magma with respect to composition ordered by set inclusion, which distributes from the right over union. Moreover, we showed that the restricted class of propositional Krom programs is distributive and therefore its proper instance forms an idempotent semiring (Theorem 12). From a logical point of view, we obtained algebraic tools for reasoning about propositional logic programs. Algebraically, we obtained a correspondence between propositional logic programs and finite unital magmas and other algebraic structures, which hopefully enables us in the future to transfer concepts from the algebraic literature to the logical setting. In a broader sense, this paper is a first step towards an algebra of logic programs and we expect interesting concepts and results to follow.

Acknowledgments

We would like to thank the reviewers for their thoughtful and constructive comments, and for their helpful suggestions to improve the presentation of the article.

Conflict of interest

The authors declare that they have no conflict of interest.

Data availability statement

The manuscript has no data associated.

References

Antić Antić, C. (2023a). Algebraic characterizations of least model and uniform equivalence of propositional Krom logic programs., https://arxiv.org/pdf/2302.04664.pdf.
Antić Antić, C. (2023b). Logic program proportions. Annals of Mathematics and Artificial Intelligence, accepted. https://arxiv.org/pdf/1809.09938.pdf.
Antić Antić, C. (2023c). On syntactically similar logic programs and sequential decompositions. Information and Computation, under review, https://arxiv.org/pdf/2109.05300.pdf.
Antić Antić, C. (2023d). Sequential composition of answer set programs., https://arxiv.org/pdf/2104.12156v2.pdf.
Apt Apt, K. R. (1990). Logic programming. In van Leeuwen, J. (Ed.), Handbook of Theoretical Computer Science, Vol. B, pp. 493–574. Elsevier, Amsterdam.
Apt Apt, K. R. (1997). From Logic Programming to Prolog. C.A.R. Hoare Series. Prentice Hall, Prentice Hall, Englewood Cliffs, NJ.
Apt and Bezem Apt, K. R., and Bezem, M. (1991). Acyclic programs. New Generation Computing, 9(3-4), 335–363.
Baral Baral, C. (2003). Knowledge Representation, Reasoning and Declarative Problem Solving. Cambridge University Press, Cambridge.
Bistarelli et al. Bistarelli, S., Montanari, U., and Rossi, F. (2001). Semiring-based constraint logic programming—syntax and semantics. ACM Transactions on Programming Languages and Systems, 23(1), 1–29.
Bossi et al. Bossi, A., Bugliesi, M., Gabbrielli, M., Levi, G., and Meo, M. (1996). Differential logic programs: Programming methodologies and semantics. Science of Computer Programming, 27, 217–262.
Brewka et al. Brewka, G., Eiter, T., and Truszczynski, M. (2011). Answer set programming at a glance. Communications of the ACM, 54(12), 92–103.
Brogi et al. Brogi, A., Lamma, E., and Mello, P. (1992a). Compositional model-theoretic semantics for logic programs. New Generation Computing, 11, 1–21.
Brogi et al. Brogi, A., Mancarella, P., Pedreschi, D., and Turini, F. (1992b). Meta for modularising logic programming. In META 1992, pp. 105–119.
Brogi et al. Brogi, A., Mancarella, P., Pedreschi, D., and Turini, F. (1999). Modular logic programming. ACM Transactions on Programming Languages and Systems, 16(4), 1361–1398.
Brogi and Turini Brogi, A., and Turini, F. (1995). Fully abstract compositional semantics for an algebra of logic programs. Theoretical Computer Science, 149(2), 201–229.
Bugliesi et al. Bugliesi, M., Lamma, E., and Mello, P. (1994). Modularity in logic programming. The Journal of Logic Programming, 19-20(1), 443–502.
Ceri et al. Ceri, S., Gottlob, G., and Tanca, L. (1989). What you always wanted to know about datalog (and never dared to ask). IEEE Transactions on Knowledge and Data Engineering, 1(1), 146–166.
Ceri et al. Ceri, S., Gottlob, G., and Tanca, L. (1990). Logic Programming and Databases. Surveys in Computer Science. Springer-Verlag, Berlin/Heidelberg.
Chen et al. Chen, W., Kifer, M., and Warren, D. S. (1993). HiLog: A foundation for higher-order logic programming. The Journal of Logic Programming, 15(3), 187–230.
Clark Clark, K. L. (1978). Negation as failure. In Gallaire, H., and Minker, J. (Eds.), Logic and Data Bases, pp. 293–322. Plenum Press, New York.
Coelho and Cotta Coelho, H., and Cotta, J. C. (1988). Prolog by Example. How to Learn, Teach, and Use It. Springer-Verlag, Berlin/Heidelberg.
Dao-Tran et al. Dao-Tran, M., Eiter, T., Fink, M., and Krennwallner, T. (2009). Modular nonmonotonic logic programming revisited. In ICLP 2009, LNCS 5649, pp. 145–159. Springer-Verlag, Berlin/Heidelberg.
Dix et al. Dix, J., Osorio, M., and Zepeda, C. (2001). A general theory of confluent rewriting systems for logic programming and its applications. Annals of Pure and Applied Logic, 108(1-3), 153–188.
Dong and Ginsburg Dong, G., and Ginsburg, S. (1990). On the decomposition of datalog program mappings. Theoretical Computer Science, 76(1), 143–177.
Dong and Ginsburg Dong, G., and Ginsburg, S. (1995). On decompositions of chain datalog programs into $\mathcal{P}$ (left-)linear 1-rule components. The Journal of Logic Programming, 23(3), 203–236.
Eiter et al. Eiter, T., Gottlob, G., and Mannila, H. (1997). Disjunctive datalog. ACM Transactions on Database Systems, 22(3), 364–418.
Eiter et al. Eiter, T., Ianni, G., and Krennwallner, T. (2009). Answer set programming: a primer. In Reasoning Web. Semantic Technologies for Information Systems, volume 5689 of Lecture Notes in Computer Science, pp. 40–110. Springer, Heidelberg.
Eiter et al. Eiter, T., Ianni, G., Lukasiewicz, T., Schindlauer, R., and Tompits, H. (2008). Combining answer set programming with description logics for the Semantic Web. Artificial Intelligence, 172(12-13), 1495–1539.
Eiter et al. Eiter, T., Ianni, G., Schindlauer, R., and Tompits, H. (2005). A uniform integration of higher-order reasoning and external evaluations in answer-set programming. In Kaelbling, L. P., and Saffiotti, A. (Eds.), IJCAI 2005, pp. 90–96.
Faber et al. Faber, W., Leone, N., and Pfeifer, G. (2004). Recursive aggregates in disjunctive logic programs: semantics and complexity. In Alferes, J., and Leite, J. (Eds.), JELIA 2004, LNCS 3229, pp. 200–212. Springer, Berlin.
Gaifman and Shapiro Gaifman, H., and Shapiro, E. (1989). Fully abstract institute of mathematics fully abstract compositional semantics for logic programs. In Proceedings of the 16th Annual ACM Symposium on Principles of Programming Languages, pp. 134–142. ACM Press.
Gelfond and Lifschitz Gelfond, M., and Lifschitz, V. (1991). Classical negation in logic programs and disjunctive databases. New Generation Computing, 9(3-4), 365–385.
Hill and Lloyd Hill, P., and Lloyd, J. W. (1994). The Gödel Programming Language. The MIT Press.
Hodges Hodges, W. (1994). Logical features of Horn clauses. In Gabbay, D. M., Hogger, C. J., and Robinson, J. A. (Eds.), Handbook of Logic in Artificial Intelligence and Logic Programming, Vol. 1, pp. 449–503. Clarendon Press, Oxford/New York.
Howie Howie, J. M. (2003). Fundamentals of Semigroup Theory. London Mathematical Society Monographs New Series. Oxford University Press, Oxford.
Ioannidis and Wong Ioannidis, Y. E., and Wong, E. (1991). Towards an algebraic theory of recursion. Journal of the ACM, 38(2), 329–381.
Kowalski Kowalski, R. (1979). Logic for Problem Solving. North-Holland, New York.
Krom Krom, M. R. (1967). The decision problem for a class of first-order formulas in which all disjunctions are binary. Mathematical Logic Quarterly, 13(1-2), 15–20.
Leinster Leinster, T. (2004). Higher Operads, Higher Categories, Vol. 298 of London Mathematical Society Lecture Note Series. Cambridge University Press, Cambridge.
Lifschitz Lifschitz, V. (2019). Answer Set Programming. Springer Nature Switzerland AG, Cham, Switzerland.
Lloyd Lloyd, J. W. (1987). Foundations of Logic Programming (2 edition). Springer-Verlag, Berlin, Heidelberg.
Maher Maher, M. J. (1988). Equivalences of logic programs. In Minker, J. (Ed.), Foundations of Deductive Databases and Logic Programming, chap. 16, pp. 627–658. Morgan Kaufmann Publishers.
Makowsky Makowsky, J. A. (1987). Why Horn formulas matter in computer science: initial structures and generic examples. Journal of Computer and System Sciences, 34(2-3), 266–292.
Mancarella and Pedreschi Mancarella, P., and Pedreschi, D. (1988). An algebra of logic programs. In Kowalski, R., and Bowen, K. A. (Eds.), Proceedings of the 5th International Conference on Logic Programming, pp. 1006–1023. The MIT Press, Cambridge MA.
Miller and Nadathur Miller, D., and Nadathur, G. (2012). Programming with Higher-Order Logic. Cambridge University Press.
Oikarinen Oikarinen, E. (2006). Modular Answer Set Programming. Ph.D. thesis, Helsinki University of Technology, Helsinki, Finland.
Oikarinen and Janhunen Oikarinen, E., and Janhunen, T. (2006). Modular equivalence for normal logic programs. In Brewka, G., Coradeschi, S., Perini, A., and Traverso, P. (Eds.), Proc. 17th European Conference on Artificial Intelligence, pp. 412–416. IOS Press, Amsterdam, Netherlands.
O’Keefe O’Keefe, R. A. (1985). Towards an algebra for constructing logic programs. In SLP 1985, pp. 152–160.
Pelov Pelov, N. (2004). Semantics of Logic Programs with Aggregates. Ph.D. thesis, Katholieke Universiteit Leuven, Leuven.
Pereira and Shieber Pereira, F. C. N., and Shieber, S. M. (2002). Prolog and Natural-Language Analysis. Microtome Publishing, Brookline, Massachusetts.
Plambeck Plambeck, T. (1990a). Semigroup techniques in recursive query optimization. In PODS 1990, pp. 145–153.
Plambeck Plambeck, T. E. (1990b). Semigroups and Transitive Closure in Deductive Databases. Ph.D. thesis, Stanford University, Stanford.
Sterling and Shapiro Sterling, L., and Shapiro, E. (1994). The Art of Prolog: Advanced Programming Techniques (2 edition). The MIT Press, Cambridge MA.
van Emden and Kowalski van Emden, M. H., and Kowalski, R. (1976). The semantics of predicate logic as a programming language. Journal of the ACM, 23(4), 733–742.