# Expressivity of Planning with Horn Description Logic Ontologies
(Technical Report)

Stefan Borgwardt,1 Jörg Hoffmann,2 Alisa Kovtunova,1 Markus Krötzsch,1
Bernhard Nebel,3 Marcel Steinmetz2

###### Abstract

State constraints in AI Planning globally restrict the legal environment
states. Standard planning languages make closed-domain and closed-world
assumptions. Here we address open-world state constraints formalized by
planning over a description logic (DL) ontology. Previously, this combination
of DL and planning has been investigated for the light-weight DL DL-Lite. Here
we propose a novel compilation scheme into standard PDDL with derived
predicates, which applies to more expressive DLs and is based on the
rewritability of DL queries into Datalog with stratified negation. We also
provide a new rewritability result for the DL Horn-$\mathcal{ALCHOIQ}$, which
allows us to apply our compilation scheme to quite expressive ontologies. In
contrast, we show that in the slight extension Horn-$\mathcal{SROIQ}$ no such
compilation is possible unless the weak exponential hierarchy collapses.
Finally, we show that our approach can outperform previous work on existing
benchmarks for planning with DL ontologies, and is feasible on new benchmarks
taking advantage of more expressive ontologies.

##  1 Introduction

AI planning is concerned with sequential decision making problems where an
agent needs to choose actions to achieve a goal, or to maximize reward
(Ghallab, Nau, and Traverso 2004). Such problems are compactly described in a
declarative language. Specifically, in the most basic (“classical”) version of
planning, a planning task describes an initial state of the agent’s
environment, a set of actions that can affect that environment, and a goal
formula that is to be satisfied. In order to reach the goal, actions can be
applied whenever their preconditions are satisfied in the current state. Here
we are interested in _state constraints_ , constraints that should hold
globally, i.e. at every state, in difference to preconditions which merely
need to hold locally. Moreover, standard planning formalisms (based on
variants of the PDDL language (McDermott et al. 1998; Haslum et al. 2019))
follow closed-domain and closed-world assumptions, in which absent facts are
assumed to be false and no new objects can be created. In particular, these
assumptions underly state constraints as can be specified in PDDL3 (Gerevini
et al. 2009). Here we instead target open-domain, open-world reasoning.

One way to do this is via _explicit-input Knowledge and Action Bases (eKABs)_
(Calvanese et al. 2016), where states (sets of ground atoms) are interpreted
using open-world semantics. All states are subject to a _background ontology_
, which describes high-level concepts and global state constraints. Together,
a state and an ontology describe a multitude of possible worlds, which leaves
room for unknown information about existing and unknown objects. For example,
an ontology could express that “everyone operating a machine works for an
engineering department” and “everyone who works for a department is an
employee” without explicitly identifying the department of each person or even
stating that they are employees. Action preconditions contain _queries_ that
are evaluated under open-world semantics, e.g. the query for all “employees”
would return all machine operators among other people. Finally, action effects
add or remove atoms in the state, e.g. reassign machines or departments. This
allows for a clean separation of what is directly observed (i.e. the state,
which contains, e.g. operational data and sensor data) from what is indirectly
inferred (using the ontology).

Calvanese et al. (2016) investigated eKABs with ontologies and queries
formulated in the description logic DL-Lite, which is a popular formalism for
conceptual modeling (Calvanese et al. 2007b). Queries in this logic enjoy
_first-order rewritability_ , which means that the queries and the ontology
can be compiled into first-order (FO) formulas that are then evaluated under
closed-world semantics. Based on this property, the authors described a
compilation of DL-Lite eKABs into classical PDDL planning tasks. Later, this
compilation was further optimized to enable practical planning with DL-Lite
background ontologies (Borgwardt et al. 2021).

The goal of this paper is to extend the expressivity of state constraints in
eKABs from the light-weight DL-Lite to more powerful description logics (DLs)
(Baader et al. 2017). We mainly consider _Horn_ DLs, which are fragments of
Horn-FOL (Krötzsch, Rudolph, and Hitzler 2013; Jung et al. 2019). We
investigate for which Horn DLs compilations into PDDL exist. For this purpose,
we adapt the notion of _compilation schemes_ (Nebel 2000; Thiébaux, Hoffmann,
and Nebel 2005), which relate the expressivity of two formalisms. On the one
hand, polynomial compilation schemes show that the expressivity of DL eKABs is
not higher than that of PDDL. On the other hand, although such eKABs could be
considered syntactic sugar, they represent powerful tools that allow domain
engineers to add open-world constraints to planning tasks.

Our first contribution is a generic compilation scheme for any DL and queries
that enjoy _Datalog ¬-rewritability_, which essentially allows us to compile
them into a set of PDDL _derived predicates_. Using this, we can immediately
employ many existing rewritability results from the DL literature for AI
planning (Ortiz, Rudolph, and Šimkus 2010; Eiter et al. 2012; Bienvenu and
Ortiz 2015). We continue by describing a novel polynomial Datalog¬-rewriting
for queries in the very expressive DL Horn-$\mathcal{ALCHOIQ}$ (Ortiz,
Rudolph, and Šimkus 2011), which allows us to extend the previous
compilability result even further. In contrast to this, we then show that such
a compilation cannot exist (under a reasonable complexity-theoretic
assumption) for the slightly more expressive DL Horn-$\mathcal{SROIQ}$ (Ortiz,
Rudolph, and Šimkus 2011). For this, we follow the idea of a previous non-
compilability result for PDDL with derived predicates into PDDL without
derived predicates (Thiébaux, Hoffmann, and Nebel 2005). This more or less
draws a line between the standardized ontology languages OWL
1,111http://www.w3.org/TR/owl-features/ which results in planning tasks of
equal expressivity as PDDL, and OWL 2,222http://www.w3.org/TR/owl2-overview/
where queries are strictly more expressive than PDDL.

While polynomial rewritings are nice in theory, they are often not practical
due to a polynomial increase in the arity of predicates. We therefore conclude
the paper with an experimental evaluation that combines an existing practical
implementation of an (exponential) Datalog¬-rewriting for
Horn-$\mathcal{SHIQ}$ (Eiter et al. 2012) with our generic compilation scheme,
compares this against previous approaches for DL-Lite eKABs on existing
benchmarks (Calvanese et al. 2016; Borgwardt et al. 2021), and also introduces
new benchmarks exploiting the newly increased expressivity.

##  2 Preliminaries

We first introduce description logics, Datalog¬, planning with derived
predicates and ontologies, and compilations between these formalisms. As
usual, we use the symbol $\models$ with two different meanings: open-world
_entailment_ of formulas from sets of formulas, where all possible
interpretations of arbitrary (even infinite) size are considered, and closed-
world _satisfaction_ of a formula in a fixed, finite interpretation. It should
always be clear from the context which one is used.

#### Description Logics.

Description logics are a family of KR formalisms (Baader et al. 2017) that
describe open-world knowledge using _axioms_ in restricted first-order logic
over unary and binary predicates. Members of this family differ in their
expressivity and complexity. A _TBox_ (_ontology_) is a finite set of _DL
axioms_ , which can be seen as first-order sentences. The precise syntax of
these axioms depends on the specific DL that is used, but this is not
important for most of the paper. A _state_ (_ABox_) is a finite set of _ground
atoms_ $p(\vec{c})$, where $p$ is a predicate and $\vec{c}$ is a sequence of
_objects_ (_constants_). Since we use standard planning formalisms, we also
allow predicates of arity higher than $2$ in states, but those cannot occur in
TBoxes, so essentially have a closed-world semantics. For a state $s$,
$\mathcal{O}(s)$ is the set of all objects occurring in $s$. Two special unary
predicates are $\top$ and $\bot$, which always evaluate to _true_ and _false_
, respectively.

#### Queries.

A _conjunctive query (CQ)_ is a formula of the form
$q(\vec{x})=\exists\vec{y}.\phi(\vec{x},\vec{y})$, where $\phi$ is a
conjunction of unary and binary atoms. A _union of CQs (UCQ)_ is a disjunction
of CQs. An _instance query (IQ)_ is a CQ of the form $p(x)$, where $p$ is
unary. The central reasoning problem is to decide whether
$s,{\mathcal{T}},\theta\models q$, where $s$ is a state, $\mathcal{T}$ a TBox,
and $\theta$ an assignment of objects from $\mathcal{O}(s)$ to the free
variables in the (U)CQ $q$. In an abuse of notation, we may denote with $\bot$
the CQ $\exists x.\bot(x)$. _ECQs_ were introduced to combine open-world and
closed-world reasoning (Calvanese et al. 2007a). We further extend ECQs by
“closed-world atoms” that can also be of higher arity. ECQs are defined by the
grammar $Q::=p(\vec{x})\mid[q]\mid\lnot Q\mid Q\land Q\mid\exists y.Q$, where
$p$ is a predicate, $\vec{x}$ are terms, $q$ is a UCQ, and $y$ is a variable.
The semantics of ECQs is defined as follows:

$\begin{array}[]{@{}l@{\ \ }l@{\ \ }l@{}}s,{\mathcal{T}},\theta\models
p(\vec{x})&\text{iff}&s\models p(\theta(\vec{x}))\\\
s,{\mathcal{T}},\theta\models[q]&\text{iff}&s,{\mathcal{T}},\theta\models q\\\
s,{\mathcal{T}},\theta\models\lnot
Q_{1}&\text{iff}&s,{\mathcal{T}},\theta\not\models Q_{1}\\\
s,{\mathcal{T}},\theta\models Q_{1}\land
Q_{2}&\text{iff}&s,{\mathcal{T}},\theta\models Q_{1}\text{ and
}s,{\mathcal{T}},\theta\models Q_{2}\\\ s,{\mathcal{T}},\theta\models\exists
y.Q_{1}&\text{iff}&\exists o\in\mathcal{O}(s):s,{\mathcal{T}},\theta[y\mapsto
o]\models Q_{1}\end{array}$

There is a difference between the ECQs $B(x)$, which is answered directly in
the (closed-world) model described by $s$, and $[B(x)]$, which is evaluated
w.r.t. the TBox as well. For example, if $s=\\{C(a)\\}$ and
${\mathcal{T}}=\\{C\sqsubseteq B\\}$, then $B(x)$ is not satisfied by any
instantiations, but $[B(x)]$ is.

#### Datalog¬.

A _Datalog ¬ rule_ is a formula $p(\vec{x})\leftarrow\Phi(\vec{x},\vec{y})$
whose _body_ $\Phi(\vec{x},\vec{y})$ is a conjunction of literals and whose
_head_ $p(\vec{x})$ is an atom. A set of Datalog¬ rules $\mathcal{R}$ is
_stratified_ if the set of its predicates can be partitioned into
${\mathcal{P}}_{1},\dots,{\mathcal{P}}_{n}$ such that, for all
$p_{i}\in{\mathcal{P}}_{i}$ and
$p_{i}(\vec{x})\leftarrow\Phi(\vec{x},\vec{y})\in{\mathcal{R}}$,

  * •

if $p_{j}\in{\mathcal{P}}_{j}$ occurs in $\Phi(\vec{x},\vec{y})$, then $j\leq
i$, and

  * •

if $p_{j}\in{\mathcal{P}}_{j}$ occurs negated in $\Phi(\vec{x},\vec{y})$, then
$j<i$.

In the following, all sets of Datalog¬ rules are stratified. Datalog is the
restriction of Datalog¬ to positive rule bodies.

All variables in Datalog¬ rules are implicitly universally quantified. Given a
state $s$ and a set of Datalog¬ rules $\mathcal{R}$, we denote by
${\mathcal{R}}(s)$ the minimal Herbrand model of $s\cup{\mathcal{R}}$.

######  Definition 1.

A TBox $\mathcal{T}$ and a UCQ $q(\vec{x})$ are _Datalog ¬-rewritable_ if
there is a set of Datalog¬ rules ${\mathcal{R}}_{{\mathcal{T}},q}$ with a
predicate $P_{q}$ such that, for all states $s$ and substitutions $\theta$ of
$\vec{x}$ in $\mathcal{O}(s)$, we have $s,{\mathcal{T}},\theta\models
q(\vec{x})$ iff ${\mathcal{R}}_{{\mathcal{T}},q}(s)\models
P_{q}(\theta(\vec{x}))$.

A Datalog¬-rewriting may use additional predicates and constants, but only
needs to be correct for the original symbols. We talk about _Datalog-
rewritability_ if the set ${\mathcal{R}}_{{\mathcal{T}},q}$ does not contain
negation. A variety of such rewritability results for DLs exist, for example a
very complex (but polynomial-size) Datalog-rewriting for IQs over
Horn-$\mathcal{ALCHOIQ}$ (Ortiz, Rudolph, and Šimkus 2010), a polynomial-size
Datalog-rewriting for IQs in ${\mathcal{EL}}^{++}$ (Krötzsch 2011), or an
exponential-size Datalog-rewriting for UCQs over Horn-$\mathcal{SHIQ}$ TBoxes
implemented in the Clipper system333https://github.com/ghxiao/clipper (Eiter
et al. 2012), which is polynomial for the sublogic ${\mathcal{ELH}}_{\bot}$
(Bienvenu and Ortiz 2015).

Datalog¬-rewritability naturally extends to ECQs $Q$: take the disjoint union
${\mathcal{R}}_{{\mathcal{T}},Q}$ of all ${\mathcal{R}}_{{\mathcal{T}},q}$ for
UCQs $q$ occurring in $Q$ and construct an FO formula $Q_{\mathcal{T}}$ by
replacing each UCQ atom $[q(\vec{x})]$ in $Q$ with $P_{q}(\vec{x})$. Then
$s,{\mathcal{T}},\theta\models Q(\vec{x})$ is equivalent to
${\mathcal{R}}_{{\mathcal{T}},Q}(s)\models Q_{\mathcal{T}}(\theta(\vec{x}))$
(Calvanese et al. 2007a).

