CS Paper Radar

The Infinite, in Finite Time

Rayhana Amjad, Rob van Glabbeek, Liam O'Connor

cs.LO ·submitted 2026-08-24 11:03 UTC · v1
publishedtheory

Abstract

Linear-time temporal properties, such as those described by Linear-time Temporal Logic, are typically modelled as sets of infinite traces. Yet, in a run-time verification context, such as when testing or monitoring a system, only a finite prefix of the system's behaviour can be observed. For some properties, these finite prefixes may be definitive---a yes or no answer can be given without further observation. By enriching the semantics of LTL with these definitive prefixes, we give a proper inductive accounting of the semantics of LTL$_3$, a multi-valued variant of Linear-time Temporal Logic for run-time verification applications. The semantic descriptions of LTL$_3$ in previous work are given only in terms of their relationship to conventional LTL. We show that the semantics of LTL and of LTL$_3$ are isomorphic. In addition, we formalise the formula progression evaluation technique, popularly used in runtime verification contexts, and show its soundness and completeness up to finite traces with respect to our semantics. Then, we turn to linear-time properties more generally: using our theory of definitive prefixes, we re-prove the well-known safety-liveness decomposition theorem, and reconstruct the topology of infinite traces. We define monitorability for properties, providing neat topological characterisations for various monitorability classes, and arrange them into a hierarchy. All of our definitions and proofs are mechanised in Isabelle/HOL.

Comment
This paper contains the material of arXiv:2411.14581

Closest papers

Nearest neighbours by meaning across the whole index.

Progression- vs Automata-based Anticipatory Monitoring of LTL over Finite Traces (Extended Version)

cs.LO cs.AI ·2026-09-26 ·Sarah Winkler, Toryn Klassen, Sheila McIlraith, Marco Montali
similarity 0.80
Abstract

When safety-critical systems are developed from a known internal specification, their correctness can be established by model checking. In the frequent case where such a specification is unknown or inaccessible, runtime verification presents an attractive alternative, e.g., to ascertain that autonomous and agentic systems as well as business processes satisfy desirable properties and/or comply with safety requirements. In this paper we study anticipatory monitoring, an advanced form of runtime verification, where the monitoring state is determined by both the trace prefix seen so far, and all its possible finite-length, future continuations. We focus on monitoring linear-time properties that may involve arithmetic constraints. Automata-based approaches, the de-facto standard in this setting, are notorious for their computational complexity. We propose an alternative approach based on progression and LTLf satisfiability checking, for both propositional and arithmetic settings. We experimentally compare the automata- and progression-based approaches, and a third method that combines the two. Our experiments suggest that the progression-based approach often succeeds in producing a verdict when the automata constructions do not terminate, especially for the arithmetic setting. For the propositional setting, the combined technique provides a good tradeoff.

0.03

MightyPPL : Towards model checking MTL

cs.LO ·2026-09-16 ·Hsi-Ming Ho, Shankara Narayanan Krishna, Khushraj Madnani, Rupak Majumdar, Paritosh Pandya
similarity 0.73
Abstract · Best paper Award at QEST+FORMATS 2026, nominated for Best Artifact Award at QEST+FORMATS 2026

The theoretical foundation for model checking timed systems against Metric Interval Temporal Logic (MITL) was established in the early 1990s, yet the first practical tool supporting future MITL (MightyL) did not emerge until 2017. Recently, there has been growing interest in extending this toolchain to support more expressive logical operators, including past modalities, Pnueli modalities, and limited use of singular intervals. MightyPPL is one such toolchain. We introduce an upgraded version of MIghtyPPL that enables for the first time, the model checking of Metric Temporal Logic (MTL) properties of the form (whenever an event p occurs, it is eventually followed by some event q after exactly some k time units) in addition to Pnueli and Past modalities. We discuss the tool's underlying architecture and implementation, and present a performance evaluation against the Tempora tool across diverse satisfiability and model checking benchmarks, demonstrating that MightyPPL delivers significantly better performance.

0.22

Model Checking HyperRecHML is Decidable

cs.LO cs.FL ·2026-10-15 ·Elli Anastasiadi, Kim Guldstrand Larsen, Martin Zimmermann
similarity 0.72
Abstract

Temporal hyperlogics combine explicit quantification over traces with temporal requirements evaluated over the quantified traces. HyperRecHML is a temporal hyperlogic which allows for arbitrary mixing of trace quantification and the use of fixed points for expressing temporal requirements, which makes it very expressive in comparison to other first-order hyperlogics. HyperRecHML has already been successfully applied in runtime verification, but the decidability of its model checking problem remains open. We answer this question positively by providing two main contributions. Firstly, a normalization procedure that allows to reduce arbitrary HyperRecHML formulas to a normal form with restricted nesting of trace quantification and fixed points. Secondly, we provide an automata-based model checking algorithm for formulas of this normal form. The complexity of our algorithm is comparable to similar ones for other hyperlogics, despite the extra expressive power.

0.16

Runtime Verification under Split Past and Future

cs.LO ·2026-08-21 ·Dogan Ulus
similarity 0.72
Abstract

