A Logic for Fresh Labelled Transition Systems
Mohamed H. Bandukara, Nikos Tzevelekos · 2025
Read A Logic for Fresh Labelled Transition Systems by Mohamed H. Bandukara, Nikos Tzevelekos (2025) 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-2506-14538.txt.
Introduction
Mohamed Bandukara and Nikos Tzevelekos build a logic for machines that mint fresh data, in a 2025 paper. Some systems handle values that must never repeat, like new keys or session names. Their automata track the history of seen values in registers and can demand that the next input be genuinely new.
The authors extend a classic property language with recursion so it fits these history-aware systems. The logic can state rich claims, such as the existence of an endless path of all-distinct values, or a short path that breaks a safety rule. Checking a system against such claims reduces to solving a parity game, and set theory for named objects caps the cost at one exponential level. The work gives fresh-data systems a formal inspection language.
Catalog record
| CREATOR | Mohamed H. Bandukara, Nikos Tzevelekos |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 157 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-14538
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Logic for Fresh Labelled Transition Systems Mohamed H. Bandukara, Nikos Tzevelekos Abstract We introduce a Hennessy-Milner logic with recursion for Fresh Labelled Transition Systems (FLTSs). These are nominal labelled transition systems which keep track of the history, i.e. of data values seen so far, and can capture fresh data generation. In particular, FLTSs generalise the computations of Fresh-Register Automata, which in turn are one of the simplest classes of history-dependent automata operating on infinite input alphabets. Each automaton comes equipped with a finite set of registers where it can store data values and compare them with others from the input. In addition, the automaton can accept an input just if it be fresh: not seen in the computation before. The logic we introduce can express a variety of properties, such as the existence of an infinite path of distinct data values or the existence of a finite path where some taint property is violated. We study the model checking problem and its complexity via reduction to parity games and, using nominal sets techniques, provide an exponential upper bound for it. Queen Mary University of London, United [email protected] by EPSRC DTP EP/R513106/1. Queen Mary University of London, United [email protected][orcid] keywords Nominal Transition Systems with Fresh Data, Hennessy-Milner Logic, Modal Mu-Calculus, Nominal Sets, Parity Games † † runningauthor: M. H. Bandukara and N. Tzevelekos 1 Introduction Nominal Labelled Transition Systems (LTSs) can capture computational scenarios which require unbounded sets of data values [ 4 ] . In the most elementary case, data values are just names , that is, atomic identifiers that can only be compared for equality. Nominal LTSs can be used, for example, for modelling mobile processes [ 35 ] and computation with variables [ 23 , 20 ] , and for verifying XML query languages [ 37 ] . A particularly popular class of nominal LTSs are the ones generated by computations of “regular” automata over infinite alphabets, such as register automata [ 23 ] and the (largely) equivalent nominal automata [ 4 ] . A register automaton is equipped with a finite set of states, and hence the nod to regularity, but also a finite set of registers where it can store data values and compare them with, and possibly update them with, data values from the input. This design allows register automata to capture languages over infinite alphabets even though their specification is finite. Fresh-Register Automata (FRAs) [ 40 ] expand on this design by having the option of allowing the automaton to accept a name just if it is globally fresh, that is, it has not appeared so far in the input. FRAs can be used to capture computational models that use names and name generation, e.g. (finitary) \pi -calculus processes [ 40 , 2 ] or ML-like programs with mutable references [ 32 ] . They have been applied to program verification and system modelling, leading to verification tools [ 29 , 32 , 19 ] and model learning techniques [ 5 , 1 ] . Verification of FRAs has mainly focussed on bisimulation equivalence [ 40 , 30 , 31 ] . In this work we are interested in furthering formal verification for nominal computation, with an interest on FRAs and more generally history-dependent computation, in the direction of modal logics. Hennessy-Milner Logic (HML) is a modal behavioural logic that captures branching-time properties of labelled transition systems. It was initially introduced in 1980 by Hennessy and Milner [ 21 ] as an alternative exposition of observational equivalence [ 7 ] . Observational equivalence has a focus on testing whether two systems can simulate each other in a step-by-step manner, whereas HML logic focuses on the expressiveness of a single system. Under certain assumptions, two processes are equivalent just if they satisfy the same HML formulas [ 22 ] . The extension of HML with recursion, called modal \mu -calculus, was introduced by Kozen [ 27 ] . Here, we study a nominal extension thereof, where modalities are allowed to include names and where quantifications over some/all names and some/all fresh names are catered for. More specifically, our contributions include: • We introduce the notion of fresh LTS (FLTS) , which extends nominal LTS with history dependence. • We introduce a fresh HML with recursion , called \mu FHML, which allows us to express recursive branching-time properties involving names and name-freshness. • We study the model checking problem for \mu FHML formulas on FLTSs. This leads us to developing parity games for \mu FHML and, through a series of reductions and using nominal techniques, devising a decision procedure for them. • We provide (exponential) upper bound calculations for \mu FHML parity games and \mu FHML model checking, in the latter case both on general FLTSs and on FRAs. Related work HML for the \pi -calculus was first examined in [ 28 ] . For properties involving paths of unbounded length, it is natural to examine recursive extensions thereof such as the modal \mu -calculus and variants thereof [ 7 ] . The logic we introduced is based on the \pi - \mu -calculus of Dam [ 11 ] and is related to the recent work on nominal \mu -calculi of Klin and collaborators [ 24 , 25 , 14 ] . The \pi - \mu -calculus [ 11 ] specifically targets \pi -calculus processes, but the syntax used for recursion is the same as ours. The study of a history-dependent nominal \mu -calculus in [ 14 ] is the work closest to ours. In a certain sense, our work continues and answers open problems from loc cit. in particular by operating on history-dependent LTSs (and FRAs) and accommodating a vectorial version of recursion. We also provide a more algorithmic view on model checking via parity games and produce complexity bounds. In the area of nominal techniques, the modal logics for nominal LTSs by Parrow et al. [ 34 ] can subsume our logic but do not allow for decidable model checking. Logics for variants of register automata have been widely studied, e.g. [ 38 , 13 , 17 ] . The main focus of those works is on decidability, e.g. by restricting the number of registers allowed. No such restrictions are imposed on our logic, which is undecidable for satisfiability but our focus is instead on model checking. There have also been a series of works on logics related to the \pi -calculus, e.g. [ 33 , 26 , 3 ] . Those works mainly study expressiveness and characterisation of variants of behavioural equivalence for \pi -calculus processes. Other related works, such as [ 10 , 6 ] , expand on the modal \mu -calculus and study model checking, and show it to be decidable for finitary \pi -calculus processes. 2 Nominal sets and fresh labelled transition systems (FLTSs) We start by briefly introducing the nominal sets framework, which will be the basis of much of this paper. Intuitively, nominal sets are sets where names are baked in from the outset. Let us fix \mathbb{A} to be a countably infinite set of names (or data values ) upon which nominal sets are built. A permutation \pi on \mathbb{A} (i.e. a bijection \pi:\mathbb{A}\to\mathbb{A} ) is