#### PDDL with Derived Predicates.

We recall PDDL 2.1 extended with derived predicates (Fox and Long 2003;
Hoffmann and Edelkamp 2005). In this context, states are viewed under the
closed-world assumption and all sets are finite.

######  Definition 2.

A _PDDL domain description_ is a tuple
$({\mathcal{P}},{\mathcal{P}}_{\mathsf{der}},{\mathcal{A}},{\mathcal{R}})$,
where ${\mathcal{P}},{\mathcal{P}}_{\mathsf{der}}$ are disjoint sets of
predicates; $\mathcal{A}$ is a set of _actions_ ; and $\mathcal{R}$ is a set
of _rules_. An _action_ is of the form
$(\vec{x},{\mathsf{pre}},{\mathsf{eff}})$, with _parameters_ $\vec{x}$,
_precondition_ $\mathsf{pre}$, and a finite set $\mathsf{eff}$ of _effects_.
The precondition is an FO formula over
${\mathcal{P}}\cup{\mathcal{P}}_{\mathsf{der}}$ with free variables from
$\vec{x}$, and an _effect_ is of the form
$(\vec{y},{\mathsf{cond}},{\mathsf{add}},{\mathsf{del}})$, where $\vec{y}$ are
variables, $\mathsf{cond}$ is an FO formula over
${\mathcal{P}}\cup{\mathcal{P}}_{\mathsf{der}}$ with free variables from
$\vec{x}\cup\vec{y}$, $\mathsf{add}$ is a finite set of atoms over
$\mathcal{P}$ (without ${\mathcal{P}}_{\mathsf{der}}$) with free variables
from $\vec{x}\cup\vec{y}$, and $\mathsf{del}$ is a finite set of such negated
atoms. _Rules_ are of the form $P(\vec{x})\leftarrow\phi(\vec{x})$ with
$P\in{\mathcal{P}}_{\mathsf{der}}$ and a first-order formula $\phi$ over
${\mathcal{P}}\cup{\mathcal{P}}_{\mathsf{der}}$. The set $\mathcal{R}$ must be
_stratified_ , i.e. fulfill the same condition as sets of Datalog¬ rules when
considering the rule bodies $\phi(\vec{x})$ in NNF.

A _PDDL task_ is a tuple $(\Delta,{\mathcal{O}},I,G)$, where $\Delta$ is a
PDDL domain description; $\mathcal{O}$ is a finite set of _objects_ including
the ones in $\Delta$; $I$ is the _initial state_ ; and $G$ is the _goal_ , a
closed FO formula over ${\mathcal{P}}\cup{\mathcal{P}}_{\mathsf{der}}$ and
constants from $\mathcal{O}$.

Derived predicates are not allowed to be modified by actions, i.e. they are
only determined by the current state and the rules. The semantics of rules is
defined similarly to Datalog¬, i.e. for a state $s$, ${\mathcal{R}}(s)$ is the
minimal Herbrand model obtained by exhaustively applying the rules in
${\mathcal{R}}$, stratum by stratum, to the facts in $s$ in order to populate
the derived predicates ${\mathcal{P}}_{\mathsf{der}}$. In fact, all such rule
sets $\mathcal{R}$ can be reformulated into Datalog¬ rule sets (Abiteboul,
Hull, and Vianu 1995; Thiébaux, Hoffmann, and Nebel 2005). Although the
definition of derived predicates requires the head and body to have the same
free variables, this is compatible with the semantics of Datalog¬ since
additional body variables can be viewed as implicitly existentially
quantified.

For an action $a=(\vec{x},{\mathsf{pre}},{\mathsf{eff}})$ and
$\theta\colon\vec{x}\to{\mathcal{O}}$, the _ground action_ $\theta(a)$ has no
parameters. A ground action $a=({\mathsf{pre}},{\mathsf{eff}})$ is
_applicable_ in a state $s$ if ${\mathcal{R}}(s)\models{\mathsf{pre}}$ and its
_application_ yields a new state $s\llbracket a\rrbracket$ that contains a
ground atom $\alpha$ iff (1) there are
$(\vec{y},{\mathsf{cond}},{\mathsf{add}},{\mathsf{del}})\in{\mathsf{eff}}$ and
$\theta$ such that ${\mathcal{R}}(s)\models\theta({\mathsf{cond}})$ and
$\alpha\in\theta({\mathsf{add}})$; or (2) $\alpha\in s$ and for all
$(\vec{y},{\mathsf{cond}},{\mathsf{add}},{\mathsf{del}})\in{\mathsf{eff}}$ and
$\theta$ it holds that ${\mathcal{R}}(s)\not\models\theta({\mathsf{cond}})$ or
$\lnot\alpha\notin\theta({\mathsf{del}})$. A _plan_ $\pi$ is a sequence of
ground actions such that $\pi$ is applicable in $I$ and
${\mathcal{R}}(I\llbracket\pi\rrbracket)\models G$.

#### eKABs.

We recall _explicit-input action and knowledge bases_ (Calvanese et al. 2016),
but slightly adapt the notation to be consistent with PDDL notation.

######  Definition 3.

An _eKAB domain description_ is a tuple
$({\mathcal{P}},{\mathcal{A}},{\mathcal{T}})$, where $\mathcal{P}$ is a finite
set of predicates; $\mathcal{A}$ is a finite set of _DL actions_ ; and
$\mathcal{T}$ is a TBox over the unary and binary predicates in $\mathcal{P}$.
A _DL action_ is of the form $(\vec{x},{\mathsf{pre}},{\mathsf{eff}})$, where
${\mathsf{pre}}$ is an ECQ over $\mathcal{P}$ with free variables from
$\vec{x}$, and $\mathsf{eff}$ consists of _DL effect_ of the form
$(\vec{y},{\mathsf{cond}},{\mathsf{add}},{\mathsf{del}})$, where
$\mathsf{cond}$ is an ECQ over $\mathcal{P}$ with free variables from
$\vec{x}\cup\vec{y}$, and $\mathsf{add}$ and $\mathsf{del}$ are as in PDDL.

An _eKAB (task)_ is a tuple $(\Delta,{\mathcal{O}},{\mathcal{O}}_{0},I,G)$,
where $\Delta$ is an eKAB domain description; $\mathcal{O}$ is a possibly
infinite set of _objects_ ; ${\mathcal{O}}_{0}$ is a finite subset of
$\mathcal{O}$ including the objects from $\Delta$; $I$ is the _initial state_
(over ${\mathcal{O}}_{0}$), which is consistent with $\mathcal{T}$; and $G$ is
the _goal_ , a closed ECQ over $\mathcal{P}$ and constants from
${\mathcal{O}}_{0}$.

A ground action $a$ is _applicable_ in $s$ if $s\models{\mathsf{pre}}$ and
$s\llbracket a\rrbracket\cup{\mathcal{T}}$ is consistent. The _application_
$s\llbracket a\rrbracket$ contains a fact $\alpha$ iff (1’) there are
$(\vec{y},{\mathsf{cond}},{\mathsf{add}},{\mathsf{del}})\in{\mathsf{eff}}$ and
$\theta\colon\vec{y}\to\mathcal{O}(s)\cup{\mathcal{O}}_{0}$ such that
$s,{\mathcal{T}},\theta\models{\mathsf{cond}}$ and
$\alpha\in\theta({\mathsf{add}})$; or (2’) $\alpha\in s$ and for all
$(\vec{y},{\mathsf{cond}},{\mathsf{add}},{\mathsf{del}})\in{\mathsf{eff}}$ and
$\theta$ as above it holds that
$s,{\mathcal{T}},\theta\not\models{\mathsf{cond}}$ or
$\lnot\alpha\notin\theta({\mathsf{del}})$. A _plan_ $\pi$ must be applicable
in $I$ and satisfy $I\llbracket\pi\rrbracket,{\mathcal{T}}\models G$.
Substitutions for effects range over $\mathcal{O}(s)\cup{\mathcal{O}}_{0}$
since the TBox may contain objects from ${\mathcal{O}}_{0}$. In the following,
we assume w.l.o.g. that ${\mathcal{O}}_{0}\subseteq\mathcal{O}(s)$.

#### Additional Assumptions.

Actions can refer to new objects (parameters $\vec{x}$ that are not in the
precondition), and thereby increase the number of objects in a state. To
obtain manageable state transition systems, in the literature the assumption
of _state-boundedness_ is often considered for eKAB-like formalisms; it
requires that there exists a bound $b$ such that any state reachable from $I$
contains at most $b$ objects (Calvanese et al. 2013; De Giacomo et al. 2014).
For a fixed $b$, $b$-boundedness of an eKAB is decidable (De Giacomo et al.
2014). Even if a given eKAB is not state-bounded, one could instead ask for
the existence of a $b$-bounded plan (Ahmetaj et al. 2017). An abstraction
result implies that any $b$-bounded eKAB can be reformulated into one where
$|{\mathcal{O}}|=|{\mathcal{O}}_{0}|+n+b$, where $n$ is the maximum number of
parameters of any action (Calvanese et al. 2013, 2016). Any plan of the
original eKAB can still be encoded using this finite set of objects.
Conversely, any abstract plan can be reformulated into a plan of the original
eKAB by replacing the $n+b$ abstract objects by fresh objects from the
original set $\mathcal{O}$ where necessary (i.e. if those objects did not
occur in the previous state). We will also make this assumption here and
assume for simplicity that ${\mathcal{O}}={\mathcal{O}}_{0}$ is finite and
denote both sets by $\mathcal{O}$.

Even for a $b$-bounded eKAB, the TBox $\mathcal{T}$ can entail the existence
of objects that are not mentioned in a state $s$. These objects are not
affected by the bound $b$, because they are never explicitly materialized in
$s$. Hence, the reasoning problems still employ standard DL semantics rather
than fixed-domain reasoning (Gaggl, Rudolph, and Schweizer 2016).

We also assume that goals of eKAB and PDDL tasks consist of a single (closed-
world) atom $g(\vec{c})$. If that is not the case, we can introduce a new
action with the goal formula $G(\vec{x})$ as precondition that adds
$g(\vec{x})$ to the state. The parameters $\vec{x}$ correspond to the
constants $\vec{c}$ in the original goal formula $G(\vec{c})$. This assumption
simplifies some of the formal definitions, but does not affect our main
insights. Without this assumption, for example, the following definition of
domain compilation $f_{\delta}$ would also need to depend on the goal formula
since we later need to compile all UCQs (also those in the goal) into derived
predicates.

#### Compilations.

To study the relative expressivity of these formalisms, we adapt the notion of
compilation schemes (Nebel 2000; Thiébaux, Hoffmann, and Nebel 2005).

######  Definition 4.

A _compilation scheme_ $\mathbf{f}$ from eKABs to PDDL is a tuple of functions
$(f_{\delta},f_{o},f_{i},f_{g})$ that induces a function $F$ from eKAB tasks
$\Pi=(\Delta,{\mathcal{O}},I,G)$ to PDDL tasks

$F(\Pi):=\big{(}f_{\delta}(\Delta),{\mathcal{O}}\cup
f_{o}(\Delta),f_{i}({\mathcal{O}},I),f_{g}({\mathcal{O}},G)\big{)}$

such that (A) there exists a plan for $\Pi$ iff there exists a plan for
$F(\Pi$); and (B) $f_{i}$ and $f_{g}$ are polynomial-time computable. If
$\|f_{\delta}(\Delta)\|$ and $\|f_{o}(\Delta)\|$ are bounded polynomially
(exponentially) in $\|\Delta\|$, then $\mathbf{f}$ is _polynomial_
(_exponential_).

If for every plan $P$ solving an instance $\Pi$ there exists a plan
$P^{\prime}$ solving $F(\Pi)$ such that $\|P^{\prime}\|\leq c\cdot\|P\|^{n}+k$
for positive integer constants $c,n,k$, we say that $\mathbf{f}$ _preserves
plan size polynomially_. If $n=1$, it _preserves plan size linearly_ , and if
additionally $c=1$, then it _preserves plan size exactly_.

To be considered of the same expressivity, there should be a polynomial
compilation scheme between two formalisms that at least preserves plan size
polynomially, but ideally exactly. Compilation schemes for specific DLs are
restricted to TBoxes $\mathcal{T}$ formulated in the specified DL. For
example, there exists an exponential compilation scheme for DL-Lite eKABs that
rewrites ECQs in-situ into FO conditions (Calvanese et al. 2016). This
compilation has been optimized by Borgwardt et al. (2021) by using derived
predicates to simplify the conditions. In contrast, the compilations we
investigate in the following directly use Datalog¬-rewritings to compile UCQs
into derived predicates.

##  3 Compiling TBoxes into Derived Predicates

We start by describing a generic compilation that exploits
Datalog¬-rewritability of specific DLs to compile open-world ECQs into closed-
world formulas using derived predicates.

One restriction of PDDL derived predicates is that they cannot occur in action
effects. However, Datalog¬-rewritings may derive new facts about the
predicates occurring in the state and TBox, which can also occur in action
effects. To circumvent this issue, we observe that query rewriting is only
necessary for _evaluating conditions_ , but does not affect the states
themselves. Therefore, we separate the condition evaluation and action effects
by using two disjoint signatures of predicates: we use the Datalog¬-rewriting
on a copy $s^{\prime}$ of the state $s$ in which each original predicate $P$
has been replaced by a copy $P^{\prime}$. This copying process can be
simulated by making $P^{\prime}$ a derived predicate with the rule
$P^{\prime}(\vec{x})\leftarrow P(\vec{x})$. In the following, we denote by
${\mathcal{T}}^{\prime}$ the result of replacing each predicate $P$ in
$\mathcal{T}$ by $P^{\prime}$, and likewise for ECQs $Q$.

