Verification and Monitoring for First-Order LTL with Persistence-Preserving Quantification over Finite and Infinite Traces

Diego Calvanese, Giuseppe De Giacomo, Marco Montali, Fabio PatriziIJCAI 2022 · DOI

TL;DR

This paper tackles the challenge of verifying and monitoring dynamic systems whose states are described by first-order logic interpretations, especially when new objects can be introduced during execution. They introduce a restricted logic, LTL-FOp, which focuses on objects that persist across states, making verification and monitoring decidable for state-bounded systems, a crucial step for practical applications like process mining.

What Problem Does This Paper Address?

Modern systems, from AI agents to complex software, often involve dynamic states where the set of relevant "objects" can change over time. Think of a robot interacting with objects in a room, or a database system handling new customer records. Formally modeling these systems requires first-order logic (FOL) to represent the objects and their properties. Temporal logics are then used to specify desired behaviors over time.

However, combining FOL with temporal logic (specifically, Linear Temporal Logic or LTL) leads to significant theoretical challenges. While some temporal logics (like the µ-calculus) have decidable verification for these systems under certain conditions (state-boundedness), standard LTL with FOL (LTL-FO) is generally undecidable. This paper addresses this gap by identifying a decidable fragment of LTL-FO, called LTL-FOp, that is suitable for verifying and monitoring these dynamic systems, particularly when the number of objects in any given state is bounded. This decidability is crucial for practical applications where we need to ensure systems behave correctly and to monitor ongoing executions.

Methods

The authors build upon existing work on relational transition systems (RTSs) and first-order temporal logics. Their core contribution lies in defining and analyzing two fragments of LTL-FO:

  • LTL-FOa: Quantifiers range over "active" objects (those present in the current state).
  • LTL-FOp: Quantifiers range over "persisting" objects (those present in the current state and in the next state).

They first re-establish the undecidability of LTL-FOa (and thus LTL-FO) by isolating the source of this complexity. The key innovation is then proving the decidability of LTL-FOp for state-bounded and generic RTSs. This decidability is achieved by leveraging techniques like persistence-preserving bisimulation and abstraction, which allow them to reduce the problem to checking finite-state systems.

For monitoring, they extend the concept of 4-valued semantics (RV-LTL) to their first-order setting. This allows them to determine the current and future status of a property (satisfied, violated, possibly satisfied, possibly violated) given a finite trace of an ongoing execution.

Datasets

Not discussed in the paper. The paper focuses on theoretical decidability results and formalisms rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • The Devil is in the Details of Quantification: The paper highlights how the scope of quantifiers in first-order temporal logic dramatically impacts decidability. While quantifying over any active object (LTL-FOa) leads to undecidability, restricting it to objects that persist across states (LTL-FOp) unlocks decidability for important classes of systems.
  • Persistence is Key to Decidability: The core insight is that by focusing on objects that remain active across consecutive states, we can manage the complexity introduced by first-order logic. This "persistence-preserving" quantification allows for effective abstraction and model checking.
  • Bridging Theory and Practice: The decidability of LTL-FOp verification directly enables practical monitoring of dynamic systems. This is particularly relevant for fields like Process Mining, where real-time monitoring of ongoing business processes is essential.
  • Undecidability Source Isolated: The paper clarifies that the undecidability of LTL-FO stems from the ability to encode arbitrary counter machines, a capability that is preserved even in the LTL-FOa fragment.

Key Results

  • LTL-FO verification is undecidable: This is re-established for LTL-FOa and LTL-FO.
  • LTL-FOp verification is decidable: For state-bounded and generic relational transition systems (RTSs), model checking LTL-FOp properties is decidable. This is a significant theoretical advancement.
  • LTL-FOp monitoring is decidable: The paper shows that monitoring LTL-FOp properties over state-bounded traces is also decidable, making it applicable to real-world scenarios.
  • Persistence-Preserving Equivalence: A formal notion of equivalence is introduced, which is crucial for relating different traces and systems while respecting object persistence.

Limitations and Future Work

  • State-Boundedness Assumption: The decidability results for LTL-FOp rely on the assumption of state-boundedness, meaning the number of objects in any state is limited. While this is a common and practical assumption, it might not hold for all dynamic systems.
  • Focus on Situation Calculus: While the results are presented in the context of situation calculus, the authors note they apply to other formalisms that guarantee genericity and boundedness. Future work could explore these broader applications.
  • Automata-Based Techniques: The authors suggest developing automata-based techniques for verification and monitoring of LTL-FOp. This would likely lead to more efficient algorithms and practical implementations.
  • Broader Monitoring Scenarios: Extending the monitoring framework to handle infinite traces and more complex execution continuations is a potential avenue for future research.

Summary updated

BibTeX
@inproceedings{calvanese2022verification,
  author = {Diego Calvanese and Giuseppe De Giacomo and Marco Montali and Fabio Patrizi},
  title = {{Verification and Monitoring for First-Order LTL with Persistence-Preserving Quantification over Finite and Infinite Traces}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/354},
}
Figure