Abstract: Modern information systems require the seamless integration of static data structures (ontologies) and dynamic workflows. This paper presents a formal framework for Description Logic Based Dynamic Systems (DLDSs), enabling the verification and automated synthesis of processes that interact with complex knowledge bases. By assuming "state-boundedness"—where the number of active objects at any single time is finite—the authors prove that temporal properties remain decidable even when the system encounters an infinite number of objects over its lifetime.
Introduction: The Gap Between Data and Process
In computer science, static data modeling and dynamic process modeling are often treated as distinct domains. However, real-world "data-aware" processes, such as banking workflows or conference management systems, require a deep intertwining of both. The challenge lies in the fact that combining Description Logics (DLs) with temporal dynamics often leads to undecidability due to the complex interaction between object domains and time.
The DLDS Framework: Formalizing System Evolution
The authors build their framework on Levesque’s functional approach, decoupling the knowledge base (KB) from the progression mechanism. The system evolves through a series of transitions driven by actions. The KB supports two primary operations: ASK (querying the current state) and TELL (updating the state via actions).
As shown in Figure 1, a transition involves selecting parameters ($\pi$), assigning them values ($m$), and applying an effect function ($\tau$) to produce a new state ($A_{new}$). This generic approach ensures that the system's behavior depends on object properties rather than specific identities.
Key Insight: State-Boundedness
The "secret sauce" of this research is the state-boundedness assumption. While a system might encounter an infinite number of objects over its entire execution history, the number of objects stored in the "active" part of the KB (the ABox) at any single point in time is assumed to never exceed a fixed bound $b$. This reflects practical systems where, for instance, a bank processes millions of customers but only a limited number of active transactions at once.
To handle this, the authors utilize $\mu DL_p$ logic, a variant of the $\mu$-calculus that restricts quantification to "live" objects currently in active memory. By using a finite set of "representative" objects to simulate all possible behaviors, the authors construct a finite-state transition system that is behaviorally equivalent (bisimilar) to the potentially infinite-state system.
Verification and Synthesis Results
The paper establishes two major theoretical results:
- Decidability of Model Checking: Verifying $\mu DL_p$ formulas over state-bounded, generic DLDSs is decidable. The complexity is at most exponential in the size of the system specification.
- Decidability of Synthesis: The framework supports adversarial synthesis, allowing for the automatic generation of strategies that force a system toward a goal even in the presence of an unpredictable environment (modeled as a two-player game).
Conclusion and Future Directions
While the results are promising, they rely on the assumption of a known bound $b$. If a system accumulates unlimited objects without deletion, the problem becomes undecidable. Future work aims to implement these theoretical foundations into robust tools for high-level process verification, potentially utilizing lightweight DLs like DL-Lite to optimize computational complexity and ensure practical scalability.
Summary updated