Another issue is that the rewriting may introduce additional constants, which
are not allowed for instantiating actions, because that would change their
behavior. We simulate this via two new predicates $S$ and $N$ and a new action
$a_{S,N}$ with precondition $\lnot S$ and unconditional effect $S$ and $N(o)$
for all objects $o$ that are not in the original domain description. All other
action conditions are also extended by $S$ and $\lnot
N(\vec{x}):=\bigwedge_{x\in\vec{x}}\lnot N(x)$ for their parameters $\vec{x}$,
to ensure that they can only be instantiated by the original objects.

######  Definition 5.

Let $(({\mathcal{P}},{\mathcal{A}},{\mathcal{T}}),{\mathcal{O}},I,G)$ be a
$b$-bounded eKAB for which all UCQs as well as $\bot$ are Datalog¬-rewritable
w.r.t. $\mathcal{T}$. Let ${\mathcal{R}}_{{\mathcal{T}}^{\prime}}$ be the
disjoint union of ${\mathcal{R}}_{{\mathcal{T}}^{\prime},\bot}$ and all
${\mathcal{R}}_{{\mathcal{T}}^{\prime},Q^{\prime}}$ for ECQs $Q$ in the eKAB.
Then the PDDL task
$(({\mathcal{P}}\cup\\{S,N\\},{\mathcal{P}}^{\prime},{\mathcal{A}}^{\prime},{\mathcal{R}}^{\prime}),{\mathcal{O}}^{\prime},I,G^{\prime})$
is obtained as follows:

  * •

${\mathcal{P}}^{\prime}$ consists of the predicates occurring in
${\mathcal{R}}_{{\mathcal{T}}^{\prime}}$;

  * •

${\mathcal{A}}^{\prime}$ contains $a_{S,N}$ and all actions obtained from
$\mathcal{A}$ by replacing preconditions $\mathsf{pre}$ by $S\land\lnot
N(\vec{x})\land\lnot
P_{\bot}\land{\mathsf{pre}}^{\prime}_{{\mathcal{T}}^{\prime}}$ and effect
conditions $\mathsf{cond}$ by
${\mathsf{cond}}^{\prime}_{{\mathcal{T}}^{\prime}}$;

  * •

${\mathcal{R}}^{\prime}={\mathcal{R}}_{{\mathcal{T}}^{\prime}}\cup\\{P^{\prime}(\vec{x})\leftarrow
P(\vec{x})\mid P\in{\mathcal{P}}\\}$;

  * •

${\mathcal{O}}^{\prime}={\mathcal{O}}\cup\mathcal{O}({\mathcal{R}}_{{\mathcal{T}}^{\prime}})$;
and

  * •

$G^{\prime}=S\land\lnot P_{\bot}\land G$.

The goal does not need to be rewritten w.r.t. $\mathcal{T}$ since we assumed
that it is a single (closed-world) atom.

######  Theorem 1.

Def. 5 is a compilation scheme from Datalog¬-rewritable eKABs to PDDL that
preserves plan size exactly.

###### Proof.

The new goal $G^{\prime}$ can be computed in polynomial time since we only add
$S\land\lnot P_{\bot}$. Moreover, $a_{S,N}$ and the set of rules
${\mathcal{R}}_{{\mathcal{T}}^{\prime}}$ depend only on the objects and
conditions occurring in the original eKAB domain description. We show that all
plans of either planning task are also plans for the other (modulo the
initializing action $a_{S,N}$).

Consistency of $s\cup{\mathcal{T}}$ is equivalent to
${\mathcal{R}}_{{\mathcal{T}}^{\prime},\bot}(s^{\prime})\not\models P_{\bot}$,
where $s^{\prime}$ is obtained from $s$ by replacing each $P$ with
$P^{\prime}$. Hence, the rules $P^{\prime}(\vec{x})\leftarrow P(\vec{x})$ and
the conjuncts $\lnot P_{\bot}$ in all conditions ensure that all states
reached while executing a plan for the PDDL task are consistent with
$\mathcal{T}$. This includes the initial state since $I$ is consistent with
$\mathcal{T}$ by assumption.

Similarly, for any ECQ $Q$, we have ${\mathcal{R}}^{\prime}(s)\models
Q^{\prime}_{{\mathcal{T}}^{\prime}}(\theta(\vec{x}))$ iff
$s^{\prime},{\mathcal{T}}^{\prime},\theta\models Q^{\prime}(\vec{x})$, which
is equivalent to $s,{\mathcal{T}},\theta\models Q(\vec{x})$. Due to $a_{S,N}$,
the substitutions for instantiating action and effect conditions range over
the same objects in both tasks. Hence, both formalisms allow equivalent action
applications in each state and can reach a goal state by the same plans. ∎

For example, this immediately implies that eKABs with Horn-$\mathcal{SHIQ}$
TBoxes have exponential compilations into PDDL with derived predicates
(without negation) and for ${\mathcal{ELH}}_{\bot}$ and DL-Lite we even obtain
polynomial compilations (Eiter et al. 2012; Bienvenu and Ortiz 2015). The
latter also holds for Horn-$\mathcal{SHOIQ}$ if all conditions are restricted
to EIQs (Ortiz, Rudolph, and Šimkus 2010). In general, our construction
applies to any ontology language where UCQs (or IQs) are Datalog¬-rewritable,
and to any specific TBoxes and queries that happen to be Datalog¬-rewritable.

##  4 A Polynomial Rewriting for Horn-$\mathcal{ALCHOIQ}$

To extend the compilability results, we develop a polynomial-size rewriting
for UCQs over Horn-$\mathcal{ALCHOIQ}$ into Datalog¬. It is based on a query
answering approach developed by Carral, Dragoste, and Krötzsch (2018) and
encodes the relevant definitions from their paper into DatalogS,¬ rules, which
extend Datalog¬ by _set terms_ that denote sets of objects. We then adapt a
known polynomial translation to obtain a set of Datalog¬ rules (Ortiz,
Rudolph, and Šimkus 2010).

The full details can be found in the appendix, but we describe the main ideas
here. The rewriting starts by translating the Horn-$\mathcal{ALCHOIQ}$ axioms
of the given TBox $\mathcal{T}$ into Datalog rules (Carral, Dragoste, and
Krötzsch 2018). However, since the resulting rule set is exponential, we here
reformulate it into polynomially many DatalogS,¬ rules, loosely following
ideas from Ortiz, Rudolph, and Šimkus (2010). The original approach uses
exponentially many constants $t_{X}$, where $X$ is a set of unary predicates,
to describe anonymous objects that satisfy $X$. In DatalogS,¬, these
individuals can directly be described by sets $\\{X\\}$ that can be used as
arguments to predicates. For example, our rewriting introduces a new predicate
${\mathsf{role}}(r,X,Y)$ to express that the objects represented by $X$ and
$Y$ are connected by the binary predicate $r$, which is now viewed as an
additional element of $\mathcal{O}$. Using such additional predicates, the
translation of the original Datalog rules by Carral, Dragoste, and Krötzsch
(2018) is straightforward.

The remainder of the rewriting encodes the _filtration phase_ from that paper
into several strata of DatalogS,¬ rules. We use bespoke predicates to encode
the constructions of expanded states and graphs in Definitions 7 and 8 in
(Carral, Dragoste, and Krötzsch 2018), e.g. to compute a partial expansion of
the input state to obtain more query matches and an acyclicity check over a
dependency graph between query variables to filter out spurious matches. After
a translation from DatalogS,¬ into Datalog¬ (Ortiz, Rudolph, and Šimkus 2010),
correctness of the rewriting follows mostly from Theorem 3 in the paper by
Carral, Dragoste, and Krötzsch (2018).

######  Theorem 2.

UCQs over Horn-$\mathcal{ALCHOIQ}$ TBoxes are Datalog¬-rewritable with
rewritings of polynomial size.

By Theorem 1, we thus obtain a polynomial compilation scheme for
Horn-$\mathcal{ALCHOIQ}$ eKABs into PDDL that preserves plan size exactly.
Admittedly, this construction is rather complex, but theoretically very
interesting, in particular in light of the next section.

##  5 Non-Compilability for Expressive eKABs

As a counterpoint to the previous section, we now prove that polynomial
compilations cannot exist for Horn-$\mathcal{SROIQ}$, not even if we allow the
plan size to increase polynomially. Horn-$\mathcal{SROIQ}$ differs from
Horn-$\mathcal{ALCHOIQ}$ only in allowing one additional type of axiom, called
_complex role inclusions_. The following result is inspired by a similar non-
compilability result for PDDL with derived predicates (Thiébaux, Hoffmann, and
Nebel 2005). We start with some observations about the complexity of the
involved problems. The _polynomial-step planning problem_ is to decide whether
a given planning task has a plan of length polynomial (for some given
polynomial), and the _1-step planning problem_ is the special case where the
polynomial is $1$.

######  Theorem 3.

The polynomial-step planning problem for PDDL is ExpTime-complete.

###### Proof.

Hardness follows from the complexity of the 1-step planning problem for PDDL
with derived predicates (Thiébaux, Hoffmann, and Nebel 2005, Theorem 1).
Membership can be seen as follows. In exponential time, we can enumerate all
plans of polynomial length (for a fixed polynomial). For each such plan, we
can check whether each ground action was applicable, which facts were
generated or deleted, and whether the goal is satisfied in the end. The most
complex part of this check is the evaluation of the derived predicates after
each action, which can be done in exponential time (Dantsin et al. 2001). ∎

######  Theorem 4.

The 1-step planning problem for Horn-$\mathcal{SROIQ}$ eKABs is 2ExpTime-
complete.

###### Proof.

Hardness follows from the complexity of reasoning in Horn-$\mathcal{SROIQ}$
(Ortiz, Rudolph, and Šimkus 2010). Membership holds since we can enumerate all
candidate 1-step plans in PSpace, the CQs in preconditions and the goal can be
evaluated in 2ExpTime (Ortiz, Rudolph, and Šimkus 2011) and the remaining
parts of the ECQs can be evaluated in PSpace (Abiteboul, Hull, and Vianu
1995). ∎

While these complexity results already indicate that reasoning in
Horn-$\mathcal{SROIQ}$ is more powerful than (polynomial) planning in PDDL
with derived predicates, they tell us nothing about the relative expressivity
of these two formalisms. There could still exist a polynomial-size compilation
scheme from the former to the latter that preserves plan size polynomially,
because the compilation can use arbitrary computational resources as long as
the result is of polynomial size.

To prove that such a compilation indeed cannot exist, we follow Thiébaux,
Hoffmann, and Nebel (2005) by using the notion of _advice-taking_ Turing
machines (Karp and Lipton 1982). Such machines are equipped with an advice
oracle $a$, which is a function from positive integers to bit strings. On
input $w$, the machine receives the _advice_ $a(\|w\|)$ and then starts its
computation as usual. The advice depends only on the length of the input, but
not on its contents. An advice oracle is _polynomial_ if the length of
$a(\|w\|)$ is bounded polynomially in $\|w\|$. ExpTime/poly (_non-uniform_
ExpTime) is the class of problems that can be decided by Turing machines with
polynomial advice and exponential time bound.

The following result shows that a polynomial compilation scheme from
Horn-$\mathcal{SROIQ}$ eKABs to PDDL would imply that the weak exponential
hierarchy collapses completely. The latter is considered to be unlikely; in
particular, it would mean that one can eliminate any bounded quantifier prefix
in second-order logic and Presburger arithmetic (Gottlob, Leone, and Veith
1995; Haase 2014).

######  Theorem 5.

Unless ${\text{{{ExpTime}}}}^{\text{{{NP}}}}={\text{{{ExpTime}}}}$, there is
no polynomial compilation scheme from Horn-$\mathcal{SROIQ}$ eKABs to PDDL
preserving plan size polynomially.

###### Proof sketch.

Let $M$ be a universal Turing machine with double-exponential time bound that
can simulate all other such TMs. In the appendix, we show how to construct a
family of Horn-$\mathcal{SROIQ}$ eKAB domain descriptions $\Delta_{n}$ such
that $M$ accepts a word $w$ of length $n$ iff
$(\Delta_{n},{\mathcal{O}},I_{w},g)$ has a plan of length $1$. Here,
${\mathcal{O}}$ contains only the two objects $o$ and $e$, $I_{w}$ is a state
that can be computed from $w$ in polynomial time, and $g$ is a nullary
predicate. This construction is based on the 2ExpTime-hardness proof for
Horn-$\mathcal{SROIQ}$ (Ortiz, Rudolph, and Šimkus 2010).

