💻 computer science

Expregular functions

This paper introduces "expregular functions," a robust class of string-to-string functions with exponential growth defined by three equivalent models (MSO set interpretations, yield-Hennie machines, and Ariadne transducers), and proves their equivalence to establish that MSO set interpretations are regularity reflecting, thereby resolving a major conjecture regarding the decidable MSO theory of automatic $\omega$ -words.

Original authors: Thomas Colcombet, Nathan Lhote, Pierre Ohlmann

Published 2026-05-08

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Thomas Colcombet, Nathan Lhote, Pierre Ohlmann

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 have a machine that reads a string of letters (like a word) and spits out a new, longer string. In computer science, we love to categorize these machines based on how much they can "stretch" the input.

Regular Machines: These are like a photocopier. If you feed them a 10-page document, they might print 10 or 20 pages, but they never print 1,000. The output grows linearly with the input.
Polyregular Machines: These are like a printer that can make multiple copies of every page. If you feed it a 10-page document, it might print 100 pages (10 squared). The growth is polynomial.
Expregular Machines (The Star of This Paper): These are the "super-stretchers." If you feed them a 10-page document, they might print 1,024 pages ( $2^{10}$ ). The output grows exponentially.

This paper, titled "Expregular functions," introduces a new, robust class of these "super-stretchers" and proves that despite their massive output, they are still well-behaved and predictable. The authors, Thomas Colcombet, Nathan Lhote, and Pierre Ohlmann, propose three different ways to describe these machines and prove they are all secretly the same thing.

Here is the breakdown using everyday analogies:

1. The Three Faces of the Same Machine

The authors argue that "Expregular functions" are the natural, "finite-state" version of exponential growth. To prove this, they show three different models that do the exact same job:

