Suppose a factory database records that Maya operates a milling machine. It does not record her department or repeat the classification Employee(Maya). A background ontology may say that every machine operator works for an engineering department and that anyone who works for a department is an employee. Under open-world semantics, the missing department need not be named: the theory entails that some suitable department exists and that Maya is an employee. An action whose precondition asks the ontology whether Maya is an employee may therefore be applicable.

Standard PDDL starts elsewhere. A finite state is a set of ground atoms under a closed-world assumption. If Employee(Maya) is absent, the atom is false unless a derived-predicate rule makes it true. The fixed object set and explicit interpretation are strengths for planning algorithms, but they do not automatically reproduce description-logic entailment. Naïvely copying the database into PDDL would silently change which actions are legal.

The authors frame ontology formulae as global state constraints, rather than merely local action preconditions. A precondition only has to hold where an action is attempted. A state constraint says which environment states are admissible throughout a plan. This matters after effects: an action that adds an explicit fact can make the state inconsistent with the ontology even if its own precondition held before execution.

The proposed bridge is compilation. Instead of writing a new planner, translate the ontology-aware task into standard PDDL with derived predicates. Existing planners may then search, while rules recompute the consequences needed for conditions. This is not simply a software conversion. A valid compilation must preserve plan existence and control how domain size and plan length change. Otherwise a translation could hide the original problem in an enormous artefact or an impractically long plan.

A description-logic TBox is a finite set of restricted first-order axioms over unary and binary predicates. It expresses intensional knowledge such as inclusions, disjointness, role relationships and existential requirements. The state: also called an ABox in description-logic usage: is a finite set of ground atoms. Predicates of arity above two may appear in the planning state but not in the TBox, so those higher-arity relations retain an essentially closed-world reading.

Open-world entailment ranges over all interpretations, potentially infinite ones, that satisfy the state and TBox. A claim is entailed only if it holds in every such interpretation. Absence does not by itself imply falsity. This is a discipline against treating an incomplete record as a complete universe. It also permits the TBox to require objects that the state never explicitly names. State-boundedness limits named objects in reachable states; it does not erase these semantic witnesses.

A conjunctive query is an existential conjunction of unary and binary atoms. A union of conjunctive queries disjoins several such patterns. An instance query is the smallest case, asking whether an individual belongs to a concept. Extended conjunctive queries, or ECQs, combine ontology-mediated query atoms with direct state atoms, negation, conjunction and existential quantification. Brackets carry the crucial signal: B(x) consults the explicit finite state, whereas [B(x)] asks what the state plus TBox entails.

Take a state containing only C(a) and a TBox containing C ⊑ B. The direct atom B(a) is not satisfied in the state. The bracketed query [B(a)] is satisfied because every model of the theory places a in B. ECQ negation applies to the result of this evaluation. It therefore lets a condition combine database-style tests with ontology-aware tests in one formula, while preserving which semantics each subexpression uses.

An eKAB domain description is a triple of predicates, DL actions and a TBox. A DL action has parameters, an ECQ precondition and a finite set of conditional effects. Each effect has local variables, an ECQ condition, an add set and a delete set. The action manipulates explicit atoms. The TBox is not rewritten by an action; it remains the background against which every new state is interpreted.

An eKAB task adds a possibly infinite object supply, a finite set of initially available objects, a TBox-consistent initial state and a closed ECQ goal. A ground action is applicable when its precondition is satisfied under the combined state-and-TBox semantics and the resulting explicit state remains consistent with the TBox. A plan is a sequence of such actions whose final state entails the goal.

Action parameters that do not occur in the precondition can introduce fresh objects. Without control, reachable states can keep accumulating names. The literature therefore considers b-bounded tasks: every reachable state contains at most b explicit objects. A known abstraction allows relevant plans to use a finite representative pool composed of initial objects, enough slots for an action’s parameters and the state bound. Fresh representatives can be renamed back to genuinely fresh objects when needed.

