CS Paper Radar

New Translations From LTL with Past to LDBA and DPA

David Lidell, Nir Piterman

cs.FL ·submitted 2026-10-11 09:28 UTC · v1
published

Abstract

We present asymptotically optimal translations from linear temporal logic with past to limit-deterministic Buchi automata and onwards to deterministic parity automata. In contrast to previously known translations involving past, the ones presented here are incremental: states and transitions can be constructed as needed on-the-fly, and they do not involve backtracking in order to correct for temporal inconsistencies. The past is naturally encoded in the formula by alternating between weak and strong versions of past operators. To handle the difficulties that arise from the alternation of least and greatest fix-point operators (such as between the "until" operator and its weak counterpart), we rewrite the given formula based on the infinitary behavior of a given word with respect to subformulae rooted with such operators.

Comment
In Proceedings GandALF 2026, arXiv:2610.08898
Journal ref
EPTCS 454, 2026, pp. 130-147
DOI
10.4204/EPTCS.454.10

Closest papers

Nearest neighbours by meaning across the whole index.

A note on the reduction from LTLf to LTL

cs.FL cs.LO ·2026-08-31 ·Alexandre Duret-Lutz
similarity 0.67
Abstract

LTLf, a finite word variant of LTL, can be reduced to LTL by introducing a new atomic proposition indicating the prefix of the infinite words that correspond to the finite words that the original LTLf formula was considering. Such a reduction was originally proposed by De Giacomo and Vardi (IJCAI'13). However, while any LTL formula reduced from LTLf describes an obligation property in the hierarchy of Manna and Pnueli (PODC'90), the aforementioned reduction does not provide an LTL formula that belongs to the syntactic obligation fragment of LTL. This note shows how the reduction was fixed in Spot in order to ensure that the resulting LTL formula is always a syntactic obligation. Doing so allows algorithms specialized to syntactic obligation to be used on LTLf formulas. For instance, in previous work (CAV'26) we described a specialized translation from syntactic obligations to minimal, weak, deterministic Büchi automata that would not be usable with the original reduction.

0.23

The Infinite, in Finite Time

cs.LO ·2026-08-24 ·Rayhana Amjad, Rob van Glabbeek, Liam O'Connor
publishedtheory similarity 0.61
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

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.60
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

Operator Precedence Tree Automata

cs.FL ·2026-11-17 ·Matteo Pradella
similarity 0.57
Abstract

Operator-precedence tree automata (OPTA) separate the construction of a word's syntactic structure from its recognition: an operator-precedence (OP) matrix determines a canonical tree, which is evaluated by a finite bottom-up automaton with regular horizontal transition languages. OPTA define exactly the operator-precedence languages. For a fixed matrix and language, a tree-context congruence yields an effectively constructible canonical complete deterministic exact recognizer, minimal in the number of vertical states and unique up to isomorphism. For acyclic OP matrices, we characterize balanced non-counting by aperiodicity of the context transition monoid of the canonical minimal ranked tree recognizer. Combined with existing characterizations of OP languages, this gives an equivalence with first-order definability over OP words, definability in Precedence-Oriented Temporal Logic (POTL), and star-free operator-precedence expressions for acyclic matrices.

0.32

Model Checking HyperRecHML is Decidable

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

MightyPPL : Towards model checking MTL

cs.LO ·2026-09-16 ·Hsi-Ming Ho, Shankara Narayanan Krishna, Khushraj Madnani, Rupak Majumdar, Paritosh Pandya
similarity 0.55
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 Gentzen-style monadic translation of Gödel's System T revisited

cs.LO ·2026-10-04 ·Chuangjie Xu
theory similarity 0.55
Abstract · Extended version of "A Gentzen-Style Monadic Translation of Gödel's System T" (FSCD 2020), DOI: 10.4230/LIPIcs.FSCD.2020.25

We revisit the Gentzen-style monadic translation of Gödel's System T. The translation is parametrized by a nucleus, a monad-like structure that need not satisfy the monad laws. A fundamental theorem of logical relations provides a uniform correctness argument for its instances. By choosing suitable nuclei, we obtain majorants, moduli of pointwise and uniform continuity, internal dialogue trees, and functionals of general bar recursion, all represented by terms of T. The internal dialogue-tree application gives a simpler construction, with correctness established directly using Church-encoded terms. We also extend the translation and its fundamental theorem to sums and finite lists. Finally, we develop the Kuroda-style translation and its continuity instance, comparing the moduli obtained with those of the Gentzen-style translation.

0.20

Undecidability of Reachability for Constraint Automata

cs.FL ·2026-10-11 ·Jakub Michaliszyn
theoryhot direction similarity 0.55
Abstract

We prove that reachability for constraint automata over finite binary words is undecidable. Eight registers suffice, with conjunctive guards using only equality, proper prefix, proper suffix, and infix incomparability, without word constants or concatenation. Finite-run nonemptiness, Buechi nonemptiness, and bounded Buechi nonemptiness are undecidable as consequences. For Boolean guards over equality, prefix, suffix, and prefix and suffix incomparability, Buechi nonemptiness is PSPACE-complete with arbitrarily many registers and word constants. The upper bound also allows positive infix atoms and yields PSPACE-completeness of prefix--suffix LTL satisfiability.

0.31