Face A: The MSO Set Interpreter (The Architect's Blueprint)
Imagine you have a blueprint (a logical formula) that describes how to build a new city based on an old one. Instead of just moving existing buildings, this blueprint says: "For every house in the old city, imagine every possible way you could paint it, and build a new house for each of those color combinations."
Because you are exploring every combination, the new city explodes in size (exponential growth). The paper proves that even though this blueprint is complex, it follows strict rules.
Face B: The Yield-Hennie Machine (The Forking Factory)
Imagine a single worker on an assembly line (a standard computer). Now, imagine that whenever the worker hits a specific button, they can clone themselves.
- The original worker keeps going.
- The clone starts a new task.
- The clones can clone themselves again.
  However, there is a rule: The Bounded Visit Rule. No matter how many clones exist, no single clone can look at the same spot on the assembly line more than a fixed number of times (say, 5 times).
  When all the clones finish their tiny tasks, they shout out a single letter. The final product is the "yield" (the collection of all letters shouted) from the bottom of this tree of clones.
  The paper proves that the "Blueprint" (Face A) can be perfectly translated into this "Forking Factory" (Face B).
Face C: The Ariadne Transducer (The Labyrinth Walker with a Memory Stack)
Imagine a robot walking through a maze (the input string). It has a backpack (a stack) where it writes down its history.
- It can push a new note into the backpack (move forward).
- It can pop a note out (go back).
- The Twist: Unlike a normal robot, this one can peek at any note in its backpack, not just the top one. This helps it remember complex patterns.
- The Twist 2: It has a "bouncing" rule. If it tries to go back to a spot it's already visited too many times, it must change its internal state (like putting on a different hat) to ensure it doesn't get stuck in an infinite loop.
  The paper proves that the "Forking Factory" (Face B) can be simulated by this "Labyrinth Walker" (Face C), and vice versa.

2. The Big Discovery: "Regularity Reflection"

The most important result in the paper is a property called Regularity Reflection.

In simple terms, this means: "If you take the output of an Expregular machine and ask a simple question about it (like 'Does this output contain the word 'apple'?'), you can translate that question back to the input and ask it there instead."

Why is this a big deal?
Usually, when you have a machine that explodes the size of data (exponential growth), it becomes impossible to predict or analyze. It's like trying to find a needle in a haystack that keeps growing.
The authors prove that for Expregular machines, the "haystack" is actually structured. If the output is "regular" (predictable), the input was also "regular."
- The Consequence: This solves a decades-old puzzle about "Automatic $\omega$ -words" (infinite patterns). The paper proves that the logic used to describe these infinite patterns is always decidable (you can always write a program to answer questions about them).

3. How They Proved It (The "Funnel" Trick)

The hardest part of the paper is translating the "Blueprint" (Face A) into the "Forking Factory" (Face B).

The authors realized that to manage the exponential explosion, you need to track intervals of the output. Imagine the output is a long line of dominoes.

They invented a concept called "Funnels." A funnel is a way of narrowing down a huge chunk of the output into a smaller, manageable piece.
They proved that no matter how complex the blueprint is, you can always break the output down into these funnels in a way that respects the "Bounded Visit" rule.
They used a clever encoding system (like a tiling puzzle) to represent these funnels on the machine's tape, ensuring the machine never gets lost or visits a spot too many times.

Summary

This paper introduces Expregular functions, a new class of string-to-string machines that can double, triple, or exponentially expand data.

They show that three very different ways of describing these machines (Logic, Forking Processes, and Stack-based Walkers) are actually equivalent.
They prove that despite the massive growth, these machines are "well-behaved" (Regularity Reflection).
This result settles a major conjecture, proving that certain complex infinite patterns have predictable, solvable logic.

In short: The authors found a way to tame the "exponential monster" of computer science, showing that even when data explodes in size, it still follows a strict, understandable set of rules.

Technical Summary: Expregular Functions

1. Problem Statement and Context

The paper addresses the characterization of string-to-string functions with exponential growth. While the class of regular functions (linear growth) and polyregular functions (polynomial growth) are well-understood, robust, and admit multiple equivalent characterizations (logical, automata-theoretic, and transducer-based), the landscape for functions with super-polynomial growth is fragmented. Existing models for exponential growth, such as HDT0L-systems, are not equivalent to each other, and it is unclear which, if any, constitutes a "canonical" notion of finite-state computation for this growth rate.

A specific gap identified is the status of MSO set interpretations. These logical formalisms extend standard MSO transductions by utilizing set variables (monadic variables) to define the output universe, naturally leading to exponential output sizes. However, it was an open question whether this class possesses the crucial property of regularity reflection (i.e., whether the inverse image of a regular language under the function is regular). Resolving this is significant because it would settle a major conjecture regarding automatic structures: specifically, that every automatic $\omega$ -word has a decidable MSO theory.

2. Methodology and Models

The authors propose a new class of functions called expregular functions, defined as those computable by MSO set interpretations. To establish the robustness of this class, the paper introduces and analyzes three distinct formalisms:

MSO Set Interpretations: A logical formalism where the output string is defined by an MSO formula over the input string's positions, using set variables to generate a universe of configurations (which form the output positions). The order and labeling of the output are defined by MSO formulas.
Yield-Hennie Machines: A branching extension of Hennie machines (one-tape Turing machines with a bounded-visit property). These machines can spawn parallel subprocesses. The output is the concatenation of the letters produced by the leaves of the computation tree (the "yield"). They are restricted by a bounded-visit condition on each branch.
Ariadne Transducers: A sequential model extending pebble transducers. They utilize a stack to record the history of a bounded-visit computation. Crucially, they can access the entire substack corresponding to the history of the current input position. They support "push" (extending the computation) and "pop" (reverting with an inflationary update to avoid cycles) operations.

3. Key Contributions and Results

A. Equivalence of Models

The primary technical contribution is the proof of equivalence between these three models:

MSO Set Interpretations $\to$ Yield-Hennie Machines: This is the most complex translation. The authors introduce the concept of simplicity of an interval of configurations at a "split" (a cut in the input string). They prove that simplicity is bounded for any MSO set interpretation. To handle the encoding of intervals during the machine's execution, they introduce definable interval bases and funnels (sequences of intervals and splits). This allows the machine to locally update its state (a coloring of the input) as it traverses the input, maintaining the necessary information to generate the correct output factors.
Yield-Hennie Machines $\to$ Ariadne Transducers: This translation is relatively straightforward. The Ariadne transducer simulates the tree traversal of the Yield-Hennie machine's run. Moving down the tree corresponds to pushing onto the stack, and moving up corresponds to popping.
Ariadne Transducers $\to$ MSO Set Interpretations: This direction relies on proving that the language of reachable configurations (stacks) for an Ariadne transducer is regular. The authors achieve this by translating Ariadne automata into alternating Hennie automata. Since alternating Hennie automata are known to recognize regular languages (a result from Dartois, Nguyen, and Peyrat), the stack configurations form a regular language, which can then be defined by an MSO formula.

B. Regularity Reflection and Decidability

The equivalence establishes that MSO set interpretations are regularity reflecting. This means that for any expregular function $f$ and any regular language $L$ , the inverse image $f^{-1}(L)$ is regular.

Significance: This result confirms that expregular functions form a robust class analogous to polyregular functions but for exponential growth.
Corollary: As a direct consequence, the paper settles a conjecture by Bárány (and later Filiot et al.) stating that every automatic $\omega$ -word has a decidable MSO theory. This is because automatic $\omega$ -words can be viewed as outputs of MSO set interpretations over unary inputs, and regularity reflection ensures the decidability of their theories.

C. Closure Properties

The paper demonstrates that the class of expregular functions is:

Closed under precomposition by regular functions.
Closed under postcomposition by polyregular functions.
Not closed under precomposition by polyregular functions (a counterexample is provided where the composition results in super-exponential growth, exceeding the $2^{O(n)}$ bound of expregular functions).

4. Significance and Claims

The paper claims that expregular functions constitute the natural and robust notion of "exponential finite-state computation" for string-to-string functions. This claim is supported by:

Multiple Characterizations: The existence of three distinct, equivalent models (logical, branching machine, and sequential stack machine).
Regularity Reflection: The class satisfies the standard requirement for robustness in transducer theory.
Decidability: The resolution of the decidability of MSO theories for automatic $\omega$ -words.

The authors note that while the machinery developed (splits, funnels, definable bases) likely extends to tree-to-string settings, a generalization to tree-to-tree contexts would require new insights. They also highlight that the succinctness of Ariadne automata and alternating Hennie automata (Tower complexity compared to finite automata) suggests these models are more succinct than MSO formulas, though an elementary transformation between them remains an open question.

In summary, the work provides a foundational framework for understanding string-to-string functions with exponential growth, bridging the gap between logical definitions and machine models, and resolving long-standing open problems in the theory of automatic structures.