Monitoring Data-aware Temporal Properties (Extended Version)

Alessandro Gianola, Marco Montali, Sarah Winkler · 2026

Read Monitoring Data-aware Temporal Properties (Extended Version) by Alessandro Gianola, Marco Montali, Sarah Winkler (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-14666.txt.

Introduction

Gianola, Montali and Winkler develop early-warning monitoring for linear-time properties plus an SMT theory over finite traces. Monitoring here is hard. The state depends on both the trace seen so far and every possible finite continuation. Under mild assumptions on the background theory, they prove a framework correct. It pairs automata methods for the temporal side with machine reasoning for the first-order side. Decidable cases are also found, covering linear arithmetic with uninterpreted functions.

Catalog record

CREATORAlessandro Gianola, Marco Montali, Sarah Winkler
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE90950
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.14666

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Monitoring Data-aware Temporal Properties (Extended Version) Alessandro Gianola, Marco Montali, Sarah Winkler Abstract Dynamic systems in AI are often complex and heterogeneous, so that an internal specification is not accessible and verification techniques such as model checking are not applicable. Monitoring is in such cases an attractive alternative, as it evaluates desirable properties along traces generated by an unknown dynamic system. In this work, we consider anticipatory monitoring of linear-time properties enriched with an arbitrary SMT theory over finite traces (LTL M ​ T f {}_{f}^{MT} ). Anticipatory monitoring in this setting is highly challenging, as the monitoring state depends on both the trace prefix seen so far and all its possible finite continuations. Under reasonable assumptions on the background theory, we present and formally prove the correctness of a novel foundational framework for monitoring properties in an expressive fragment of LTL M ​ T f {}_{f}^{MT} . The framework combines automata-theoretic methods to handle the temporal aspects of the logic, with automated reasoning techniques to address the first-order dimension. Moreover, we identify for the first time decidable fragments of this monitoring problem that are practically relevant as they combine linear arithmetic with uninterpreted functions, which covers e.g. data-aware business processes and dynamic systems operating over a read-only database. Feasibility is witnessed by a prototype implementation and preliminary evaluation. 1 Introduction Complex, dynamic AI systems increasingly comprise autonomous agents and heterogeneous components with unknown, inaccessible, or opaque internal specifications. This hampers the possibility of ascertaining their safety and trustworthiness through traditional design-time verification methods such as model checking and testing. A remedy in such situations is to keep track of desired properties at runtime, by monitoring the executions of the black-box system under scrutiny. A widely known, solid approach to monitoring is that of runtime verification (RV), where given a logical property, a corresponding monitor can be automatically constructed, with the guarantee that it will emit a provably correct verdict 44 . These advantages have fostered the application of RV in various AI contexts, including multiagent systems 20 ; 3 , robotics 11 , cyber-physical systems 50 , and business processes 47 ; 13 . The vast majority of such approaches specify properties using variants of linear-time temporal logic (LTL). 44 ( 44 ) point out two key insights in monitoring: First, since the trace \tau seen so far is necessarily of finite length, this calls for a finite-trace semantics for LTL. However, as the system evolves, \tau is only the prefix of a (yet unknown) continuation. Different variants of LTL then have to be studied depending on whether such a continuation eventually terminates, or continues forever. In many AI-relevant settings (e.g., planning and business processes 4 ; 5 ; 24 ; 22 ) the monitored system operates for an unbounded, yet finite, number of steps. This means that also each one of the (infinitely many) possible suffixes of \tau has a finite length, making LTL f (LTL over finite traces 24 ) a natural candidate logic for monitoring 23 ; 21 ; 13 . A key limitation of many of these approaches is that LTL f is propositional and cannot express properties about structured data. This is ubiquitous in AI systems, as witnessed by the new agentic wave, where agents are often delegated to execute business tasks and processes, and have consequently to deal with different types of structured data, such as numbers with arithmetic, sets, lists, and uninterpreted functions. Recently, 35 ( 35 ) brought forward LTL f modulo theories (LTL {}_{f}^{MT} ) to enrich LTL f with the full spectrum of theories supported by state-of-the-art SMT 7 solvers, which include all the datatypes mentioned before. The following example illustrates the need for such rich properties: Example 1 . Consider an online marketplace for concert tickets. A buyer agent dynamically receives ticket offers, and is tasked by its human principal with the goal of selecting the best offer (that is, the ticket with the lowest price) for a given concert (indicated by constant \mathtt{myc} below). Every ticket has two properties: its price, and the concert it refers to. Formally, this setting is captured by three datatypes \mathit{Ticket} , \mathit{Concert} (with \mathtt{myc}\,{\in}\,\mathit{Concert} ), and the real numbers \mathbb{R} , a dedicated constant \mathtt{undef} of type \mathit{Ticket} and functions \mathop{price}\colon\mathit{Ticket}\to\mathbb{R} and \mathop{con}\colon\mathit{Ticket}\to\mathit{Concert} that resp. assign to each ticket its price and the concert it is for. Such two functions conceptually model a database table with three columns, where each record stores a ticket id (primary key) with its price and concert. The agent should select the cheapest ticket. An execution consists of a trace where at each time step the values of two variables of type \mathit{Ticket} are specified: t , the ticket currently offered by the marketplace; and b , the ticket currently bookmarked by the agent. Since the agent specification is not accessible, its human principal wants to formalise the expected behavior and check whether the agent indeed adheres to it. To this end, the principal constructs a suitable LTL {}_{f}^{MT} formula composed of different parts. The first part \psi_{change} captures the situation where the bookmarked ticket must be changed to the currently received one, because it has a lower price. The notation \lhd{b} is used here to refer to the previous value of variable b , i.e., the value b held in the instant before the current one. With this notation at hand, we set \psi_{change} as \mathop{con}(t)\,{=}\,\mathtt{myc}\land(\lhd{b}\,{=}\,\mathtt{undef}\lor\mathop{price}(t)<\mathop{price}(\lhd{b}))\to b\,{=}\,t Next, the formula \psi_{keep} deals with the case where the bookmarked ticket is kept, since the currently received ticket either refers to a concert of no interest, or has a higher price than the bookmarked one. Formally, \psi_{keep} is given by (\mathop{con}(t)\,{\neq}\,\mathtt{myc}\lor(\lhd{b}\,{\neq}\,\mathtt{undef}\land\mathop{price}(t){>}\mathop{price}(\lhd{b})))\to b{=}\lhd{b} To bundle everything together, we assume for simplicity that the ticket stream starts at the second instant. We can hence require that b is initially \mathtt{undef} , while the formulae \psi_{keep} and \psi_{change} must hold in every instant of the trace, starting from the next one. 1 1 1 We assume for simplicity that if a ticket with the same price appears, the agent keeps the one already bookmarked. The latter condition is captured using the LTL f operators \mathsf{X} and \mathsf{G} , yielding \psi:=(b\,{=}\,\mathtt{undef})\wedge\mathsf{X}\mathsf{G}(\psi_{change}\wedge\psi_{keep}) Differently from the simpler settings of propositional LTL f 21 , or of LTL f extended with numerical variables 34 , where a trace is simply a sequence of assignments, dealing with LTL {}_{f}^{MT} also requires to keep track of a first-order model M . In Ex. 1 , this corresponds to the set of tickets seen in the trace, as well as their prices and concerts. Therefore, different interpretations of the monitoring problem are conceivable: the model underlying a trace can be considered as fixed, or it may be assumed to change in every step. In this work, we adopt the following: given a trace \tau with model M , a continuation of \tau provides an extension of M – a notion that we later anchor precisely to the model-theoretic concept of embeddings . This interpretation has the following advantages: (1) the current model, dealing with the trace seen so far, is extended only conservatively, in that facts concerning the previous elements must be kept throughout the trace, and

Read the complete text