Computational Aspects of Progression for Temporal Equilibrium Logic

Thomas Eiter, Davide Soldà

Abstract

Temporal logic plays a crucial role in specifying and reasoning about dynamic systems, where temporal constraints and properties to be monitored are essential. Traditional approaches like LTL-monitoring assume monotonicity, which limits their applicability to scenarios involving non-monotonic temporal properties. We delve into complexity aspects of monitoring temporal specifications using non-monotonic Temporal Equilibrium Logic (TEL), a temporal extension of Answer Set Programming defined over Temporal Here and There Logic (THT) with a minimality criterion enforcing stable models. Notably, we study the complexity gap between monitoring properties in THT and TEL semantics, and the complexity of monitoring approximations based on progression, which is widely used in verification and in AI. In that, we pay particular attention to the fragment of temporal logic programs.

Introduction

In AI and verification, real-time monitoring of dynamic systems is essential for ensuring safety and correctness. While Linear Temporal Logic (LTL) is the standard for such tasks, it is inherently monotonic: once a property is satisfied, additional information cannot invalidate it. This limitation makes LTL unsuitable for complex AI scenarios involving defaults, exceptions, or the principle of inertia.

Temporal Equilibrium Logic (TEL) addresses these needs by providing a non-monotonic framework. However, the power of TEL comes at a high computational cost. This paper investigates the complexity of monitoring TEL and explores progression—a technique that partially evaluates formulas as data arrives—as a means to achieve practical efficiency.

The Monitoring Framework

To monitor properties in a non-monotonic setting, the authors define a 3-valued semantics ($THT_3$ and $TEL_3$). In this framework, a property can be evaluated as True (satisfied), False (violated), or Unknown (pending further observations).

The 3-valued monitoring state machine illustrates how the minimality criterion (red) distinguishes TEL from THT in transitioning from an unknown state to a terminal truth value.

The transition between these states is governed by the existence of equilibrium traces. As shown in the figure above, the "minimality criteria" is the defining feature of TEL, ensuring that only stable models are considered. This allows the monitor to move from an uncertain state (?) to a terminal state ($\top$ or $\perp$) based on whether the current finite trace can be extended into an equilibrium trace.

Conditions for determining the truth value of a finite trace $T^f$ based on the existence of equilibrium extensions.

Progression and Complexity

Progression ($P_{TEL}$) is the core technique proposed to handle infinite or long-running data streams. Instead of re-evaluating the entire system history at every step, the formula is "progressed" to a new version that represents the remaining requirements for the future.

The research reveals a significant complexity gap:

  • Exact TEL Monitoring: Proven to be EXPSPACE-complete, making it significantly harder than standard LTL monitoring.
  • TEL Progression: The progression operator itself is $D^p$-complete, which is roughly the difficulty of two NP problems—a substantial improvement over the full monitoring task.
  • THT Progression: Monitoring the monotonic base logic (THT) using Directed Acyclic Graphs (DAGs) to share sub-formulas is feasible in polynomial time.

Tractable Fragments for Practical Use

The most significant finding for practitioners is the identification of tractable fragments. For "Normal" or "Head-Cycle-Free" (HCF) temporal logic programs—the structures most commonly used in Answer Set Programming—progression becomes polynomial time. This result provides a theoretical foundation for building high-performance, real-time monitors for complex non-monotonic rules.

Conclusion and Future Work

While exact monitoring in TEL is computationally daunting, progression offers a sound and efficient approximation. Future work aims to integrate these DAG-based progression algorithms into existing solvers like telingo and to extend the framework to handle nondeterministic observations and more complex past-time operators.

Summary updated

Abstract

Temporal logic plays a crucial role in specifying and reasoning about dynamic systems, where temporal constraints and properties to be monitored are essential. Traditional approaches like LTL-monitoring assume monotonicity, which limits their applicability to scenarios involving non-monotonic temporal properties. We delve into complexity aspects of monitoring temporal specifications using non-monotonic Temporal Equilibrium Logic (TEL), a temporal extension of Answer Set Programming defined over Temporal Here and There Logic (THT) with a minimality criterion enforcing stable models. Notably, we study the complexity gap between monitoring properties in THT and TEL semantics, and the complexity of monitoring approximations based on progression, which is widely used in verification and in AI. In that, we pay particular attention to the fragment of temporal logic programs.
BibTeX
@inproceedings{eiter2024computational,
  author = {Thomas Eiter and Davide Soldà},
  title = {{Computational Aspects of Progression for Temporal Equilibrium Logic}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=wbWj1pjZ2Q},
}
Figure