The finiteness assumption is about explicit state vocabulary, not domain closure for the ontology. The TBox may still entail anonymous individuals, and those witnesses remain outside the explicit object bound. This subtlety is necessary: replacing open-world reasoning with fixed-domain reasoning would change the source semantics before compilation even began. For presentation, the paper also reduces goals to a single closed-world atom; a general goal can be moved into the precondition of a final action that adds this atom.

A PDDL domain here contains ordinary predicates, disjoint derived predicates, actions and rules. Rule heads are derived predicates; bodies are first-order formulae over ordinary and derived vocabulary. Stratification orders predicates so positive dependencies do not point upwards and negative dependencies point strictly downwards. Exhaustive evaluation stratum by stratum yields a unique minimal Herbrand model extending the current state.

Actions may consult this derived closure in preconditions and conditional effects, but their add and delete lists contain only ordinary predicates. That separation makes derived facts views of the current state rather than persistent data. After an action alters ordinary facts, rule evaluation recomputes the view. This closely matches the desired role of ontology consequences, provided suitable query rewritings exist.

The authors adapt Nebel’s formal notion of a compilation scheme. Four functions transform the domain, add auxiliary objects, translate the initial state and translate the goal. Plan existence must agree in both directions. Initial-state and goal translations must be polynomial-time computable. The domain description and auxiliary object set determine whether the compilation is polynomial or exponential in size.

Plan length is separately protected. Polynomial preservation permits a polynomial increase, linear preservation fixes degree one, and exact preservation uses unit coefficient apart from a fixed constant. These conditions prevent a misleading claim that one language is no more expressive than another merely because an unbounded translator can solve the instance or encode each source action as an exponential target sequence.

Assume the task is state-bounded and every union of conjunctive queries appearing in its ECQs: as well as the inconsistency query ⊥: has a stratified Datalog¬ rewriting with respect to the TBox. The compiler unions these rewritings. ECQ query atoms can then be replaced by the corresponding derived predicates, turning open-world condition evaluation into closed-world evaluation over a rule closure.

The first problem is that a Datalog rewriting may derive predicates with names also used as mutable state predicates, while PDDL forbids action effects on derived predicates. The compiler creates a disjoint primed signature. For every ordinary predicate P, a rule P′(x) ← P(x) copies current explicit facts into the inference layer. The rewritten TBox and queries use primed symbols. Actions still add and delete unprimed atoms. Inference observes state without becoming writable state.

The second problem is auxiliary constants introduced by a rewriting. If the planner were allowed to bind ordinary action parameters to them, the compilation would invent behaviours absent from the eKAB. A special initialisation action sets a flag S and marks each rewriting-only object with N. Every ordinary action requires S and ¬N for its parameters. Thus auxiliary names may support inference but may not masquerade as domain objects in action instances.

The third problem is ontology inconsistency. The rewriting for ⊥ derives a special predicate P⊥ when the copied state violates the TBox. Ordinary action conditions and the final goal require ¬P⊥. The target therefore cannot proceed through a state that the source regards as semantically impossible. With rewritten preconditions and effect conditions, the same ground actions are available and produce equivalent explicit successors.

Theorem 1 states that this construction is a compilation scheme preserving plan size exactly, modulo the one fixed initialisation action. The domain artefacts depend only on the source domain description, and instance translations remain polynomial. The proof aligns consistency checks, query answers, parameter ranges, transitions and goal reachability. The result is generic: any ontology language: or even individual TBoxes and queries: with the required rewritability can use it.

A stratified Datalog¬ rule has an atom in its head and a conjunction of literals in its body. Predicates are partitioned into strata. Positive dependencies may stay within a stratum; negative dependencies must point strictly to an earlier one. Evaluating strata in order yields a minimal Herbrand model. This gives PDDL derived predicates a deterministic meaning even when rule bodies include negation.

