CS Paper Radar

On Synthesis of Metric Interval Temporal Logics

Hsi-Ming Ho, Shankaranarayanan Krishna, Khushraj Madnani

cs.LO cs.AI ·submitted 2026-09-01 10:30 UTC · v1
published

Abstract

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.

Comment
To appear at RTSS 2026

Closest papers

Nearest neighbours by meaning across the whole index.

MightyPPL : Towards model checking MTL

cs.LO ·2026-09-16 ·Hsi-Ming Ho, Shankara Narayanan Krishna, Khushraj Madnani, Rupak Majumdar, Paritosh Pandya
similarity 0.75
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

The Infinite, in Finite Time

cs.LO ·2026-08-24 ·Rayhana Amjad, Rob van Glabbeek, Liam O'Connor
publishedtheory similarity 0.68
Abstract · This paper contains the material of arXiv:2411.14581

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.

0.16

Mining DTA with SMT by Exploiting Simple Elementary Language and Timed Augmented Prefix Acceptor

cs.FL ·2026-09-15 ·Ziran Wang, Jie An, Naijun Zhan
hot direction similarity 0.67
Abstract

Timed automata, which extend finite state automata by introducing clock variables, serve as a popular formalism for specifying and analyzing the timed behaviors of real-time systems. Extracting the timed behaviors of a black-box, safety-critical system is crucial for designing and analyzing its real-time requirements, yet it remains challenging. In this paper, we address this problem by generating a deterministic timed automaton (DTA) consistent with a given set of system behaviors, comprising both positive and negative examples. To this end, we adapt the formalism of simple elementary languages (sEL) and introduce the timed augmented prefix tree acceptor (tAPTA). Our approach proceeds as follows: First, we preprocess samples by translating them into sEL, which discards redundancy and detects conflicts; then, we rewrite the resulting sELs in an incremental form and construct a tAPTA to further simplify the samples; finally, we encode the search for a DTA that accepts the simplified tAPTA as an SMT formula. We evaluate our approach on randomly generated benchmarks and a scheduling case study. The results demonstrate the effectiveness of our simplification method in reducing the size of the encoded SMT formula and the efficiency of our approach in mining a DTA.

0.29

Model Checking HyperRecHML is Decidable

cs.LO cs.FL ·2026-10-15 ·Elli Anastasiadi, Kim Guldstrand Larsen, Martin Zimmermann
similarity 0.66
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

Formal Explanations for Linear Temporal Logic over Finite Traces

cs.LO cs.AI ·2026-10-26 ·Valeria Fionda, Antonio Ielo, Francesco Ricca
theory similarity 0.65
Abstract

Linear Temporal Logic over Finite Traces (LTLf) is widely used in Artificial Intelligence to specify desired temporal behavior and determine whether finite traces satisfy or violate it. Explaining these outcomes is essential for debugging and trust. However, existing approaches typically capture either sufficient reasons or counterfactual causes, without clarifying their relationship. We introduce a native characterization of abductive (AXps) and contrastive (CXps) explanations directly over finite traces, based on locking and unlocking time-indexed events. We prove its equivalence to the classifier-based formulation, and show that CXps coincide with a recently proposed temporal causality semantics for LTLf. This characterization enables an efficient implementation based on the enumeration of minimal unsatisfiable cores and minimal correction sets of ASP programs. Experiments on real-world event logs demonstrate the effectiveness of the approach.

0.27

Compositional Automata Learning of Timed Synchronous Systems

cs.FL ·2026-10-15 ·Hanyue Chen, Chang Liu, Miaomiao Zhang
publishedbenchmarkcode/data similarity 0.63
Abstract · 32 pages, 26 figures, including appendices. Accepted at SETTA 2026. Code and data: https://github.com/zeno-98/NRTA_Learning

Active model learning is a crucial technique for automatically constructing formal models of black-box timed systems. However, existing learning approaches typically construct a single monolithic automaton for a timed system with multiple synchronous components, obscuring its component structure and hindering component-level analysis. We propose a compositional learning approach that constructs a deterministic real-time automaton (RTA) for each component with access only to the target system as a whole. Upon termination, the learned RTAs form a network that exhibits exactly the same timed behaviors as the target system. Within the respective resource limits, our implementation terminates successfully on 213 of the 240 (88.8%) randomly generated benchmark instances and all six adapted case-study benchmarks, and requires less learning time than monolithic approaches on some instances.

0.41

Active Learning of Temporal Specifications through Distinguishing Queries

cs.LO cs.AI ·2026-11-13 ·Rajarshi Roy, Xiaowei Huang
theory similarity 0.63
Abstract

Temporal specifications are essential for verification and monitoring, yet writing formulas that capture the intended behaviour is difficult. Active learning derives such specifications through interaction between a learner and a teacher, but remains underexplored for temporal logics. Existing approaches require the teacher to answer equivalence queries and to construct counterexamples, and they often rely on SAT-based learning procedures that restart the search after each new example. We present an active-learning framework for LTLf in which the teacher only labels traces and answers natural-language questions about the intended behaviour. The learner maintains an enumerated version space of candidate formulas, generates traces that distinguish candidates, and uses the teacher's hints to rank candidates or to restrict the search. We prove consistency with the observed examples, identification within bounded hypothesis classes with a bound on the number of queries, and a PAC guarantee for the final hypothesis. In experiments with a simulated teacher on 36 targets, including targets in four standard environments, the learner identifies every target when it compares all rivals, with fewer than seven queries beyond an initial sample of ten traces on average. Correct hints reduce the number of queries by up to 16% and the number of generated candidates by a fifth, and hints used for ranking never prevent identification, even when incorrect. Our enumeration-based version space is faster than the SAT-based approach of previous learners at every target size.

0.21

Reward Machines for Signal Temporal Logic

cs.AI cs.LGcs.RO ·2026-08-13 ·Alper Kamil Bozkurt, Shangtong Zhang, Yuichi Motai
similarity 0.63
Abstract

Signal temporal logic (STL) provides a formal language for specifying real-time properties of real-valued observations, along with a quantitative robustness score for monitoring satisfaction. Control synthesis from STL specifications is of interest since manual controller design becomes infeasible as real-world systems grow in complexity. Moreover, many modern autonomous and AI-enabled systems lack accurate and complete system models, which makes optimization-based synthesis approaches unsuitable and motivates learning-based control. Prior work uses STL robustness scores as rewards in reinforcement learning (RL) to obtain control policies satisfying given specifications; however, robustness depends on execution history, leading to intractable state space expansion for general long-horizon specifications with arbitrarily nested temporal operators. This work introduces a novel automata-based approach that provides an efficient memory mechanism and associated Markovian rewards suitable for RL frameworks. Our approach constructs a timed alternating automaton from the given STL specifications, augments the state space with automaton locations and clock valuations, and derives rewards from the automaton acceptance condition. We empirically demonstrate that our approach learns policies that achieve higher robustness scores and satisfaction rates than those learned by existing approaches using robustness-based rewards.

0.04