Introduction
In the field of Knowledge Representation (KR), a long-standing objective has been the seamless integration of dynamic reasoning—modeling how the world changes through actions—with static structural knowledge, typically represented via ontologies. This paper, presented at IJCAI 2015, investigates the computational boundaries of combining the Situation Calculus, a premier framework for reasoning about action, with Description Logics (DLs), the formal foundation for the Semantic Web and modern ontologies.
The authors demonstrate a sobering reality: even the most restricted combinations of these two formalisms result in undecidability. This finding suggests a fundamental theoretical barrier in the "two-dimensional" semantics inherent in systems that track both the evolution of situations and the complex relationships between domain objects.
The Challenge of Two-Dimensional Reasoning
The difficulty arises from the intersection of two distinct logical dimensions. The Situation Calculus manages the flow of time and the consequences of actions (e.g., moving an object changes its coordinates). Description Logics, conversely, define invariant domain constraints (e.g., "every employee must belong to a department").
Researchers have sought to use DL ontologies as "state constraints" within the Situation Calculus to ensure that the rules of a domain are preserved across action sequences. However, this combination creates a complex model-theoretic structure where one dimension represents the sequence of situations and the second represents the domain of individuals. Previous research had suggested that such 2D structures are prone to undecidability; this paper quantifies exactly how much simplicity is required to regain decidability, ultimately finding that even extreme restrictions do not suffice.
Methodology: Reductions to Undecidable Problems
To establish undecidability, the authors employ a reduction strategy, mapping known computationally impossible problems into the combined logic. They focus on two primary methods:
- The Tiling (Domino) Problem: The authors show that a Situation Calculus theory integrated with the DL $\mathcal{ALC}$ can effectively represent an infinite 2D grid. By encoding the rules of a tiling problem into the axioms of the logic, they prove that checking the satisfiability of a scenario is equivalent to solving the tiling problem, which is known to be undecidable.
- Turing Machine Halting: For even simpler, "lightweight" DLs such as DL-Lite and $\mathcal{EL}_\bot$, the authors demonstrate how to encode the entire execution trace of a Turing Machine. If the combined logic were decidable, it would provide a solution to the Halting Problem—a mathematical impossibility.
Crucially, these reductions are applied to highly restricted versions of the Situation Calculus. The authors analyze theories that are both context-free (where action effects are independent of the current situation) and have local effects (where actions only modify the properties of the objects they directly interact with).
Key Insights: The Role of Inertia and Cycles
The paper identifies two primary drivers of undecidability in these combined frameworks:
- The "Inertia" Trap: In the Situation Calculus, the "frame problem" is addressed through Successor State Axioms (SSAs), which dictate that properties remain unchanged unless an action specifically modifies them. This mechanism essentially provides the logic with a "memory" of previous states. When this memory is combined with the ability of DLs to imply the existence of new, anonymous objects, it allows for the construction of the infinite structures necessary for undecidability.
- The Crux of Cycles: The authors pinpoint "cyclic assertions" (e.g., $A \sqsubseteq \exists R.A$, implying every $A$ has an $R$-successor that is also an $A$) as the critical element. These cycles allow the logic to force the existence of infinite chains of objects over time, which, when coupled with the "memory" provided by SSAs, enables the simulation of a Turing Machine tape or a 2D grid.
Results and Impact
The study culminates in several key theorems that delineate the boundaries of decidability:
- Theorems 1 & 2: Confirm that satisfiability for the Situation Calculus combined with standard DLs like $\mathcal{ALC}$ or $\mathcal{AL}$ is undecidable.
- Theorems 3 & 4: Demonstrate that undecidability persists even when using the most "neutered" action theories (local effect, context-free) and lightweight DLs like DL-Lite or $\mathcal{EL}_\bot$. This is particularly significant because DL-Lite is the foundation of the OWL 2 QL profile, designed for efficient data access.
These results effectively demonstrate that a "naive" union of Situation Calculus axioms and DL TBoxes is computationally intractable. One cannot simply merge the two formalisms and expect automated reasoning to be possible.
Conclusion and Future Directions
The findings of this paper suggest that to achieve a decidable combination of dynamic and structural reasoning, researchers must look beyond simple axiomatic unions. The authors suggest two potential paths forward:
- Further DL Restrictions: Exploring even weaker languages, such as RDFS, which do not allow for the existential cycles that facilitate undecidability.
- Alternative Architectures: Moving toward "functional" or "loosely coupled" views, such as Levesque’s ASK/TELL architecture. In these models, the action layer and the ontology layer are strictly separated, interacting only through specific queries rather than shared logical space. This approach has shown promise in maintaining decidability while still allowing for rich domain modeling.
Summary updated