Verifying First-Order Temporal Properties of Infinite-State Systems via Timers and Rankings

Raz Lotan, Neta Elad, Oded Padon, Sharon Shoham · 2026

Read Verifying First-Order Temporal Properties of Infinite-State Systems via Timers and Rankings by Raz Lotan, Neta Elad, Oded Padon, Sharon Shoham (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-2601-13325.txt.

Introduction

Raz Lotan, Neta Elad, Oded Padon, and Sharon Shoham verify time traits of systems with no bound on state count. Their frame is deductive, built on well founded ranks. A rank map that must fall at each step can prove that a run ends or holds a trait. Check tasks are passed to SMT solvers, tools that test if a logic claim can hold.

Their new step is a cut from trait checks to end checks. A fresh tool of timers joins the ranks to make that cut work. With it any first order time trait can be recast as an end task. For proof tool teams, one strong end engine can then serve all traits.

Catalog record

CREATORRaz Lotan, Neta Elad, Oded Padon, Sharon Shoham
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE63 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-13325

Browse the full library · About the Tower of Babel

Full text

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

Verifying First-Order Temporal Properties of Infinite-State Systems via Timers and Rankings Raz Lotan, Neta Elad, Oded Padon, Sharon Shoham Abstract We present a unified deductive verification framework for first-order temporal properties based on well-founded rankings, where verification conditions are discharged using SMT solvers. To that end, we introduce a novel reduction from verification of arbitrary temporal properties to verification of termination. Our reduction augments the system with prophecy timer variables that predict the number of steps along a trace until the next time certain temporal formulas, including the negated property, hold. In contrast to standard tableaux-based reductions, which reduce the problem to fair termination, our reduction does not introduce fairness assumptions. To verify termination of the augmented system, we follow the traditional approach of assigning each state a rank from a well-founded set and showing that the rank decreases in every transition. We leverage the recently proposed formalism of implicit rankings to express and automatically verify the decrease of rank using SMT solvers, even when the rank is not expressible in first-order logic. We extend implicit rankings from finite to infinite domains, enabling verification of more general systems and making them applicable to the augmented systems generated by our reduction, which allows us to exploit the decrease of timers in termination proofs. We evaluate our technique on a range of temporal verification tasks from previous works, giving simple, intuitive proofs for them within our framework. 1 Introduction Several recent works [ 32 , 33 , 30 , 29 , 41 ] have dealt with verifying temporal properties of transition systems specified in first-order logic. Temporal properties of such systems are naturally specified in First-Order Linear Temporal Logic (FO-LTL). FO-LTL extends standard first-order logic with temporal operators that reason about the behavior of a transition system over time, and allows to specify both safety properties and liveness properties with various fairness assumptions. Existing approaches for the verification of liveness properties of transition systems given in first-order logic can roughly be divided to those employing a liveness-to-safety reduction or those that use well-founded rankings. The liveness-to-safety reduction of [ 32 ] can target any FO-LTL property and is quite powerful when augmented with temporal prophecy [ 33 , 23 ] . However, verifying the safety of the resulting system is complicated since it requires reasoning about a monitored copy of the system that tracks repeated states modulo a dynamic finite abstraction. In contrast, well-founded rankings operate at the level of the original system and are therefore more intuitive to use, but current works in this setting [ 30 , 29 , 41 ] only target specific liveness properties and are limited in the kinds of ranking arguments they can capture. Our goal is to design a verification framework for first-order transition systems that is both intuitive for users and applicable to any temporal property. To this end, we combine two key ideas. First, to obtain a unified approach, we base our framework on a novel reduction from the verification of FO-LTL properties to verification of termination. Our reduction is sound and complete and produces a transition system that is easy to reason about since it is an augmentation of the original transition system with prophecy variables that track violations of the property. Then, verifying termination of the resulting transition system is equivalent to showing that there is no violating trace of the original system. Second, for verifying termination, we adopt and extend the notion of implicit rankings from [ 29 ] , allowing the user to encode a range of well-founded rankings that may involve the prophecy variables introduced by the reduction. Implicit rankings are provided by the user and verified automatically by an SMT solver. Our reduction to termination takes a transition system T and a temporal property \varphi and reduces the verification of T\models\varphi to verifying termination of an augmented transition system obtained by a synchronous composition of T with T_{\neg\varphi} , the timer transition system of \neg\varphi . The infinite traces of T_{\neg\varphi} are exactly all the infinite traces that satisfy \neg\varphi . The timer transition system resembles standard tableaux constructions, except that it does not have fairness assumptions. As a result, we get a reduction to verification of termination instead of fair termination, which is easier to handle. To construct T_{\neg\varphi} we introduce for each subformula \psi of \neg\varphi a timer variable t_{\psi} that takes values in \mathbb{N}\cup\{\infty\} , and predicts the number of transitions until \psi is next satisfied, or \infty if there is no such number. This behavior is enforced by the transitions of T_{\neg\varphi} . The initial states of T_{\neg\varphi} are then defined as those where t_{\neg\varphi}=0 which means that all of their outgoing infinite traces satisfy \neg\varphi . It follows that the composition T\times T_{\neg\varphi} is an augmentation of T with timers that contains all infinite traces of T that satisfy \neg\varphi . Thus, T\models\varphi holds if and only if the augmented transition system obtained by the composition has no infinite traces, that is, terminates. To show termination of the transition systems produced by the reduction we employ the method of implicit rankings [ 29 ] . Implicit rankings are first-order formulas that capture the decrease of some ranking function between two states, without defining the function explicitly. Implicit rankings are useful for reasoning about ranking functions that are not easily expressible in first-order logic, such as functions that involve unbounded set cardinalities or summations. The constructors of implicit rankings defined in [ 29 ] provide an expressive language for well-founded rankings that can be reasoned about in first-order logic, using SMT solvers, but these are defined only for systems that operate over finite, albeit unbounded, domains. In particular, they cannot leverage timers in rankings, even though their domain is well-founded. To mitigate this, we extend the formalism of implicit rankings to be able to soundly reason over systems with infinite domains. We do so by introducing an explicit soundness condition that allows us, for example, to require that some dynamically updated set is finite in all reachable states or that some relation is well-founded. We further generalize the constructors of [ 29 ] to this setting. In particular, this allows us to use the decrease of timers in the ranking used to prove termination of the augmented system produced by our reduction. Importantly, the use of timers in the termination proof relies on their intuitive meaning, and does not require understanding the construction of the augmented system. We implement our reduction and the constructions of implicit rankings in a deductive verification tool that takes as input a transition system specification and a first-order temporal property, as well as an implicit ranking (given by a composition of constructors) and supporting invariants, which may refer to the timer variables. Our tool uses these ingredients to generate verification conditions that capture the decrease of rank encoded by the implicit rankings in every reachable transition of the system augmented with timers. It then verifies that the system satisfies the property by using an SMT solver to automatically discharge the verification conditions. We evaluate our tool by verifying a set of challenging examples from previous works which include liveness properties of distributed protocols and termination of programs. We

Read the complete text