A TBox and UCQ are Datalog¬-rewritable when a finite rule set and a distinguished result predicate return exactly the ontology-entailment answers for every state and substitution over its explicit objects. Rewritings may use auxiliary predicates and constants. ECQs inherit the property: union the rewritings for all bracketed UCQs, then replace each bracketed query atom with its result predicate inside the remaining first-order formula.

The paper assembles earlier results into an expressivity map. Horn-SHIQ UCQs have an exponential Datalog rewriting implemented by CLIPPER. The sublogic ELH⊥ has a polynomial version. DL-Lite also permits polynomial compilation in the setting used here. Instance queries over Horn-SHOIQ have suitable results, though the full Horn-SHOIQ position for the broader query setting is left between the paper’s positive and negative frontiers.

Polynomial size is not the same as practical compactness. A polynomial rewriting can introduce high-arity predicates and large constants, while a theoretically exponential construction may remain small on ordinary inputs and use constant-sized rules. The authors therefore separate their theoretical Horn-ALCHOIQ construction from the implemented evaluation, which uses CLIPPER’s existing Horn-SHIQ rewriting. That choice is honest: experiments test the generic compilation architecture with a practical rewriting, not the new theoretical rewriting itself.

The starting combined approach for Horn-ALCHOIQ query answering translates TBox axioms into Datalog and then filters candidate query matches. A direct form can be exponential because it introduces a constant tX for every relevant set X of unary predicates, representing an anonymous object satisfying that type. The paper first works in an extended notation, Datalog with set terms and stratified negation, where the set itself can occur compactly as an argument.

Predicates such as role(r,X,Y) express that the objects represented by type sets X and Y are connected by role r. Polynomially many rules compute a partial expansion of the input state, yielding additional candidate matches that account for anonymous objects. Further strata construct a dependency graph over query variables and reject spurious matches: for example, matches whose supposed anonymous witness structure cannot be realised consistently or whose dependencies form a prohibited cycle.

A known polynomial translation then removes the set-term notation, producing ordinary stratified Datalog¬. Correctness follows from the combined-approach result once the compact reconstruction and filtration have been encoded. Theorem 2 states that unions of conjunctive queries over Horn-ALCHOIQ TBoxes have polynomial-size Datalog¬ rewritings.

Combined with Theorem 1, this yields a polynomial compilation of Horn-ALCHOIQ eKABs into PDDL with exactly preserved plan size. The authors call the construction complex but theoretically significant. The significance lies in locating a broad region where open-world ontological state constraints add modelling convenience without adding formal planning expressivity beyond the target, under the paper’s compilation measure.

A complex role inclusion can state that a chain of roles is included in another role. It enables long relational consequences to be described succinctly. That extra succinctness changes the relevant query-answering complexity. The paper first establishes that polynomial-step plan existence for PDDL with derived predicates is EXPTIME-complete: candidate plans of the bounded length can be enumerated within exponential time, with derived closure evaluated after each action.

By contrast, even one-step plan existence for Horn-SROIQ eKABs is 2EXPTIME-complete. Hardness comes from description-logic reasoning; membership follows by enumerating one-step candidates and evaluating the conjunctive queries within the double-exponential bound. A mere gap in uniform complexity does not yet rule out compilation because the domain compiler is permitted arbitrary computation so long as it emits only polynomially many bits.

The decisive argument therefore uses non-uniform complexity and advice-taking Turing machines. The authors construct domain descriptions indexed only by input length. If a polynomial compilation existed, its translated domain could serve as polynomial advice. An exponential-time target procedure could then decide computations that encode double-exponential behaviour. This would imply EXPTIME^NP=EXPTIME, collapsing the weak exponential hierarchy: an outcome complexity theory regards as unlikely.