Runtime assurance for autonomous systems increasingly requires reasoning not only about observed executions but also about anticipated future behaviors. Traditional runtime verification, however, primarily evaluates the execution observed so far and does not directly account for predicted continuations. We propose a formal framework for runtime assurance that combines monitoring of the observed execution with analysis of multiple predicted continuations. To support this integration, we introduce Split Linear Temporal Logic (SplitLTL), a linear-time temporal logic that assigns complementary roles to past and future temporal specifications within a single specification. The past component uses the observed history to determine the assurance requirements applicable at the current point of execution, while the future component evaluates predicted continuations against those requirements. The framework therefore filters predicted continuations according to the requirements induced by the observed history, identifying admissible continuations that can support subsequent decision making. We formally define the syntax and semantics of SplitLTL and present an online monitoring architecture for evaluating observed executions together with predicted continuations.

0.20

Synchronous Observers Revisited for Runtime Verification of Lustre Using STL

cs.LO cs.FL ·2026-08-13 ·Logan Kenwright, Partha Roop, Sobhan Chatterjee, Nathan Allen
published similarity 0.72
Abstract

Signal Temporal Logic (STL) is a popular formalism for the temporal safety properties of cyber-physical systems, most often used for runtime verification. In the synchronous family of languages, safety properties are instead expressed as synchronous observers, modules composed with a program for static verification, which are also runnable specifications suitable for runtime verification, though this use is rarely explored. We present a technique for compiling the synchronous fragment of STL (SSTL) into synchronous observers in the dataflow language Lustre. Unlike previous work, we allow arbitrary nesting of bounded SSTL properties via modular compilation, and admit a globally unbounded outer operator for online monitoring; the resulting observers serve both runtime verification and, as a by-product, static verification with the Kind2 model checker. We further contribute an interactive visualiser that renders a property's three-valued verdict over an editable trace, and evaluate on two case studies from the literature: a spring-mass system and a car-following cruise controller.

0.23

On the monitorability of linear-time timed logics

cs.LO ·2026-11-18 ·Mouloud Amara, Mohammed Aristide Foughali, Giovanni Bernardi, Adrian Francalanza, Nicanora Ordoño Wallig
theory similarity 0.70
Abstract

In [10], we solved the monitorability problem for Tlin , a new expressive (linear-time) timed mu-calculus that we proposed. We showed that Tlin is strictly more expressive than MTL, the de facto timed extension of the well-known LTL. Moreover, we identified MTlin , the largest monitorable fragment of Tlin. The maximality of MTlin was proven modulo an expressive monitoring framework called Mon, yet under the assumption of reactivity. Our work in [10] was the first to solve the monitorability problem for such an expressive timed logic, and its theoretical results were accompanied with compilers (i) from MTL to Tlin and (ii) from Tlin formulae to monitors. This paper is an extension of [10] with the following new contributions. First, we generalise the maximality results to arbitrary monitors, which include both reactive and non-reactive monitors. Second, we extend the expressiveness results of Tlin . We completely revise the embedding of MTL into Tlin : we show that the syntax of MTL given in [10] was incomplete, and provide a new compiler from MTL, under its standard syntax with the strict Until operator and negation over arbitrary formulae, into Tlin . In passing, we demonstrate that Tlin is closed under complement and provide a fully syntactic complementation procedure. Moreover, we prove that Tlin is strictly more expressive than TPTL, a popular timed logic more expressive than MTL, and develop an automatic embedding from TPTL to Tlin . This gives Tlin and the machinery around it the power of a unified framework to reason on the monitorability of linear-time timed logics. Accordingly, we identify important monitorable fragments for both MTL and TPTL.

0.17

TLA-Verus: Generating and Solving Temporal Proof Obligations with LLM Agents

cs.LG ·2026-10-10 ·Kseniia Strelbytska, Balázs Szilágyi, Anna Mészáros, Ferenc Huszár
theory similarity 0.68
Abstract

The TLA+ (temporal logic of actions) formal specification toolkit has seen widespread adoption in modeling modern distributed software systems including databases, storage systems, ledgers and coordination protocols. This popularity is despite its two significant limitations for software verification: Firstly, TLA+ offers no way to detect drift between software implementation and mathematical specification; secondly, TLC and TLAPS cannot provide satisfactory proofs of arbitrary temporal logic properties. We address the second limitation and take a first step towards the first by translating TLA+ specifications into Verus, an auto-active verifier built for Rust, via both a deterministic transpiler and an agentic translator. We demonstrate that our LLM-based pipeline is able to generate proof obligations from TLA+ specifications at scale, and to produce fully machine checkable proofs of both safety and liveness properties. Since temporal logic reasoning in Verus is a largely new task for LLMs, our work yields a valuable evaluation dataset, which we use to map out current generation model capabilities in Verus theorem proving.

0.35

On Synthesis of Metric Interval Temporal Logics

cs.LO cs.AI ·2026-09-01 ·Hsi-Ming Ho, Shankaranarayanan Krishna, Khushraj Madnani
published similarity 0.68
Abstract · To appear at RTSS 2026

Automated mining of formal specifications is vital for verifying real-time systems. However, existing passive learning approaches remain restricted to deterministic specifications or limited fragments of Timed Regular Expressions (TRE). To our knowledge, this paper presents the first framework to tackle \emph{precise} passive learning for an expressive timed logic, \emph{Metric Interval Temporal Logic} (MITL) without relying on predefined templates or restricted logic fragments. Our approach formally reduces the timed learning problem into a scalable untimed one. By identifying quantitative timing differences between positive and negative traces, we synthesise precise timed constraints and inject them as new Boolean atomic propositions. This embeds timing into the alphabet, delegating the complex formula evaluation to highly optimised, off-the-shelf untimed LTL tools. Crucially, our framework is complete, guaranteeing a separating specification can always be found. We evaluate our implementation across several benchmarks, demonstrating the effectiveness of our approach.

0.25