Assume now that there is a compilation scheme
$\mathbf{f}=(f_{\delta},f_{o},f_{i},f_{g})$ from Horn-$\mathcal{SROIQ}$ eKABs
to PDDL preserving plan size polynomially. This scheme could be used as an
advice oracle as follows. Let $M^{\prime}$ be a TM with double-exponential
time bound. Then $M^{\prime}$ accepts $w^{\prime}$ iff $M$ accepts
$w=M^{\prime}\\#w^{\prime}$ (in some fixed encoding). Let $n$ be the size of
$w$. The compilation of $\Delta_{n}$ to a PDDL domain description
$\Delta_{n}^{\prime}=f_{\delta}(\Delta_{n})$ as well as $f_{o}(\Delta_{n})$
can be used as polynomial advice for a Turing machine that, on input $w$,
computes ${\mathcal{O}}=\\{o,e\\}$, $I_{w}$, and
$(\Delta_{n}^{\prime},{\mathcal{O}}\cup
f_{o}(\Delta_{n}),f_{i}({\mathcal{O}},I_{w}),f_{g}({\mathcal{O}},g))$, which
can be done in polynomial time. It then decides polynomial-step plan existence
for this PDDL task, which can be done in ExpTime by Theorem 3 and is
equivalent to deciding whether $M^{\prime}$ accepts $w^{\prime}$ by Definition
5. Overall, this implies that
${\text{{{ExpTime}}}}^{\text{{{NP}}}}\subseteq\text{{{2ExpTime}}}$ is included
in ExpTime/poly, and therefore
${\text{{{ExpTime}}}}^{\text{{{NP}}}}={\text{{{ExpTime}}}}$ (Buhrman and Homer
1992), which contradicts the assumption of the theorem. ∎

######  Corollary 1.

Unless ${\text{{{ExpTime}}}}^{\text{{{NP}}}}={\text{{{ExpTime}}}}$, in general
there can be no polynomial Datalog¬-rewritings for IQs over
Horn-$\mathcal{SROIQ}$ TBoxes.

###### Proof.

By Theorem 1, such a rewriting would yield a polynomial compilation from
Horn-$\mathcal{SROIQ}$ eKABs to PDDL preserving plan size exactly, which
contradicts the assumption by Theorem 5. ∎

We obtain a similar result also for the non-Horn DLs $\mathcal{SH}$ and
$\mathcal{ALCI}$, because for them similar 2ExpTime-hardness proofs can be
adapted (Lutz 2008; Eiter et al. 2009a).

######  Theorem 6.

Unless ${\text{{{ExpTime}}}}^{\text{{{NP}}}}={\text{{{ExpTime}}}}$, there is
no polynomial compilation scheme from $\mathcal{SH}$ or $\mathcal{ALCI}$ eKABs
to PDDL preserving plan size polynomially.

##  6 Experiments

While polynomial compilations are nice in theory, they have one major
drawback: the size of the rules and in particular the arity of the new
predicates grows polynomially with the input (Carral and Krötzsch 2020). In
contrast, the existing exponential compilation from Horn-$\mathcal{SHIQ}$ to
Datalog uses rules of constant size and in many cases does not exhibit an
exponential blowup (Eiter et al. 2012). Moreover, from a pragmatic
perspective, it is the only Datalog rewriting for CQs over Horn-DLs that has
been implemented so far, in the Clipper system. We thus implemented our
compilation from Section 3 using Clipper to answer the following questions: 1)
Is the compilation feasible, i.e. can the generated classical planning tasks
be handled by state-of-the-art planners? 2) How does our compilation perform
against existing eKAB compilations?

For the experiments, we use the Fast Downward (FD) planning system (Helmert
2006) version 20.06 (the newest version as of August 2021), the main
implementation platform for classical planning today. We ran FD with a dual-
queue greedy best-first search using the $h^{\textup{FF}}$ heuristic, a
commonly used baseline in the planning literature. All experiments were run on
a computer with an Intel Core i5-4590<EMAIL_ADDRESS>and run time and memory
cutoffs of 600s and 8GBs, respectively. The benchmarks and the compiler are
available online.444https://gitlab.perspicuous-
computing.science/a.kovtunova/pddl-horndl

#### Implementation.

We encode Horn-$\mathcal{SHIQ}$ eKAB tasks as ontology files accompanied by
PDDL files whose syntax has been extended to allow conjunctive queries. The
ontology file uses Turtle syntax, which can be processed by any off-the-shelf
ontology tool. Our compiler reads the CQ-PDDL and ontology files, and
generates a classical planning task in standard PDDL format. The Datalog
rewriting is generated with Clipper (Eiter et al. 2012). The compilation
additionally normalizes complex conditions via a Tseitin-like transformation
(Tseitin 1983), which has been shown to be effective before (Borgwardt et al.
2021).

Figure 1: Comparison of the Robot (dashed) and RobotConj (solid) domains w.r.t. domain description size, compilation and planning times. |  | # solved | # compiled | planning time | compilation time
---|---|---|---|---|---
Domain | # | Cal16 | Bor21 | Horn | Cal16 | Bor21 | Horn | Cal16 | Bor21 | Horn | Cal16 | Bor21 | Horn
Cats | 20 | 14 | 20 | 20 | 20 | 20 | 20 | 63.46 | 0.13 | 0.03 | 0.16 | 0.22 | 0.65
Elevator | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 0.36 | 0.30 | 0.03 | 0.60 | 0.73 | 0.66
Robot | 20 | 4 | 12 | 20 | 12 | 12 | 20 | 15.05 | 10.10 | 0.11 | 138.52 | 138.55 | 0.75
TaskAssign | 20 | 3 | 20 | 20 | 20 | 20 | 20 | 0.81 | 0.12 | 0.06 | 2.87 | 39.21 | 0.66
TPSA | 15 | 14 | 5 | 15 | 15 | 5 | 15 | 2.01 | 2.42 | 0.30 | 0.84 | 25.37 | 0.59
VTA | 15 | 15 | 13 | 15 | 15 | 15 | 15 | 23.06 | 371.56 | 16.91 | 0.33 | 1.21 | 0.65
VTA-Roles | 15 | 15 | 5 | 15 | 15 | 5 | 15 | 2.25 | 11.61 | 1.36 | 0.59 | 95.53 | 0.66
$\sum$ | 125 | 85 | 95 | 125 | 117 | 97 | 125 | 19.99 | 77.33 | 3.59 | 18.01 | 31.84 | 0.66
Drones | 24 |  |  | 20 |  |  | 24 |  |  | 101.42 |  |  | 0.69
Queens | 30 |  |  | 15 |  |  | 30 |  |  | 21.66 |  |  | 0.69
RobotConj | 56 |  |  | 56 |  |  | 56 |  |  | 8.14 |  |  | 2.77
$\sum$ | 110 |  |  | 91 |  |  | 110 |  |  | 30.87 |  |  | 1.75
Table 1: Per-domain aggregated statistics: “# solved” number of instances
solved by the planner; “# compiled” number of instances for which the
compilers could generate the PDDL input files for the planner; “planning time”
average planner run time over the commonly solved instances; “compilation
time” average time of generating the PDDL files.

#### Benchmarks.

Our benchmark collection consists of $125$ instances adapted from existing DL-
Lite eKAB benchmarks (Calvanese et al. 2016; Borgwardt et al. 2021), and $110$
newly created instances. A detailed description can be found in the appendix.
We manually translated the existing eKAB domains (Cats, Elevator, Robot,
TaskAssign, TPSA, VTA, and VTA-Roles) into the format described above.
Modifications almost exclusively pertained to extracting the ontology from the
eKAB description into a separate Turtle file and moving so-called condition-
action rules (Calvanese et al. 2016) into action preconditions. The translated
instances are equivalent to the originals.

Since Horn-$\mathcal{SHIQ}$ is more expressive than DL-Lite, we also created
$3$ new domains (Drones, Queens, and RobotConj) in which we make use of
conjunctions, qualified existential restrictions occurring with negative
polarity, and symmetric and transitive relations, all of which are not
supported by DL-Lite (Baader et al. 2017). Drones describes a complex 2D drone
navigation problem, in which drones need to be moved to avoid critical
situations; the latter are described in the ontology using axioms with
qualified existential restrictions and symmetric relations. Queens generalizes
the eight queens puzzle to board sizes $n\in\\{5,\dots,10\\}$ and numbers of
queens $m\in\\{n-4,\dots,n\\}$. Queens are initially placed randomly on the
board and need to be moved to a configuration where no queen threatens
another. The ontology contains a symmetric, transitive relation to describe
legal moves. RobotConj is a redesign of Robot that moves some of the
complexity from actions into the ontology. The original Robot benchmark
encodes static knowledge about 2D grid cell adjacency in the action
descriptions, which can be encoded much more naturally in the ontology using
conjunctions. Note that the original Robot benchmark consists of 20 instances
(grid sizes $3\times 3$ up to $22\times 22$), whereas for the new RobotConj we
included 56 instances (up to $200\times 200$) since they could be easily
handled by our compiler.

#### Scalability Study.

We use Robot and RobotConj to analyze how our compilation performs as a
function of domain description size (including the ontology). Figure 1 depicts
the results for $56$ instances of each domain, obtained by scaling the grid
from $3\times 3$ to $200\times 200$. In both domains, the file size is
directly proportional to size of the grid. Even the largest tested instance
could be compiled and solved in less than $90$ seconds, attesting the
feasibility of our approach. The increased complexity of RobotConj’s ontology
does not affect the performance. On the contrary, both compilation and
planning for RobotConj are actually consistently faster than for Robot, due to
the simplified actions.

#### Comparison to DL-Lite Compilations.

We compare to Cal16, the original DL-Lite eKAB compiler (Calvanese et al.
2016), and to Bor21, its recently introduced optimization using derived
predicates to compile away complex formulas (Borgwardt et al. 2021). We refer
to our compilation by Horn. Table 1 gives a summary of the results. Cal16 and
Bor21 were only run on the original DL-Lite eKAB benchmarks.

Considering the DL-Lite benchmark part, Horn has similar or better performance
than Cal16 and Bor21. In Robot, the Cal16 compilation (and hence also Bor21)
could only process the $12$ smallest instances (up to grid size $14\times
14$), exceeding the $600$ seconds time limit thereafter. While Cal16 and Bor21
both show a blow-up in compilation time in some domains, our new Horn compiler
could process all instances in less than $1$ second on average. The
compilation time of Horn is almost consistently larger than $0.6$ seconds,
which can be attributed to the fixed overhead of calling Clipper. While the
compilation time of Horn is very competitive with the previous DL-Lite
compilers, the planner’s performance statistics really substantiate this
advantage. Regarding planning time and the number of solved instances, Horn
significantly outperforms both alternatives on the DL-Lite benchmarks.

The more complex ontologies in the Horn-$\mathcal{SHIQ}$ benchmark part did
not pose a challenge to Horn. All instances could still be translated within
$3$ seconds on average. The constructed instances of Drones and Queens are
however much more challenging from a planning perspective. Contrary to the DL-
Lite benchmarks before, average planning runtime is higher, and some instances
could not be solved in time. The difficulty of the instances was chosen
intentionally, with the purpose of creating challenging problems for future
work.

##  7 Conclusion

We have shown that adding Horn-DL background ontologies often does not
increase the expressivity of PDDL planning tasks. This is due to
Datalog¬-rewritability, which allows us to reduce open-world to closed-world
reasoning. However, adding more axiom types (Horn-$\mathcal{SROIQ}$) or using
non-Horn DLs ($\mathcal{SH}$ or $\mathcal{ALCI}$) increases the expressivity
beyond PDDL, unless the weak exponential hierarchy collapses. An evaluation of
our generic compilation approach using the Clipper system demonstrates the
feasibility of using Datalog¬-rewritings, even compared to more specialized
compilation schemes for the smaller logic DL-Lite. Moreover, we have
contributed additional benchmarks to showcase the increased expressivity of
our proposed approach.

In future work, we will investigate the existence of a polynomial compilation
scheme for Horn-$\mathcal{SHOIQ}$, whose expressivity lies between that of
Horn-$\mathcal{ALCHOIQ}$ and Horn-$\mathcal{SROIQ}$. We also want to
investigate planning formalisms with different effect semantics, e.g. the one
described by De Giacomo et al. (2021).

## Acknowledgements

