Description Logic Based Dynamic Systems: Modeling, Verification, and Synthesis

Diego Calvanese, Marco Montali, Fabio Patrizi, Giuseppe De GiacomoIJCAI 2015

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.

Figure 2: An example of a data-aware process involving credit card registration and payment status.

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).

Figure 1: The formal mechanism of a labeled transition in a DLDS, showing the evolution from a current state to a next state via parameter selection and effect functions.

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:

  1. 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.
  2. 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

BibTeX
@inproceedings{calvanese2015description,
  author = {Diego Calvanese and Marco Montali and Fabio Patrizi and Giuseppe De Giacomo},
  title = {{Description Logic Based Dynamic Systems: Modeling, Verification, and Synthesis}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure