💻 computer science

Finite Convergence of the Modal Mu-Calculus on Almost-Periodic Words

This paper establishes that almost-periodic words are precisely the infinite words on which the modal mu-calculus enjoys finite convergence, thereby providing a complete characterization of this property and offering a new proof of Semenov's 1984 decidability result.

Original authors: Fabian Lehr, Florian Bruse

Published 2026-07-10

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Fabian Lehr, Florian Bruse

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are watching a never-ending movie reel, a story that plays on forever. In the world of computer logic, there's a special tool called the Modal µ-calculus. Think of it as a super-powered magnifying glass that lets you ask questions about this infinite movie: "Does this character eventually appear?" or "Will this scene repeat forever?"

To answer these questions, the logic uses a trick called a fixpoint. Imagine you are trying to find the end of a maze. You start at the entrance, take a step, check if you're there, and if not, you take another step. You keep doing this, unfolding the path one step at a time. In math, this is called an "unfolding." Usually, for an infinite movie, you might think you'd have to keep unfolding the path forever, never reaching a final answer.

But sometimes, the movie has a secret: no matter how long you watch, the path you are tracing actually stops changing after a certain number of steps. The logic "converges." It finds its answer in a finite number of steps, even though the movie itself never ends.

The Big Discovery
For a long time, researchers knew that if a movie repeats itself in a perfect, predictable loop (like a song on repeat), the logic always converges quickly. But they found some weird, non-repeating movies where the logic also converged. This left a huge question hanging: What exactly makes a movie allow the logic to stop unfolding?

In this paper, Fabian Lehr and Florian Bruse from TU Munich have solved this mystery. They proved that a movie (or "word," in math speak) allows the logic to converge if and only if it is almost-periodic.

What does "almost-periodic" mean? Imagine a pattern in the movie. If a specific scene (a "factor") appears, it either:

Shows up only a few times and then vanishes forever, OR
Shows up again and again, and you are guaranteed to see it again within a specific distance (say, every 50 minutes), even if it doesn't show up at exactly the 50-minute mark every time.

The authors show that if a movie follows these rules, the logic will always find its answer in a finite number of steps. If a movie doesn't follow these rules, the logic might get stuck unfolding forever.

What They Ruled Out
The paper is very clear about what doesn't work. They explicitly rule out the idea that you need a "finite bisimulation quotient" (a fancy way of saying the movie must look like a small, finite loop) for the logic to converge. In the past, people thought you needed the whole movie to be essentially a small, repeating loop to get a quick answer. This paper proves that wrong. You can have a movie that looks totally different at every moment (infinite complexity), yet the logic still converges, as long as the "almost-periodic" rules are followed.

How Sure Are They?
This isn't a guess, a simulation, or a "maybe." The authors have provided a mathematical proof. They didn't just test a few examples; they showed that for every almost-periodic word, the logic converges, and for every word that isn't almost-periodic, it doesn't. They also showed that this result re-proves a known fact about whether we can decide if a logic statement is true on these movies (a result originally found by Semenov in 1984), but they did it with a new, simpler, and more direct method.

The "Trick" They Used
To prove this, the authors used a clever analogy involving trivial automata. Think of these as tiny, simple robots that walk along the movie reel.

If the movie is "almost-periodic," these robots are guaranteed to either get stuck in a loop or stop walking after a certain number of steps. They can't wander off into infinity without a pattern.
The authors proved that if the robots stop wandering, the logic can also stop unfolding.
They did this by turning the robot's path into a regular expression (a mathematical recipe for patterns) and showing that on these special movies, the recipe can only produce a finite number of unique "stops."

The Takeaway
So, if you have an infinite story, you don't need it to be a boring, perfect loop to make sense of it with this logic. You just need it to be "almost-periodic"—where every scene either fades away or promises to return soon enough. This discovery gives us a complete map of exactly which infinite stories are "tame" enough for this powerful logic to solve, and which ones are too wild to ever finish checking.

Technical Summary: Finite Convergence of the Modal µ-Calculus on Almost-Periodic Words

Problem Statement
The paper addresses the question of finite convergence for the linear-time Modal µ-calculus ( $L_\mu$ ) on infinite words. A structure (specifically an infinite word) enjoys finite convergence if every formula in the $L_\mu$ is equivalent to a finite unfolding of its fixpoint definitions on that structure. While it is known that ultimately periodic words possess finite convergence, and that words with finite convergence must be almost-periodic, the exact characterization of the class of words exhibiting finite convergence remained open. Specifically, it was unknown whether all almost-periodic words possess finite convergence, or if there exist almost-periodic words where fixpoint definitions require infinite unfolding.

Methodology
The authors approach the problem by establishing an equivalence between finite convergence and the behavior of trivial automata (TrA) on infinite words. A word has finite convergence if and only if all trivial automata have bounded runs on that word (i.e., runs either terminate within a finite number of steps or run forever, without the termination bound depending on the specific run path in an unbounded manner).

To prove that almost-periodic words satisfy this condition, the paper employs a direct proof strategy involving the conversion of Non-deterministic Finite Automata with Regular Expressions ( $NFA_{reg}$ ) into equivalent regular expressions. The methodology relies on the following steps:

Reduction to Trivial Automata: The problem is reduced to showing that for any almost-periodic word $w$ , any trivial automaton $A$ has bounded runs on $w$ .
Automata Conversion: The authors utilize a standard conversion process (similar to state elimination) to transform an $NFA_{reg}$ into a regular expression. They introduce specific properties for the automata during this process: minimality, goodness (ensuring prefix-freeness and disjointness of transition languages), and simplicity relative to the word $w$ .
Preservation of Properties: The paper proves via Lemmas 12, 13, and 14 that the conversion operations (merging parallel edges and removing non-initial/non-final states) preserve minimality, goodness, and simplicity.
Combinatorial Argument: A key technical component is Lemma 7, which establishes that for an almost-periodic word $w$ and prefix-free finite languages $L, L'$ , the intersection $L^*L \cap F(w)$ (where $F(w)$ is the set of factors of $w$ ) is finite. This lemma is applied to the regular expression derived from the trivial automaton to demonstrate that the set of factors of $w$ accepted by the automaton is finite, thereby bounding the run length.

Key Contributions and Results

Characterization of Finite Convergence: The paper proves the converse of the known implication: A word has finite convergence if and only if it is almost-periodic. This provides a complete characterization of the class of words on which the $L_\mu$ collapses to its alternation-free fragment (in terms of finite approximations).
Bounded Runs on Almost-Periodic Words: The central result (Theorem 15) demonstrates that all trivial automata have bounded runs on almost-periodic words. This is achieved without relying on complex existing formulations but through a direct proof using basic tools.
Decidability Re-proof: The result re-proves Semenov's (1984) decidability result for the $L_\mu$ on effectively almost-periodic words. The paper notes that while the decidability was known, the direct proof provided here offers a clearer path to the result.
Normal Form for $\omega$ -Regular Expressions: The proof technique yields a new normal-form result (Remark 17). It shows that any $\omega$ -regular expression of the form $\sum r_i s_i^\omega$ can be rewritten into a form $r \Sigma^\omega$ that agrees with the original expression specifically on the set of almost-periodic words.

Significance and Claims
The paper claims to settle an open question left by previous work (specifically [8]) regarding the exact nature of words with finite convergence. The authors emphasize that their contribution is not merely a re-statement of existing decidability results but a direct characterization of the structural properties (almost-periodicity) that guarantee finite convergence.

The significance lies in:

Completeness: It closes the gap between necessary and sufficient conditions for finite convergence on infinite words.
Simplicity: The proof is presented as "relatively straightforward" and uses "very basic tools," contrasting with previous formulations that were described as "unwieldy" or insufficient for direct derivation.
Structural Insight: It links the logical property of finite convergence directly to the combinatorial property of almost-periodicity, reinforcing the relationship between automata behavior and word structure.

The paper concludes modestly, noting that while the results are established for infinite words, future research directions include extending these findings to bi-infinite words and infinite trees, where the behavior of closure ordinals may differ due to branching structures.

More like this