This work is supported by DFG grant 389792660 as part of TRR 248 – CPEC
(https://perspicuous-computing.science).

## References

  * Abiteboul, Hull, and Vianu (1995) Abiteboul, S.; Hull, R.; and Vianu, V. 1995.  _Foundations of Databases_.  Addison-Wesley.
  * Ahmetaj et al. (2017) Ahmetaj, S.; Calvanese, D.; Ortiz, M.; and Šimkus, M. 2017.  Managing Change in Graph-Structured Data Using Description Logics.  _ACM Transactions on Computational Logic_ , 18(4): 27:1–27:35.
  * Baader et al. (2017) Baader, F.; Horrocks, I.; Lutz, C.; and Sattler, U. 2017.  _An Introduction to Description Logic_.  Cambridge University Press.
  * Bienvenu and Ortiz (2015) Bienvenu, M.; and Ortiz, M. 2015.  Ontology-Mediated Query Answering with Data-Tractable Description Logics.  In Faber, W.; and Paschke, A., eds., _Reasoning Web. 11th Int. Summer School_ , volume 9203 of _Lecture Notes in Computer Science_ , 218–307. Springer.
  * Borgwardt et al. (2021) Borgwardt, S.; Hoffmann, J.; Kovtunova, A.; and Steinmetz, M. 2021.  Making DL-Lite Planning Practical.  In Bienvenu, M.; and Lakemeyer, G., eds., _Proc. of the 18th Int. Conf. on Principles of Knowledge Representation and Reasoning (KR’21)_ , 641–645. IJCAI.
  * Buhrman and Homer (1992) Buhrman, H.; and Homer, S. 1992.  Superpolynomial Circuits, Almost Sparse Oracles and the Exponential Hierarchy.  In Shyamasundar, R., ed., _Proc. of the 12th Conf. on Foundations of Software Technology and Theoretical Computer Science (FSTTCS’92)_ , volume 652 of _Lecture Notes in Computer Science_ , 116–127. Springer-Verlag.
  * Calvanese et al. (2007a) Calvanese, D.; De Giacomo, G.; Lembo, D.; Lenzerini, M.; and Rosati, R. 2007a.  EQL-Lite: Effective First-Order Query Processing in Description Logics.  In Veloso, M. M., ed., _20th Int. Joint Conf. on Artificial Intelligence (IJCAI)_ , 274–279.
  * Calvanese et al. (2007b) Calvanese, D.; De Giacomo, G.; Lembo, D.; Lenzerini, M.; and Rosati, R. 2007b.  Tractable Reasoning and Efficient Query Answering in Description Logics: The DL-Lite Family.  _Journal of Automated Reasoning_ , 39(3): 385–429.
  * Calvanese et al. (2013) Calvanese, D.; De Giacomo, G.; Montali, M.; and Patrizi, F. 2013.  Verification and Synthesis in Description Logic Based Dynamic Systems.  In Faber, W.; and Lembo, D., eds., _7th Int. Conf. Web Reasoning and Rule Systems (RR)_ , 50–64. Springer.
  * Calvanese et al. (2016) Calvanese, D.; Montali, M.; Patrizi, F.; and Stawowy, M. 2016.  Plan Synthesis for Knowledge and Action Bases.  In Kambhampati, S., ed., _25th Int. Joint Conf. on Artificial Intelligence (IJCAI)_ , 1022–1029. AAAI Press.
  * Carral, Dragoste, and Krötzsch (2018) Carral, D.; Dragoste, I.; and Krötzsch, M. 2018.  The Combined Approach to Query Answering in Horn-$\mathcal{ALCHOIQ}$.  In Thielscher, M.; Toni, F.; and Wolter, F., eds., _Proc. of the 16th Int. Conf. on Principles of Knowledge Representation and Reasoning (KR’18)_ , 339–348. AAAI Press.
  * Carral and Krötzsch (2020) Carral, D.; and Krötzsch, M. 2020.  Rewriting the Description Logic $\mathcal{ALCHIQ}$ to Disjunctive Existential Rules.  In Bessiere, C., ed., _Proc. of the 29th Int. Joint Conf. on Artificial Intelligence and the 17th Pacific Rim Int. Conf. on Artificial Intelligence (IJCAI-PRICAI’20)_ , 1777–1783. IJCAI.
  * Dantsin et al. (2001) Dantsin, E.; Eiter, T.; Gottlob, G.; and Voronkov, A. 2001.  Complexity and Expressive Power of Logic Programming.  _ACM Computing Surveys_ , 33(3): 374–425.
  * De Giacomo et al. (2014) De Giacomo, G.; Lespérance, Y.; Patrizi, F.; and Vassos, S. 2014.  Progression and Verification of Situation Calculus Agents with Bounded Beliefs.  In amd Paul Scerri, A. L.; Bazzan, A.; and Huhns, M., eds., _13th Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS)_ , 141–148. ACM.
  * De Giacomo et al. (2021) De Giacomo, G.; Oriol, X.; Rosati, R.; and Savo, D. F. 2021.  Instance-Level Update in DL-Lite Ontologies through First-Order Rewriting.  _Journal of Artificial Intelligence Research_ , 70: 1335–1371.
  * Eiter et al. (2009a) Eiter, T.; Lutz, C.; Ortiz, M.; and Šimkus, M. 2009a.  Query Answering in Description Logics with Transitive Roles.  In Boutilier, C., ed., _Proc. of the 21st Int. Joint Conf. on Artificial Intelligence (IJCAI’09)_ , 759–764. AAAI Press.
  * Eiter et al. (2009b) Eiter, T.; Lutz, C.; Ortiz, M.; and Šimkus, M. 2009b.  Query Answering in Description Logics with Transitive Roles.  INFSYS Research Report 1843-09-02, Institut für Informationssysteme, TU Wien.
  * Eiter et al. (2012) Eiter, T.; Ortiz, M.; Šimkus, M.; Tran, T.-K.; and Xiao, G. 2012.  Query Rewriting for Horn-$\mathcal{SHIQ}$ Plus Rules.  In Hoffmann, J.; and Selman, B., eds., _Proc. of the 26th AAAI Conf. on Artificial Intelligence (AAAI’12)_ , 726–733. AAAI Press.
  * Fox and Long (2003) Fox, M.; and Long, D. 2003.  PDDL2.1: An Extension to PDDL for Expressing Temporal Planning Domains.  _Journal of Artificial Intelligence Research_ , 20: 61–124.
  * Gaggl, Rudolph, and Schweizer (2016) Gaggl, S. A.; Rudolph, S.; and Schweizer, L. 2016.  Fixed-Domain Reasoning for Description Logics.  In Kaminka, G. A.; Fox, M.; Bouquet, P.; Hüllermeier, E.; Dignum, V.; Dignum, F.; and van Harmelen, F., eds., _Proc. of the 22nd Eur. Conf. on Artificial Intelligence (ECAI’16)_ , volume 285 of _Frontiers in Artificial Intelligence and Applications_ , 819–827. IOS Press.
  * Gerevini et al. (2009) Gerevini, A.; Haslum, P.; Long, D.; Saetti, A.; and Dimopoulos, Y. 2009.  Deterministic planning in the fifth international planning competition: PDDL3 and experimental evaluation of the planners.  _Artificial Intelligence_ , 173(5-6): 619–668.
  * Ghallab, Nau, and Traverso (2004) Ghallab, M.; Nau, D.; and Traverso, P. 2004.  _Automated Planning: Theory and Practice_.  Morgan Kaufmann.
  * Gottlob, Leone, and Veith (1995) Gottlob, G.; Leone, N.; and Veith, H. 1995.  Second Order Logic and the Weak Exponential Hierarchies.  In Wiedermann, J.; and Hájek, P., eds., _Proc. of the 20th Int. Symp. on Mathematical Foundations of Computer Science (MFCS’95)_ , volume 969 of _Lecture Notes in Computer Science_ , 66–81. Springer-Verlag.
  * Haase (2014) Haase, C. 2014.  Subclasses of Presburger Arithmetic and the Weak EXP Hierarchy.  In Henzinger, T.; and Miller, D., eds., _Proc. of the Joint Meeting of the 23rd EACSL Annual Conf. on Computer Science Logic (CSL) and the 29th Annual ACM/IEEE Symp. on Logic in Computer Science (LICS)_ , 14:1–14:10. ACM.
  * Haslum et al. (2019) Haslum, P.; Lipovetzky, N.; Magazzeni, D.; and Muise, C. 2019.  An introduction to the planning domain definition language.  _Synthesis Lectures on Artificial Intelligence and Machine Learning_ , 13(2): 1–187.
  * Helmert (2006) Helmert, M. 2006.  The Fast Downward Planning System.  _Journal of Artificial Intelligence Research_ , 26: 191–246.
  * Hoffmann and Edelkamp (2005) Hoffmann, J.; and Edelkamp, S. 2005.  The Deterministic Part of IPC-4: An Overview.  _Journal of Artificial Intelligence Research_ , 24: 519–579.
  * Hoffmann et al. (2008) Hoffmann, J.; Weber, I.; Scicluna, J.; Kacmarek, T.; and Ankolekar, A. 2008.  Combining Scalability and Expressivity in the Automatic Composition of Semantic Web Services.  In _8th International Conference on Web Engineering (ICWE’08)_.
  * Jung et al. (2019) Jung, J. C.; Papacchini, F.; Wolter, F.; and Zakharyaschev, M. 2019.  Model Comparison Games for Horn Description Logics.  In Bouyer, P., ed., _Proc. of the 34th Annual IEEE Symp. on Logic in Computer Science (LICS’19)_ , 1–14. IEEE.
  * Karp and Lipton (1982) Karp, R. M.; and Lipton, R. J. 1982.  Turing Machines that Take Advice.  _L’Enseignement Mathématique_ , 28: 191–209.
  * Krötzsch (2011) Krötzsch, M. 2011.  Efficient Rule-Based Inferencing for OWL EL.  In Walsh, T., ed., _Proc. of the 22nd Int. Joint Conf. on Artificial Intelligence (IJCAI’11)_ , 2668–2773. AAAI Press.
  * Krötzsch, Rudolph, and Hitzler (2013) Krötzsch, M.; Rudolph, S.; and Hitzler, P. 2013.  Complexities of Horn Description Logics.  _ACM Transactions on Computational Logic_ , 14(1): 2:1–2:36.
  * Lutz (2007) Lutz, C. 2007.  Inverse Roles Make Conjunctive Queries Hard.  In Calvanese, D.; Franconi, E.; Haarslev, V.; Lembo, D.; Motik, B.; Turhan, A.-Y.; and Tessaris, S., eds., _Proc. of the 20th Int. Workshop on Description Logics (DL’07)_ , volume 250 of _CEUR Workshop Proceedings_ , 100–111.
  * Lutz (2008) Lutz, C. 2008.  The Complexity of Conjunctive Query Answering in Expressive Description Logics.  In _Proc. of the 4th Int. Joint Conf. on Automated Reasoning (IJCAR’08)_ , volume 5195 of _Lecture Notes in Artificial Intelligence_ , 179–193. Springer-Verlag.
  * McDermott et al. (1998) McDermott, D.; Ghallab, M.; Howe, A.; Knoblock, C.; Ram, A.; Veloso, M.; Weld, D.; and Wilkins, D. 1998.  _The PDDL Planning Domain Definition Language_.  The AIPS-98 Planning Competition Comitee.
  * Nebel (2000) Nebel, B. 2000.  On the Compilability and Expressive Power of Propositional Planning Formalisms.  _Journal of Artificial Intelligence Research_ , 12: 271–315.
  * Ortiz, Rudolph, and Šimkus (2010) Ortiz, M.; Rudolph, S.; and Šimkus, M. 2010.  Worst-case Optimal Reasoning for the Horn-DL Fragments of OWL 1 and 2.  In Lin, F.; Sattler, U.; and Truszczynski, M., eds., _Proc. of the 12th Int. Conf. on Principles of Knowledge Representation and Reasoning (KR’10)_ , 269–279. AAAI Press.
  * Ortiz, Rudolph, and Šimkus (2011) Ortiz, M.; Rudolph, S.; and Šimkus, M. 2011.  Query Answering in the Horn Fragments of the Description Logics $\mathcal{SHOIQ}$ and $\mathcal{SROIQ}$.  In Walsh, T., ed., _Proc. of the 22nd Int. Joint Conf. on Artificial Intelligence (IJCAI’11)_ , 1039–1044. AAAI Press.
  * Thiébaux, Hoffmann, and Nebel (2005) Thiébaux, S.; Hoffmann, J.; and Nebel, B. 2005.  In Defense of PDDL Axioms.  _Artificial Intelligence_ , 168: 38–69.
  * Tseitin (1983) Tseitin, G. S. 1983.  On the Complexity of Derivation in Propositional Calculus.  In Siekmann, J. H.; and Wrightson, G., eds., _Automation of Reasoning: 2: Classical Papers on Computational Logic 1967–1970_ , 466–483. Springer Berlin Heidelberg.  ISBN 978-3-642-81955-1.

##  Appendix A Proof of Theorem 2

We first describe the logic Horn-$\mathcal{ALCHOIQ}$ in more detail. We use
classical DL terms here, i.e. unary predicates are called _concept names_ ,
binary predicates are _role names_ , objects/constants are _individual names_
and states are _ABoxes_. We assume that all axioms in Horn-$\mathcal{ALCHOIQ}$
TBoxes are in _normal form_ (Carral, Dragoste, and Krötzsch 2018), i.e. they
have one of the following shapes, where $C,C_{1},\dots,C_{n},D$ are concept
names, $r,s$ are role names, and $a$ is an individual name:

  1. (i)

$C_{1}\sqcap\dots\sqcap C_{n}\sqsubseteq D$

  2. (ii)

$C\sqsubseteq\exists r.D$

  3. (iii)

$\exists r.C\sqsubseteq D$

  4. (iv)

$C\sqsubseteq{\leq 1}r.D$

  5. (v)

$C\sqsubseteq\\{a\\}$

  6. (vi)

$r\sqsubseteq s$

  7. (vii)

$\\{a\\}\sqsubseteq C$

We added the last axiom type here since our goal is a TBox rewriting that is
independent of the ABox, i.e. we need to distinguish the TBox axiom
$\\{a\\}\sqsubseteq C$ from the (equivalent) ABox fact $C(a)$. A first-order
interpretation $\mathcal{I}$ satisfies these axioms if it satisfies the
sentences

  1. (i)

$\forall x.C_{1}(x)\land\dots\land C_{n}(x)\to D(x)$,

  2. (ii)

$\forall x.C(x)\to\exists y.r(x,y)\land D(y)$,

  3. (iii)

$\forall x,y.r(x,y)\land C(y)\to D(x)$,

  4. (iv)

$\forall x,y,z.C(x)\land r(x,y)\land D(y)\land r(x,z)\land D(z)\to y=z$,

  5. (v)

$\forall x.C(x)\to x=a$,

  6. (vi)

$\forall x,y.r(x,y)\to s(x,y)$, or

  7. (vii)

$C(a)$,

respectively. Additionally, there is a bijective and irreflexive function
$\cdot^{-}$ on the set of role names such that $r^{--}=r$ and $\forall
x,y.r(x,y)\leftrightarrow(r^{-})(y,x)$ is required to hold in all models of a
TBox, for all role names $r$ ($r^{-}$ is called the _inverse_ of $r$).

