The Limit of Recursion in State-based Systems
Bahareh Afshari Giacomo Barlucchi Graham E. Leigh · 2025
Read The Limit of Recursion in State-based Systems by Bahareh Afshari Giacomo Barlucchi Graham E. Leigh (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-2511-02594.txt.
Introduction
Bahareh Afshari, Giacomo Barlucchi, and Graham Leigh bound how long a certain kind of logical recursion can run before it settles. In the modal mu-calculus, formulas can define functions by least fixed points, and the closure ordinal counts the iterations needed to reach that fixed point. The authors prove that across all countable structures, functions definable in the alternation-free fragment always settle in strictly fewer than omega-squared iterations, where omega is the first infinite ordinal.
The result corrects and extends an earlier claim by two of the authors. The proof revives Kozen's well-annotations, a bookkeeping device from the finite model theory of the mu-calculus, in a conservative form that guarantees minimal annotations. Parts of the structure then locally determine the closure ordinal, and a direct pumping argument rules out any closure ordinal between omega-squared and the limit of countability.
Catalog record
| CREATOR | Bahareh Afshari Giacomo Barlucchi Graham E. Leigh |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 44 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-02594
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The Limit of Recursion in State-based Systems Thanks: This work was supported by the Knut and Alice Wallenberg Foundation [2020.0199], Swedish Research Council [2017-05111] and Dutch Research Council [OCENW.M20.048] Affiliation: Department of Philosophy, Linguistics and Theory of Science University of Gothenburg, Gothenburg, Sweden Bahareh Afshari Giacomo Barlucchi Graham E. Leigh Abstract We prove that ω 2 \omega^{2} strictly bounds the iterations required for modal definable functions to reach a fixed point across all countable structures. The result corrects and extends the previously claimed result by the first and third authors on closure ordinals of the alternation-free μ \mu -calculus in [ 4 ] . The new approach sees a reincarnation of Kozen’s well-annotations, devised for showing the finite model property for the modal μ \mu -calculus. We develop a theory of ‘conservative’ well-annotations where minimality of annotations is guaranteed, and isolate parts of the structure that locally determine the closure ordinal of relevant formulas. This adoption of well-annotations enables a direct and clear pumping process that rules out closure ordinals between ω 2 \omega^{2} and the limit of countability. 1 Introduction State-based systems and processes lay at the heart of computer science. Abstractly, they are no more than directed graphs, also known as Kripke frames, with states as vertices and state transitions as edges. Taking a transition from one state to another can model a step in computation and, doing so recursively, singles out computation paths through the system. To specify and verify properties of computation, in a fully abstract manner, temporal logics offer an elegant framework. Syntactically simple and algorithmically rich, temporal logics have been heavily studied. Amongst them the modal \mu -calculus holds a special place, providing a level of abstraction that is mathematically appealing while computationally well-behaved. This logic not only subsumes well known temporal logics (LTL, CTL, PDL, as well as extensions such as \mu LTL and CTL*), it can also be enriched to capture, for example, probabilistic properties [ 6 , 22 , 25 ] , hyperproperties [ 15 ] , higher-dimensional properties [ 29 ] (see also [ 21 ] ), and properties of higher-order recursive schemes [ 28 , 5 ] . In other words, \mu -calculus is a cornerstone in the mosaic of logics in computer science. Modal \mu -calculus is the extension of basic modal logic with least ( \mu ) and greatest ( \nu ) fixed point operators. Over a Kripke frame \mathcal{S} , the formula \mu x\,\varphi(x) is interpreted as the least fixed point of the induced monotone function f\colon U\mapsto\varphi(U) which maps a set of states U (in \mathcal{S} ) to the denotation of \varphi(x) modulo interpretation of x as U . This fixed point can be obtained as the limit of transfinite iterations of f . Starting with the empty set, applications of f give rise to an increasing sequence of sets of states, \emptyset\subseteq f(\emptyset)\subseteq f(f(\emptyset))\subseteq\cdots\subseteq f^{\alpha}(\emptyset)\subseteq f^{\alpha+1}(\emptyset)\subseteq\cdots which necessarily stabilises at some ordinal: f^{\kappa+1}(\emptyset)=f^{\kappa}(\emptyset) . The least such \kappa is the closure ordinal of f in \mathcal{S} . One way to define a notion of closure ordinal for a formula \mu x\,\varphi is as the supremum of closure ordinals of the induced function across all frames. In this paper we study closure ordinals of the \Sigma -fragment: formulas generated from closed \mu -calculus formulas and variables through the logical and modal operators, and the least fixed point operator \mu . From an algebraic perspective the fragment corresponds to functions definable in the modal algebra with (definable) parameters. A more general class, amounting to the full calculus, is to admit arbitrary definable functions, including those defined through co-recursion. There are several problems concerning closure ordinals which, to date, have only partial solutions. As there are countably many formulas of \mu -calculus there are countable ordinals that are not closure ordinals. So, which ordinals are closure ordinals? Aside from existence is the question of decidability : Is there an algorithm that decides whether any given formula has a closure ordinal? And not least is the question of limitedness : Can a non-trivial limit on closure ordinals be determined? 1.1 Related work Closure ordinals have been considered only by a handful of authors. Most notable is the Czarnecki formulas [ 7 ] , simple formulas in the \Sigma -fragment demonstrating that every ordinal below \omega^{2} is a closure ordinal. Czarnecki’s formulas indicate a connection between syntactic and semantic complexity that was generalised in [ 4 ] : consider formulas of the form \mu x\,\varphi with \varphi given by \displaystyle\varphi=(p_{1}\land\mathop{\square}q_{1}\land\bigcirc_{1}x)\lor(p_{2}\land\mathop{\square}q_{2}\land\bigcirc_{2}x)\lor\cdots\lor(p_{n}\land\mathop{\square}q_{n}\land\bigcirc_{n}x)\lor\mathop{\square}\bot where p_{i} and q_{i} are conjunctions of literals and \bigcirc_{i}\in\{\,\mathop{\diamondsuit},\mathop{\square}\,\} for each i . It is not difficult to prove that if such a formula has a closure ordinal \alpha , then \alpha<\omega.(n+1) . In [ 4 ] , the authors also provide a tableaux-based characterisation for the closure ordinals of the alternation-free \mu -calculus. In [ 18 ] , Kretz proves that every valid \Sigma_{1} -formula in the one-variable fragment, which includes any valid formula of the form above, has finite closure ordinal. Fontaine [ 10 ] (see also [ 11 ] ) carries out a study of closure ordinals of the continuous \mu -calculus, that is the fragment constituting formulas \mu x\,\varphi(x) where \varphi(x) is continuous with respect to x in the Scott topology on the powerset algebra. It is shown the \{\mathop{\square},\nu\} -free fragment of \mu -calculus characterises the continuous \mu -calculus establishing that closure ordinals are obtained in at most \omega iterations. Fontaine and Venema provide syntactic characterisations of several other semantic properties in [ 12 ] . Gouveia and Santocanale [ 13 ] study \kappa -continuity for \kappa an infinite (regular) cardinal, and prove a generalisation of the aforementioned results regarding existence: any ordinal obtainable from 0 , 1 , \omega , and \omega_{1} (least uncountable ordinal) by the binary ordinal sum operation is the closure ordinal of a \mu -calculus formula. One may argue that the concept of closure ordinal and questions posed about it stand somewhat remote to other investigations concerning \mu -calculus. But there is strong evidence that this not so. One intriguing connection, pointed out by Skrzypczak [ 31 ] , is to the descriptive complexity of Büchi languages. Each Büchi automaton can be associated a rank below \omega_{1} , measuring the complexity of the automaton against input trees. It is shown that the rank of an automaton \mathcal{B} is strictly below \omega_{1} if and only if the language of \mathcal{B} is Borel, and strictly below \omega^{2} if and only if the language is weak monadic second order definable. Skrzypczak proposes that the pumping arguments central to deducing bounds on closure ordinals may be used to tackle questions of definability (and decidability) of non-deterministic languages, the so-called gap properties for Büchi languages (see e.g. [ 30 , 27 ] ). Milanese [ 23 ] studies closure ordinals over bidirectional models and shows that every ordinal below \omega^{\omega} is a closure ordinal (see also [ 24 ] ). This result was observed independently in [ 2 ] as part of a study of \omega -branching proof systems for the two-way \mu -calculus. Again, such results add weight to the claim that closure ordinals are entwined in many topics concerning \mu -calculi.