Theorem 5 concludes conditionally that no polynomial compilation from Horn-SROIQ eKABs to PDDL can preserve plan size polynomially. A corollary rules out polynomial Datalog¬ rewritings for instance queries in general. Similar conditional non-compilability results follow for the non-Horn logics SH and ALCI. The statement is carefully bounded: it does not say no particular Horn-SROIQ ontology can be rewritten, no exponential compiler can exist, or no specialised planner can reason in the source language.

The implementation reads an ontology in Turtle and an extended PDDL file whose conditions may contain conjunctive queries. CLIPPER generates a Horn-SHIQ Datalog rewriting. A Tseitin-like normalisation avoids duplicating complex conditions, and the generic compiler emits standard PDDL. Fast Downward 20.06 runs dual-queue greedy best-first search with the hFF heuristic. Tests used an Intel Core i5-4590 at 3.30 GHz, a 600-second time limit and an 8 GB memory limit.

The collection has 235 instances: 125 adaptations from seven DL-Lite eKAB domains and 110 new instances. The adapted domains are Cats, Elevator, Robot, TaskAssign, TPSA, VTA and VTA-Roles. The new Drones, Queens and RobotConj domains exploit conjunction, qualified existential restrictions in negative positions, symmetric relations or transitive relations unavailable in DL-Lite. RobotConj moves grid knowledge from repetitive conditional effects into an ontology.

For scalability, Robot and RobotConj are each extended through 56 grids from 3×3 to 200×200. Domain size grows linearly with grid dimension. Even the largest tested tasks compile and solve in under 90 seconds. RobotConj is consistently faster to compile and plan than Robot, despite the richer ontology, because the actions become simpler. This is a concrete case where representational abstraction helps the downstream search.

On the 125 adapted instances, the original Cal16 compiler solves 85, the optimised Bor21 compiler 95 and the Horn pipeline 125, according to the aggregate table. The Horn compiler processes every adapted instance, generally in under one second per domain average, with an approximately 0.6-second fixed CLIPPER overhead. For the 110 expressive instances, compilation succeeds for all; Fast Downward solves 91. Drones and Queens were intentionally made challenging, so unsolved tasks reflect planning search after successful compilation.

These results support feasibility and a favourable comparison on this benchmark suite. They do not benchmark the paper’s polynomial Horn-ALCHOIQ rewriting, prove superiority over every ontology planner, or isolate every source of speed-up. The same Fast Downward configuration receives differently compiled models, and representational simplification can affect heuristic search. The correct conclusion is that a generic rewriting-based pipeline can be practically useful, not that more expressive ontologies are inherently faster.

For a rewritable Horn ontology, observed facts can remain an explicit operational ledger while the TBox carries durable conceptual constraints. The compiler turns only the required inference interface into derived predicates. This maintains a clean division between what a sensor or action writes and what background knowledge entails. It also allows mature classical planners to be reused without pretending that missing source facts were false.

The generic theorem is modular. Improve a query rewriting, and the planning compiler inherits the improvement. Choose a smaller description logic, a restricted query class or a favourable individual TBox, and a cheaper route may be available. Conversely, complex role inclusions signal that a polynomial compilation guarantee may be too much to ask. At that boundary, a system designer can restrict the ontology, accept larger compilation, or use a source-native reasoning architecture.

Several caveats matter. The task model is deterministic and state-bounded. The ontology remains fixed while actions modify explicit facts. Plans are judged by existence and length, not by compilation latency, rule arity or heuristic quality. The new Horn-ALCHOIQ rewriting is a theoretical construction; the experiments instantiate Horn-SHIQ through CLIPPER. The negative result relies on a complexity separation and applies in general, not to every domain.

For the wider canon, Paper 0107 extends the translation theme of Paper 0106. The previous paper combines discrete choices with numerical constraints for hybrid time. This paper combines finite closed-world search with open-world ontological inference. Both succeed by drawing a precise interface between reasoning regimes. Paper 0108 turns to HDDL 2.1 and asks how temporal hierarchical task networks should be given a shared formal language and semantics.