Following Ortiz, Rudolph, and Šimkus (2010), we will use _Datalog S,¬_ rules
to encode reasoning in Horn-$\mathcal{ALCHOIQ}$. DatalogS,¬ extends Datalog¬
rules by introducing fixed _set sorts_ $2^{C}$, where $C$ is a set of
constants. Set terms of sort $2^{C}$ are built inductively from the
constructors $\\{c_{1},\dots,c_{n}\\}$ and $t_{1}\cup t_{2}$, where
$c_{1},\dots,c_{n}\in C$ and $t_{1},t_{2}$ are set terms of this sort. Every
predicate has an associated _sort function_ that assigns to each position a
unique sort, i.e. either the (normal) _element sort_ , or one of the fixed set
sorts. This means that the positions of this predicates always accept only
terms of the associated sort. The semantics of the resulting (stratified)
DatalogS,¬ rules is intuitive (Ortiz, Rudolph, and Šimkus 2010).

To make it easier to compare with the existing constructions (Ortiz, Rudolph,
and Šimkus 2010; Carral, Dragoste, and Krötzsch 2018), in the following we
write DatalogS,¬ rules with $\to$ instead of $\leftarrow$. We also use rules
with conjunctions of atoms in the head (instead of only one atom).

### Encoding Instance Queries

In the following, let $\mathcal{T}$ be a Horn-$\mathcal{ALCHOIQ}$ TBox in
normal form, and $\mathbf{C}$/$\mathbf{R}$/$\mathbf{I}$ denote the sets of
concept names/role names/individual names in $\mathcal{T}$. In addition to the
individuals in $\mathbf{I}$, the construction by Carral, Dragoste, and
Krötzsch (2018) uses artificial individuals of the form $t_{X}$, where $X$ is
a set of concept names, and new predicates $R$ that represent a set of role
names that have to be satisfied at the same time. We represent such $R$ and
$X$ using sets of the sorts $2^{{\mathbf{R}}}$ and
$2^{{\mathbf{C}}\cup{\mathbf{I}}}$, respectively. The latter includes named
individuals since we want to treat named and anonymous individuals using the
same predicates. However, named individuals $a$ will only appear as singleton
sets $\\{a\\}$. Formally, we are not allowed to treat individuals from the
ABox in this way, because then the set sorts (which need to be fixed) would
depend on the ABox. We nevertheless do this in the following and at the end of
this section describe how to translate these DatalogS,¬ rules into Datalog¬
rules that are ABox-independent.

Instead of an atom $C(x)$ (Carral, Dragoste, and Krötzsch 2018), we now use
atoms of the form ${\mathsf{concept}}(C,X)$, where $C\in{\mathbf{C}}$ is
treated as a new constant and $X$ is a set as described above (i.e. either a
set of concept names or a singleton set containing an individual name).
Likewise, role atoms $r(x,y)$ and $R(x,y)$ are transformed into
${\mathsf{role}}(r,X,Y)$ and ${\mathsf{roles}}(R,X,Y)$, respectively.
Additionally, we distinguish sets $X\subseteq{\mathbf{C}}$ from sets $\\{a\\}$
with $a\in{\mathbf{I}}$ by the predicate $\mathsf{anon}$, which is populated
by the following rules, for all $C\in{\mathbf{C}}$:

$\displaystyle\phantom{{}\to{}}{\mathsf{anon}}(\\{C\\})$ (1)
$\displaystyle{\mathsf{anon}}(X)$
$\displaystyle\to{\mathsf{anon}}(X\cup\\{C\\})$ (2)

We also compute the set of inverse roles of a set $R$, for all
$r\in{\mathbf{R}}$ (Ortiz, Rudolph, and Šimkus 2010):

$\displaystyle\phantom{{}\to{}}{\mathsf{inv}}(\\{r\\},\\{r^{-}\\})$ (3)
$\displaystyle{\mathsf{inv}}(R,R^{-})$
$\displaystyle\to{\mathsf{inv}}(R\cup\\{r\\},R^{-}\cup\\{r^{-}\\})$ (4)

Additionally, the original rewriting uses atoms of the form ${\mathsf{n}}(x)$
and $x\approx y$, which we simply adapt to ${\mathsf{n}}(X)$ and $X\approx Y$,
where $X,Y$ are as described above. We also add a predicate $\mathsf{ind}$,
which identifies all individual names from the ABox in order to identify query
answers in the end. This predicate represents a subset of the predicate
$\mathsf{n}$, which will also contain anonymous individuals $X$ that are
inferred to represent a unique element in every interpretation.

The original Datalog rewriting starts with several auxiliary rules, which we
translate below into their modified DatalogS,¬ form, for all
$C\in{\mathbf{C}}$ and $r\in{\mathbf{R}}$ (Carral, Dragoste, and Krötzsch
2018, Figure 2):

$\displaystyle{\mathsf{concept}}(C,X)$
$\displaystyle\to{\mathsf{concept}}(\top,X)$ (5)
$\displaystyle{\mathsf{role}}(r,X,Y)$
$\displaystyle\to{\mathsf{concept}}(\top,X)\land{\mathsf{concept}}(\top,Y)$
(6)
$\displaystyle{\mathsf{roles}}(R,X,Y)\land{\mathsf{n}}(Y)\land{\mathsf{inv}}(R,R^{-})$
$\displaystyle\to{\mathsf{roles}}(R^{-},Y,X)$ (7)
$\displaystyle{\mathsf{roles}}(R,X,Y)\land r\in R$
$\displaystyle\to{\mathsf{role}}(r,X,Y)$ (8) $\displaystyle C(x)$
$\displaystyle\to{\mathsf{concept}}(C,\\{x\\})\land{\mathsf{ind}}(\\{x\\})$
(9) $\displaystyle r(x,y)$
$\displaystyle\to{\mathsf{role}}(r,\\{x\\},\\{y\\})\land{\mathsf{ind}}(\\{x\\})\land{\mathsf{ind}}(\\{y\\})$
(10) $\displaystyle{\mathsf{ind}}(X)$ $\displaystyle\to{\mathsf{n}}(X)$ (11)
$\displaystyle X\approx Y$ $\displaystyle\to Y\approx X$ (12) $\displaystyle
X\approx Y\land Y\approx Z$ $\displaystyle\to X\approx Z$ (13)
$\displaystyle{\mathsf{concept}}(C,X)\land X\approx Y$
$\displaystyle\to{\mathsf{concept}}(C,Y)$ (14)
$\displaystyle{\mathsf{n}}(X)\land X\approx Y$
$\displaystyle\to{\mathsf{n}}(Y)$ (15)
$\displaystyle{\mathsf{roles}}(R,X,Y)\land X\approx Z$
$\displaystyle\to{\mathsf{roles}}(R,Z,Y)$ (16)
$\displaystyle{\mathsf{roles}}(R,X,Y)\land Y\approx Z$
$\displaystyle\to{\mathsf{roles}}(R,X,Z)$ (17)

Rules (9) and (10) were further modified from their originals to convert the
ABox predicates into our DatalogS,¬ syntax in an ABox-independent way. In a
slight abuse of notation, on the left-hand side of Rule (9), $C$ is treated as
a concept name, and on the right-hand side $C$ is treated as a constant
(similarly for Rule (10)).

The axioms of the TBox $\mathcal{T}$ are translated into the following
DatalogS,¬ rules (Carral, Dragoste, and Krötzsch 2018, Figures 3 and 4). For
every axiom of the form (i):

$\displaystyle{\mathsf{concept}}(C_{1},X)\land\dots\land{\mathsf{concept}}(C_{n},X)$
$\displaystyle\to{\mathsf{concept}}(D,X)$ (18) For axioms of the form (ii):
$\displaystyle{\mathsf{concept}}(C,X)$
$\displaystyle\to{\mathsf{role}}(r,X,\\{D\\})$ (19) For axiom type (iii):
$\displaystyle{\mathsf{role}}(r,X,Y)\land{\mathsf{concept}}(C,Y)$
$\displaystyle\to{\mathsf{concept}}(D,X)$ (20)
$\displaystyle{\mathsf{concept}}(C,X)\land{\mathsf{roles}}(R^{-},X,Y)\land
r\in R\land{\mathsf{inv}}(R,R^{-})\land{\mathsf{anon}}(Y)$
$\displaystyle\to{\mathsf{roles}}(R^{-},X,Y\cup\\{D\\})$ (21) Axiom type (iv)
requires more complex rules:
$\displaystyle{\mathsf{concept}}(D,Y)\land{\mathsf{role}}(r^{-},Y,X)\land{}$
$\displaystyle{\mathsf{concept}}(C,X)\land{\mathsf{role}}(r,X,Z)\land{\mathsf{concept}}(D,Z)\land{\mathsf{n}}(Z)$
$\displaystyle\to Y\approx Z$ (22) $\displaystyle{\mathsf{concept}}(C,X)\land
r\in R\land{\mathsf{roles}}(R,X,Y)\land{\mathsf{concept}}(D,Y)\land{}$
$\displaystyle{\mathsf{anon}}(Y)\land r\in
S\land{\mathsf{roles}}(S,X,Z)\land{\mathsf{concept}}(D,Z)\land{\mathsf{anon}}(Z)$
$\displaystyle\to{\mathsf{roles}}(R\cup S,X,Y\cup Z)$ (23)
$\displaystyle{\mathsf{concept}}(C,X)\land r\in
R\land{\mathsf{inv}}(R,R^{-})\land{\mathsf{concept}}(D,Y)\land{\mathsf{roles}}(R^{-},Y,X)\land{}$
$\displaystyle r\in S\land{\mathsf{inv}}(S,S^{-})\land{\mathsf{anon}}(Z)\land
E\in Z\land{\mathsf{roles}}(S,X,Z)\land{\mathsf{concept}}(D,Z)$
$\displaystyle\to{\mathsf{concept}}(E,Y)\land{}$
$\displaystyle\phantom{{}\to{}}{\mathsf{roles}}(R^{-}\cup S^{-},Y,X)$ (24)
$\displaystyle{\mathsf{concept}}(D,Y)\land{\mathsf{role}}(r^{-},Y,X)\land{\mathsf{concept}}(C,X)\land{\mathsf{n}}(X)$
$\displaystyle\to{\mathsf{n}}(Y)$ (25) In addition, we need the following rule
that completes the translation of axioms of types (ii)–(iv) by adding the
newly created anonymous individuals to the required concepts:
$\displaystyle{\mathsf{role}}(r,X,Y)\land C\in Y$
$\displaystyle\to{\mathsf{concept}}(C,Y)$ (26) For axiom type (v):
$\displaystyle{\mathsf{concept}}(C,X)$ $\displaystyle\to\\{a\\}\approx
X\land{\mathsf{n}}(\\{a\\})$ (27) For axiom type (vi), we use the predicate
$\mathsf{sup}$ that connects each role name to the set of all its super-roles
(Rule 29 is instantiated for every $s\sqsubseteq t\in{\mathcal{T}}$ or
$s^{-}\sqsubseteq t^{-}\in{\mathcal{T}}$):
$\displaystyle\to{\mathsf{sup}}(r,\\{r\\})$ (28)
$\displaystyle{\mathsf{sup}}(r,S)\land s\in S$
$\displaystyle\to{\mathsf{sup}}(r,S\cup\\{t\\})$ (29)
$\displaystyle{\mathsf{role}}(r,X,Y)\land{\mathsf{sup}}(r,S)$
$\displaystyle\to{\mathsf{roles}}(S,X,Y)$ (30)
$\displaystyle{\mathsf{role}}(r^{-},X,Y)\land{\mathsf{sup}}(r,S)\land{\mathsf{inv}}(S,S^{-})$
$\displaystyle\to{\mathsf{roles}}(S^{-},X,Y)$ (31) Finally, axiom type (vii)
can be handled like a concept assertion:
$\displaystyle\to{\mathsf{concept}}(C,\\{a\\})\land{\mathsf{n}}(\\{a\\})$ (32)

So far, the rules did not use negation and can be seen as the first stratum of
the final rule set. This part is already a rewriting of any instance query
over the TBox signature, i.e. ${\mathsf{concept}}(C,\\{a\\})$ is contained in
the least Herbrand model of these rules and an ABox iff $C(a)$ is entailed by
the original TBox over the ABox (Carral, Dragoste, and Krötzsch 2018, Lemma
4). To be able to answer arbitrary UCQs, we also need to encode the so-called
_filtration phase_ (Carral, Dragoste, and Krötzsch 2018).

### Building a Canonical Model

The next stratum encodes Definition 7 from Carral, Dragoste, and Krötzsch
(2018) by using negated atoms over the predicate $\mathsf{n}$. The goal of
this part is to derive a dependency relation
${\mathsf{role}}_{\triangleright}(r,X,Y)$ that encodes the order in which
individuals are created during the construction of a model of the ontology.
Extended individuals of the form $t_{R,X}^{i}$ are used in this relation,
where $R\subseteq{\mathbf{R}}$, $X\subseteq{\mathbf{C}}$ and $i\in\\{0,1,2\\}$
(Carral, Dragoste, and Krötzsch 2018). Therefore, the sets $X,Y$ in
${\mathsf{role}}_{\triangleright}(r,X,Y)$ are now considered to be subsets of
${\mathbf{R}}\cup{\mathbf{C}}\cup{\mathbf{I}}\cup\\{0,1,2\\}$, where again
individuals can only occur in singleton sets $\\{a\\}$, and at most one index
$0,1,2$ can be present in any given set. In addition to
${\mathsf{role}}_{\triangleright}$, the following rules also compute
extensions ${\mathsf{role}}^{\prime}$ and ${\mathsf{concept}}^{\prime}$ of
${\mathsf{role}}$ and ${\mathsf{concept}}$, respectively, to the new
individuals. Together, these three predicates describe a kind of _canonical
model_ (called ${\mathcal{C}}_{\mathcal{O}}$) over which UCQs will be
answered.

As a prerequisite, we need to introduce an intermediate stratum to define a
total order $\preceq$ on sets of the form $R\cup X$. For this purpose, we
consider an enumeration $r_{1},\dots,r_{n},C_{n+1},\dots,C_{n+m}$ of all role
and concept names and use the following rules to define the lexicographic
order $\preceq$ based on the auxiliary relations $\prec_{i}$ and
$\approx_{i}$, $i\in\\{1,\dots,n+m\\}$ (all using infix notation):

$\displaystyle\phantom{{}\to{}}\emptyset\approx_{1}\emptyset$ (33)
$\displaystyle\phantom{{}\to{}}\emptyset\prec_{1}\\{r_{1}\\}$ (34)
$\displaystyle\phantom{{}\to{}}\\{r_{1}\\}\approx_{1}\\{r_{1}\\}$ (35)
$\displaystyle X\prec_{1}Y$ $\displaystyle\to X\prec_{2}Y$ (36) $\displaystyle
X\approx_{1}Y$ $\displaystyle\to X\approx_{2}Y$ (37) $\displaystyle
X\approx_{1}Y$ $\displaystyle\to X\prec_{2}Y\cup\\{r_{2}\\}$ (38)
$\displaystyle X\approx_{1}Y$ $\displaystyle\to
X\cup\\{r_{2}\\}\approx_{2}Y\cup\\{r_{2}\\}$ (39) $\displaystyle\ \ \vdots$
$\displaystyle X\approx_{n+m}Y$ $\displaystyle\to X\preceq Y$ (40)
$\displaystyle X\prec_{n+m}Y$ $\displaystyle\to X\preceq Y$ (41)

The following rules, which use the negations of $\preceq$ and $\mathsf{n}$
from the previous strata, correspond to Definition 7 from Carral, Dragoste,
and Krötzsch (2018), where $j=(i+1)\mod 3$:

$\displaystyle{\mathsf{n}}(X)\land{\mathsf{role}}(r,X,Y)\land{\mathsf{n}}(Y)$
$\displaystyle\to{\mathsf{role}}_{\triangleright}(r,X,Y)\land{\mathsf{role}}_{\triangleright}(r^{-},Y,X)$
(42)
$\displaystyle{\mathsf{n}}(X)\land{\mathsf{roles}}(R,X,Y)\land{\mathsf{anon}}(Y)\land\lnot{\mathsf{n}}(Y)\land
r\in R$ $\displaystyle\to{\mathsf{role}}_{\triangleright}(r,X,R\cup
Y\cup\\{0\\})$ (43) $\displaystyle{\mathsf{role}}_{\triangleright}(r,X,R\cup
Y\cup\\{i\\})\land{\mathsf{roles}}(S,Y,Z)\land{\mathsf{anon}}(Z)\land\lnot{\mathsf{n}}(Z)\land{}$
$\displaystyle s\in S\land R\cup Y\preceq S\cup Z$
$\displaystyle\to{\mathsf{role}}_{\triangleright}(s,R\cup Y\cup\\{i\\},S\cup
Z\cup\\{j\\})$ (44) $\displaystyle{\mathsf{role}}_{\triangleright}(r,X,R\cup
Y\cup\\{i\\})\land{\mathsf{roles}}(S,Y,Z)\land{\mathsf{anon}}(Z)\land\lnot{\mathsf{n}}(Z)\land{}$
$\displaystyle s\in S\land R\cup Y\not\preceq S\cup Z$
$\displaystyle\to{\mathsf{role}}_{\triangleright}(s,R\cup Y\cup\\{i\\},S\cup
Z\cup\\{i\\})$ (45) $\displaystyle{\mathsf{role}}_{\triangleright}(s,X,R\cup
Y\cup\\{i\\})\land{\mathsf{role}}(r,Y,Z)\land{\mathsf{n}}(Z)$
$\displaystyle\to{\mathsf{role}}_{\triangleright}(r,R\cup
Y\cup\\{i\\},Z)\land{}$ (46)
$\displaystyle\phantom{{}\to{}}{\mathsf{role}}_{\triangleright}(r^{-},Z,R\cup
Y\cup\\{i\\})$ (47)
$\displaystyle{\mathsf{role}}_{\triangleright}(s,X,Y)\land{\mathsf{concept}}(C,Y)$
$\displaystyle\to{\mathsf{concept}}^{\prime}(C,Y)$ (48)
$\displaystyle{\mathsf{role}}_{\triangleright}(s,X,R\cup
Y\cup\\{i\\})\land{\mathsf{concept}}(C,Y)$
$\displaystyle\to{\mathsf{concept}}^{\prime}(C,R\cup Y\cup\\{i\\})$ (49)
$\displaystyle{\mathsf{role}}_{\triangleright}(r,X,Y)$
$\displaystyle\to{\mathsf{role}}^{\prime}(r,X,Y)\land{\mathsf{role}}^{\prime}(r^{-},Y,X)$
(50)

The least Herbrand model of these rules (restricted to
${\mathsf{role}}_{\triangleright}$, ${\mathsf{concept}}^{\prime}$, and
${\mathsf{role}}^{\prime}$) corresponds to the set
${\mathcal{C}}_{\mathcal{O}}$ (Carral, Dragoste, and Krötzsch 2018).
Conditions of the type “$t_{R,Y}^{i}$ is in ${\mathcal{C}}_{\mathcal{O}}$” are
translated into body atoms like ${\mathsf{role}}_{\triangleright}(r,X,R\cup
Y\cup\\{i\\})$ since these new individuals are only introduced into
${\mathcal{C}}_{\mathcal{O}}$ inside of
${\mathsf{role}}_{\triangleright}$-facts.

### Encoding the Filtration

Finally, we encode Definition 8 from Carral, Dragoste, and Krötzsch (2018),
which constructs a family of graphs that use the variables of a given CQ as
vertices, and their edges encode possible matches of the CQ into
${\mathcal{C}}_{\mathcal{O}}$. Some of these matches have to be filtered out
since they lead to spurious answers. We assume that the input CQ $q$ is of the
form $\exists v_{1},\dots,v_{\ell}.\phi(v_{1},\dots,v_{k})$, i.e.
$v_{\ell+1},\dots,v_{k}$ are the free variables (UCQs can be treated by
encoding each component CQ individually and then merging the results in a
single predicate). By $\phi(V_{1},\dots,V_{k})$ we denote the result of
replacing each concept atom $C(v_{i})$ in $\phi$ by
${\mathsf{concept}}^{\prime}(C,V_{i})$ and similarly $r(v_{i},v_{j})$ by
${\mathsf{role}}^{\prime}(r,V_{i},V_{j})$, where each $V_{i}$ is viewed as a
set variable over ${\mathbf{R}}\cup{\mathbf{C}}\cup\\{i\\}$ and denotes a
possible mapping of $v_{i}$ into ${\mathcal{C}}_{\mathcal{O}}$. We use the
indices $1,\dots,k$ to refer to the vertices in the graphs that are
constructed, and atoms of the form ${\mathsf{edge}}(i,j,V_{1},\dots,V_{k})$ to
denote an edge from $i$ to $j$ (which depends on a specific instantiation of
all variables by individuals in ${\mathcal{C}}_{\mathcal{O}}$).

The following are the rules corresponding to the first part of Definition 8
from Carral, Dragoste, and Krötzsch (2018), for all role atoms
$r(v_{i},v_{j})$ in $\phi$:

$\displaystyle\phi(V_{1},\dots,V_{k})\land{\mathsf{role}}_{\triangleright}(r,V_{i},V_{j})\land\lnot{\mathsf{role}}_{\triangleright}(r^{-},V_{j},V_{i})$
$\displaystyle\to{\mathsf{edge}}(i,j,V_{1},\dots,V_{k})$ (51)
$\displaystyle\phi(V_{1},\dots,V_{k})\land{\mathsf{role}}_{\triangleright}(r^{-},V_{j},V_{i})\land\lnot{\mathsf{role}}_{\triangleright}(r,V_{i},V_{j})$
$\displaystyle\to{\mathsf{edge}}(j,i,V_{1},\dots,V_{k})$ (52) Now, for all
$i,j\in\\{1,\dots,k\\}$, we apply the following rules to collapse this graph
according to Definition 8 from Carral, Dragoste, and Krötzsch (2018):
$\displaystyle{\mathsf{edge}}(i,j,V_{1},\dots,V_{k})\land{\mathsf{edge}}(m,j,V_{1},\dots,V_{k})$
$\displaystyle\to{\mathsf{equal}}(i,m,V_{1},\dots,V_{k})$ (53)
$\displaystyle{\mathsf{edge}}(i,j,V_{1},\dots,V_{k})\land{\mathsf{edge}}(m,n,V_{1},\dots,V_{k})\land{\mathsf{equal}}(j,n,V_{1},\dots,V_{k})$
$\displaystyle\to{\mathsf{equal}}(i,m,V_{1},\dots,V_{k})$ (54) We now need to
check whether the resulting graph is a rooted directed forest, i.e. contains
no cycles and no “diamonds” that reconnect different branches:
$\displaystyle{\mathsf{edge}}(i,j,V_{1},\dots,V_{k})$
$\displaystyle\to{\mathsf{reach}}(i,j,V_{1},\dots,V_{k})$ (55)
$\displaystyle{\mathsf{reach}}(i,j,V_{1},\dots,V_{k})\land{\mathsf{equal}}(j,m,V_{1},\dots,V_{k})$
$\displaystyle\to{\mathsf{reach}}(i,m,V_{1},\dots,V_{k})$ (56)
$\displaystyle{\mathsf{reach}}(i,j,V_{1},\dots,V_{k})\land{\mathsf{equal}}(i,m,V_{1},\dots,V_{k})$
$\displaystyle\to{\mathsf{reach}}(m,j,V_{1},\dots,V_{k})$ (57)
$\displaystyle{\mathsf{reach}}(i,j,V_{1},\dots,V_{k})\land{\mathsf{edge}}(j,m,V_{1},\dots,V_{k})$
$\displaystyle\to{\mathsf{reach}}(i,m,V_{1},\dots,V_{k})$ (58)
$\displaystyle{\mathsf{reach}}(i,i,V_{1},\dots,V_{k})$
$\displaystyle\to{\mathsf{bad}}(V_{1},\dots,V_{k})$ (59)
$\displaystyle{\mathsf{edge}}(i,j,V_{1},\dots,V_{k})\land{\mathsf{edge}}(i,m,V_{1},\dots,V_{k})\land\lnot{\mathsf{equal}}(j,m,V_{1},\dots,V_{k})\land{}$
$\displaystyle{\mathsf{reach}}(j,n,V_{1},\dots,V_{k})\land{\mathsf{reach}}(m,n,V_{1},\dots,V_{k})$
$\displaystyle\to{\mathsf{bad}}(V_{1},\dots,V_{k})$ (60) Finally, we can use
the predicate $\mathsf{bad}$ to filter out spurious matches and return the
actual answers to $q$ in the predicate $P_{q}$:
$\displaystyle\phi(V_{1},\dots,V_{k})\land\lnot{\mathsf{bad}}(V_{1},\dots,V_{k})$
$\displaystyle\to P_{q}^{\prime}(V_{\ell+1},\dots,V_{k})$ (61) $\displaystyle
P_{q}^{\prime}(V_{\ell+1},\dots,V_{k})\land{\mathsf{ind}}(V_{\ell+1})\land\dots\land{\mathsf{ind}}(V_{k})\land
a_{\ell+1}\in V_{\ell+1}\land\dots\land a_{k}\in V_{k}$ $\displaystyle\to
P_{q}(a_{\ell+1},\dots,a_{k})$ (62)

### From DatalogS,¬ to Datalog¬

To simulate set terms in plain Datalog¬, we adapt an existing construction,
which did not deal with negation or ABox-independent rule sets (Ortiz,
Rudolph, and Šimkus 2010). First, each set union $t_{1}\cup t_{2}$ over the
domain $S$ is replaced with a fresh variable $X$ and the ternary atom
${\mathsf{U}}_{S}(t_{1},t_{2},X)$ is added to the body of the rule in which
this term occurs. New rules are added to simulate the set union with this
predicate (see below). Then, sets $X\subseteq S$ are represented as bit
vectors of length $|S|$ and set variables as vectors of variables, and all
atoms are replaced accordingly. This gets rid of all set expressions while
increasing the arity of the predicates polynomially.

The main problem we face here is that we used singleton sets $\\{a\\}$ to
refer to individual names $a$ from the ABox, which means that the set sort
$2^{{\mathbf{C}}\cup{\mathbf{I}}}$ was treated as if it contained all these
individual names, although our translation cannot depend on the ABox (see
Definition 1). To avoid this issue, we modify the bit vector encoding above to
directly represent constants by themselves. For this, recall that individual
names $a$ can only occur in singleton sets $\\{a\\}$, because sets $X$ are
only extended if they belong to $\mathsf{anon}$ (see, e.g. Rules (21), (23),
or (43)). Thus, we can represent each instantiated set $X$, which is either of
the form $\\{a\\}$ or a subset of $\mathbf{C}$, as a vector $(a,0,\dots,0)$ or
$(0,b_{1},\dots,b_{m})$, respectively, where $m=|{\mathbf{C}}|$ and $b_{i}=1$
iff the $i$-th concept name of $\mathbf{C}$ is in $X$ (according to some fixed
enumeration of $\mathbf{C}$). The new constants $0$ and $1$ are used to
represent bit values. Correspondingly, set variables $X$ are split into
vectors $(x_{0},x_{1},\dots,x_{m})$, where $x_{0}$ holds the individual name
(if any) and $x_{1},\dots,x_{m}$ represent a subset of $\mathbf{C}$. The
encoding works similarly for sets of the sorts $2^{\mathbf{R}}$,
$2^{{\mathbf{R}}\cup{\mathbf{C}}}$, and
$2^{{\mathbf{R}}\cup{\mathbf{C}}\cup{\mathbf{I}}\cup\\{0,1,2\\}}$ that are
employed in the rewriting above. For example, the Datalog¬ versions of Rules
(9) and (19) are

$\displaystyle C(x)$
$\displaystyle\to{\mathsf{concept}}(C,x,0,\dots,0)\land{\mathsf{ind}}(x,0,\dots,0),\text{
and}$ (63) $\displaystyle{\mathsf{concept}}(C,x_{0},\dots,x_{m})$
$\displaystyle\to{\mathsf{role}}(r,x_{0},\dots,x_{m},0,b_{1},\dots,b_{m}),$
(64)

respectively, where $b_{i}=1$ iff $D$ is the $i$-th concept name in
$\mathbf{C}$.

Apart from the new predicates like
${\mathsf{U}}_{{\mathbf{C}}\cup{\mathbf{I}}}$, this encoding clearly preserves
the stratification of the original rule set. The following additional rules
are used to define ${\mathsf{U}}_{{\mathbf{C}}\cup{\mathbf{I}}}$, and
similarly for the other set sorts:

$\displaystyle\to{\mathsf{max}}(0,0,0)$ (65)
$\displaystyle\to{\mathsf{max}}(1,0,1)$ (66)
$\displaystyle\to{\mathsf{max}}(0,1,1)$ (67)
$\displaystyle\to{\mathsf{max}}(1,1,1)$ (68)
$\displaystyle{\mathsf{max}}(x_{1},y_{1},z_{1})\land\dots\land{\mathsf{max}}(x_{m},y_{m},z_{m})$
$\displaystyle\to{\mathsf{U}}_{{\mathbf{C}}\cup{\mathbf{I}}}(0,x_{1},\dots,x_{m},0,y_{1},\dots,y_{m},0,z_{1},\dots,z_{m}),$
(69)

This suffices to define the set union since we never need to compute unions
involving singleton sets $\\{a\\}$ with $a\in{\mathbf{I}}$. These additional
rules can be included in the first stratum since $\mathsf{max}$ and
${\mathsf{U}}_{S}$ do not occur in any other rule heads.

This finishes the presentation of the Datalog¬ rewriting for any UCQ over a
Horn-$\mathcal{ALCHOIQ}$ TBox. Its correctness follows mainly from an existing
result (Carral, Dragoste, and Krötzsch 2018, Theorem 3) since we only
translated the relevant definitions into DatalogS,¬ rules. It can also be
verified that the resulting set of Datalog¬ rules is of polynomial size.

##  Appendix B Proof of Theorem 5

We show how to construct the eKAB task $(\Delta_{n},{\mathcal{O}},I_{w},g)$
such that $M$ accepts a word $w$ of length $n$ iff there is a plan of length
$1$. The construction is based on the 2ExpTime-hardness proof for
Horn-$\mathcal{SROIQ}$ (Ortiz, Rudolph, and Šimkus 2010) and uses only a
single action with precondition $[\exists x.B(x)]$ and unconditional effect
$g$. We do not repeat all details of the original construction here, but only
adapt the relevant parts. The proof encodes the Turing machine $M$ and an
input word $w$ into a TBox $\mathcal{T}$ using the two objects $o$ and $e$
such that $M$ accepts $w$ iff at least one unary predicate $H_{q_{f}}$
(representing a final state of the TM) is empty in every model of
$\mathcal{T}$. The original proof then goes on to add axioms
$H_{q_{f}}\sqsubseteq\bot$ to force $\mathcal{T}$ to become unsatisfiable in
such a case. Since we require the initial state to be consistent with the
TBox, we instead use the axioms $H_{q_{f}}\sqsubseteq B$, which allows us to
query for $\exists x.B(x)$ instead of checking unsatisfiability.

We further adapt the original reduction by extracting from $\mathcal{T}$ the
description of the input word $w$ into a state $I_{w}$. For $w=w_{0}\dots
w_{n-1}$, $\mathcal{T}$ contains the following axioms to encode the input tape
(notation is slightly adjusted to avoid clashes):

$\displaystyle\\{o\\}$ $\displaystyle\sqsubseteq I_{1}\sqcap H_{q_{0}}$ (70)
$\displaystyle I_{j}$ $\displaystyle\sqsubseteq A_{w_{j}}\sqcap\forall
h.I_{j+1}$ $\displaystyle(0\leq j<n)$ (71) $\displaystyle I_{j}$
$\displaystyle\sqsubseteq\overline{H_{r}}$ $\displaystyle(1\leq j<n)$ (72)
$\displaystyle I_{n}$ $\displaystyle\sqsubseteq A_{\Box}$ (73) $\displaystyle
I_{n}$ $\displaystyle\sqsubseteq\forall h.I_{n}$ (74)

The object $o$ indicates the starting point of the tape, and the unary
predicates $I_{j}$ identify the first $n$ cells, which are connected via the
binary predicate $h$. The predicates $A_{w_{j}}$ indicate the presence of the
input symbols in these cells. The predicates $H_{q_{0}}$ and
$\overline{H_{r}}$ indicate the presence and absence of the head,
respectively. Finally, all cells to the right of the input word are labeled
with a blank symbol $\Box$ by using the auxiliary predicate $I_{n}$. We leave
the axioms (72)–(74) in the TBox, but replace (70)–(71) by the following
axioms (75)–(76) and assertions for $I_{w}$ (77)–(78):

$\displaystyle S_{j,a}$ $\displaystyle\sqsubseteq\forall h^{j}.I_{j}\sqcap
A_{a}$ $\displaystyle(0\leq j<n,\ a\in\Sigma)$ (75) $\displaystyle I_{n-1}$
$\displaystyle\sqsubseteq\forall h_{n}.I_{n}$ (76) $\displaystyle
H_{q_{0}}(o)$ (77) $\displaystyle S_{j,w_{j}}(o)$ $\displaystyle(0\leq j<n)$
(78)

Here, $\forall h^{j}$ stands for $j$ nested restrictions of the form $\forall
h$, and $S_{j,a}$ indicates the presence of the symbol $a$ of the TM alphabet
$\Sigma$ at cell $j$. In this way, the final TBox ${\mathcal{T}}_{n}$ only
depends on the length $n$ of the input word $w$, but not on $w$ itself. The
final domain description is
$\Delta_{n}=({\mathcal{P}}_{n},{\mathcal{A}}_{n},{\mathcal{T}}_{n})$, where
${\mathcal{P}}_{n}$ contains all symbols from ${\mathcal{T}}_{n}$ as well as
$g$, and ${\mathcal{A}}_{n}$ consists of the single action described above.

##  Appendix C Proof of Theorem 6

The proof follows the same arguments as for Theorem 5, the only difference
being how the domain description $\Delta_{n}$ and state $I_{w}$ are obtained.
For CQ entailment in $\mathcal{ALCI}$, we adapt a reduction from a (universal)
AExpSpace Turing machine (Lutz 2007). The single action we use in the
reduction will have a precondition $[q_{w}]$, where $q_{w}$ is the CQ from
that reduction, which, despite its name, does not depend on the input word
$w=w_{0}\dots w_{n-1}$, but only on the length $n$. Again, the only adaption
we have to do is to extract the part of the TBox encoding the input word into
a state $I_{w}$. Consider the relevant axioms (again with slightly adapted
notation), where $0\leq j<n$ (Lutz 2007):

$\displaystyle\big{(}R\sqcap I\big{)}(o)$ (79) $\displaystyle I$
$\displaystyle\sqsubseteq\forall
s^{n+2}.\big{(}(G_{h}\sqcap({\mathsf{pos}}=j))\to w_{j}\big{)}$ (80)
$\displaystyle I$ $\displaystyle\sqsubseteq\forall
s^{n+2}.\big{(}(G_{h}\sqcap({\mathsf{pos}}=0))\to q_{0}\big{)}$ (81)
$\displaystyle I$ $\displaystyle\sqsubseteq\forall
s^{n+2}.\big{(}(G_{h}\sqcap({\mathsf{pos}}\geq n))\to b\big{)}$ (82)

Here, $R\sqcap I$ describes the starting point of the initial configuration
and its $s^{n+2}$-successors marked with $G_{h}$ identify the exponentially
many tape cells. The counter $\mathsf{pos}$ identifies particular cells,
$w_{j}$ describes the tape content, $q_{0}$ the initial state, and $b$ the
blank symbol. We use a similar trick as before to split (80) into ABox facts
and TBox axioms that do not depend on the input word $w$, but only on its
length (for all $0\leq j<n$, $a\in\Sigma$):

$\displaystyle S_{j,a}$ $\displaystyle\sqsubseteq\forall
s^{n+2}.\big{(}(G_{h}\sqcap({\mathsf{pos}}=j))\to a\big{)}$ (83)
$\displaystyle S_{j,w_{j}}(o)$ (84)

The state $I_{w}$ now consists of all facts (84) as well as (79), and all
other axioms are part of ${\mathcal{T}}_{n}$. The remaining arguments are the
same as in the proof of Theorem 5.

The reduction for CQ entailment over $\mathcal{SH}$ TBoxes (Eiter et al.
2009b) is very similar to the previous case, except that the predicates $R$
and $G_{h}$ are not used, $s^{n+2}$ is replaced by $r^{n+1}$, $w_{j}$ is
replaced by $\forall r.(E_{h}\to w_{j})$, and similarly for $q_{0}$ and $b$
(many other details not relevant here are different as well). Hence, we can
use very similar adaptations.

##  Appendix D Benchmark Description

Our collection of benchmarks consists of a total of $235$ instances adapted
from the publicly available DL-Lite eKAB benchmark collection (Borgwardt et
al. 2021) as well as newly developed high expressivity domains. The benchmarks
and the compiler are available in the supplementary material. Each problem
instance has two representations: the Horn-$\mathcal{SHIQ}$ eKAB task encoding
with an ontology written in Turtle555https://www.w3.org/TR/turtle/ and its
compilation into PDDL.

#### Adapted DL-Lite eKAB benchmarks:

We translated the original benchmarks into equivalent representations in our
Horn-$\mathcal{SHIQ}$ eKAB task encoding. Detailed descriptions of these
domains are available online. In short,

  * •

in Robot (Calvanese et al. 2016), a robot is positioned on a grid without
knowing its position and the goal is to reach a target cell. The ontology
describes relations between rows and columns.

  * •

The goal of TaskAssign, inspired by (Calvanese et al. 2016), is to hire two
electronic engineers for a company, while the ontology describes relations
between different job positions.

  * •

The Elevator and Cats benchmarks are inspired by standard planning benchmarks.
In the Cats domain, there is a set of packages that contain either cats or
bombs and the task is to disarm all bombs. An elevator in the Elevator
benchmark can move up and down between floors to serve passengers according to
their origins and destinations.

  * •

Both the VTA and TPSA benchmarks are adaptations from older work on semantic
web-service composition (Hoffmann et al. 2008). VTA-Roles is a more complex
variant of VTA.

#### High Expressivity Domains:

  * •

Drones models a complex 2D drone navigation problem, in which drones need to
be moved while avoiding certain situations; the latter is given by ontology
reasoning, involving Horn concept inclusions with qualified existential
restrictions occurring negatively and symmetric roles. Grid cells are occupied
with different objects like Humans or Trees or weather conditions like
LowVisibility or Rain. There is a set of Drones randomly placed on the board.
Depending on the distances to other objects, a Drone can enter a critical
state (defined by the ontology). The goal is to move the drones such that no
two drones in a critical state are next to each other. In the benchmark,
instances vary in the board size and the number of drones. We have chosen the
instances such that some of them remain hard for the planner to solve. The
compilation itself is always very fast.

  * •

Queens generalizes the eight queens puzzle from chess to variable numbers of
board sizes, $n\in\\{5,\dots,10\\}$, and queens, $m\in\\{n-4,\dots,n\\}$. In
the initial state, queens are placed randomly and the ontology contains a
symmetric, transitive role to describe which queen movements are legal.
Similarly to Drones, the planner must find a sequence of legal moves such that
no two queens threaten each other.

  * •

RobotConj is a redesign of Robot, moving complexity from action descriptions
into the ontology. The original Robot benchmark encoded static knowledge about
2D-grid cell adjacency in the action descriptions, which via the use of Horn
clauses can be encoded much more naturally directly in the ontology. More
precisely, in a slightly simplified notation, the action MoveDown contains the
two redundant conditional effects

(when (and (AboveOf1 ?x) (BelowOf2 ?x)) (85) $\displaystyle\textsf{ (Row0
?x))},$

which one can read as “if the robot is above or in row 1 and below row 2, then
move the robot to row 0”, and

(when (Row1 ?x)) (86) $\displaystyle\textsf{ (Row0 ?x))},$

i.e. “if the robot position is in row 1, then move the robot to row 0”.
However, encoding the static knowledge that AboveOf1 and BelowOf2 imply Row1
is beyond DL-Lite. Moreover, the actions MoveUp, MoveLeft, and MoveRight have
similar redundant effects. For RobotConj we have simplified these descriptions
by using axioms like
$\textsf{AboveOf1}\sqcap\textsf{BelowOf2}\sqsubseteq\textsf{Row1}$, which
allows us to get rid of (85).