arxiv: 2602.21019 · v3 · submitted 2026-02-24 · 💻 cs.FL · cs.LO

Recognition: no theorem link

Expregular functions

Thomas Colcombet , Nathan Lhote , Pierre Ohlmann

Authors on Pith no claims yet

Pith reviewed 2026-05-15 19:39 UTC · model grok-4.3

classification 💻 cs.FL cs.LO

keywords expregular functionsMSO set interpretationsyield-Hennie machinesAriadne transducersregularity reflectingautomatic structuresomega-wordsdecidability

0 comments

The pith

MSO set interpretations are regularity reflecting, proving that every automatic omega-word has a decidable MSO theory.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces expregular functions as the exponential-growth counterpart to polyregular functions. It defines this class through three models: MSO set interpretations that act on monadic variables, yield-Hennie machines that are bounded-visit branching Turing machines, and Ariadne transducers that are restricted two-way pushdown devices. The central result translates MSO set interpretations into yield-Hennie machines, transferring the known regularity-reflecting property of the latter. This equivalence settles the conjecture that the monadic second-order theory of any automatic infinite word is decidable.

Core claim

The authors prove that MSO set interpretations, yield-Hennie machines, and Ariadne transducers define exactly the same class of string-to-string functions with exponential growth. The translation from MSO set interpretations to yield-Hennie machines shows that the former preserve regularity, because the latter already do so. The reverse direction follows from showing that Ariadne automata recognise only regular languages. Together these equivalences establish that every automatic omega-word has a decidable MSO theory.

What carries the argument

The translation from MSO set interpretations to yield-Hennie machines, which transfers the regularity-reflecting property by preserving preimages of regular languages.

If this is right

The three models are fully equivalent for defining expregular functions.
Yield-Hennie machines and Ariadne transducers both preserve regularity.
Ariadne automata recognise precisely the regular languages.
Automatic structures based on omega-words admit effective decision procedures for all MSO properties.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The bounded-visit restriction appears to be the precise mechanism that limits growth to exponential while retaining regularity reflection.
Similar translations might apply to other growth classes or to tree-to-tree functions.
One could now algorithmically decide MSO properties on concrete automatic words such as the Champernowne word or Sturmian words.

Load-bearing premise

The translations between MSO set interpretations, yield-Hennie machines, and Ariadne transducers correctly preserve the regularity-reflecting property.

What would settle it

An explicit MSO set interpretation whose inverse image of some regular language is non-regular, or an automatic omega-word whose monadic second-order theory is undecidable.

read the original abstract

Polyregular functions form a robust class of string-to-string functions with polynomial growth, as evidenced by Bojanczyk (2018). This class admits numerous descriptions and enjoys several closure properties. Most notably, polyregular functions are regularity reflecting (\ie the inverse image of a regular language is regular). In this work, we propose a robust class of string-to-string functions with exponential growth which we call expregular functions. We consider the following three models for describing them: - MSO set interpretations, which extend MSO interpretations (one of the models capturing polyregular functions), by operating on monadic variables instead of tuples of first-order variables; - yield-Hennie machines, which are branching one-tape Turing machines with bounded visit; and - Ariadne transducers, a new model of 2-way pushdown machines with a bounded visit restriction. Our main contribution is a translation from MSO set interpretations to yield-Hennie machines, which are known to be regularity reflecting (Dartois, Nguy\~{\^{e}}n, Peyrat 2026). In particular this establishes that MSO set interpretations are regularity reflecting, which in turn settles a major conjecture about automatic structures: every automatic $\omega$-word has a decidable MSO theory. Yield-Hennie machine directly translate to Ariadne transducers, and our second contribution is to prove that Ariadne transducers also translate to MSO set interpretations, thus establishing the equivalence of the three models. This is obtained by showing that Ariadne automata -- the automaton model corresponding to Ariadne transducers -- recognise regular languages.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper defines expregular functions through three equivalent models and uses the translation to yield-Hennie machines to settle the conjecture that automatic omega-words have decidable MSO theories.

read the letter

The core advance is a clean extension of the polyregular framework to exponential growth. They introduce expregular functions via MSO set interpretations (lifting the usual MSO interpretations by allowing monadic set variables), show these are equivalent to yield-Hennie machines and to a new Ariadne transducer model, and leverage the known regularity-reflecting property of yield-Hennie machines to conclude that MSO set interpretations are regularity reflecting. That directly implies the long-standing conjecture on automatic structures is true. The equivalence proofs and the corollary for the conjecture are the parts that stand out; the work sits squarely on established results for polyregular functions and yield-Hennie machines without obvious circularity. The translations appear to preserve the computed functions and the bounded-visit restrictions needed for the property to transfer. The main soft spot is that the MSO-to-yield-Hennie direction is the load-bearing step, and any mismatch in how monadic variables or exponential outputs are handled would leave the conjecture open. The abstract and claimed proofs suggest the construction is careful, but the details matter. This is aimed at people working on automata, logic on infinite words, and automatic structures. A reader already familiar with polyregular functions and Hennie machines will get the most out of it quickly. I would send it to peer review; the result is substantial enough to justify referee time even if some technical steps need polishing.

Referee Report

1 major / 2 minor

Summary. The paper introduces expregular functions as a class of string-to-string functions with exponential growth, defined equivalently via three models: MSO set interpretations (extending MSO interpretations by using monadic set variables), yield-Hennie machines (branching one-tape Turing machines with bounded visits), and Ariadne transducers (new 2-way pushdown machines with bounded visits). The central result is a translation from MSO set interpretations to yield-Hennie machines (known to be regularity reflecting), which implies that MSO set interpretations are regularity reflecting and settles the conjecture that every automatic ω-word has a decidable MSO theory. Equivalence is completed by showing yield-Hennie machines translate to Ariadne transducers and that Ariadne automata recognize regular languages, hence Ariadne transducers translate back to MSO set interpretations.

Significance. If the translations hold, the work provides a robust, regularity-reflecting class for exponential-growth functions analogous to polyregular functions for polynomial growth, with multiple equivalent characterizations and closure properties. It directly resolves a major open conjecture on automatic structures by establishing decidability of MSO theories for automatic ω-words. The machine-checked or explicit translation steps (if present) and the use of an independently established regularity-reflecting model (yield-Hennie) are strengths.

major comments (1)

[Main translation section (MSO set interpretations to yield-Hennie)] The translation from MSO set interpretations to yield-Hennie machines (main contribution) must explicitly preserve the exact string-to-string function computed, including on all inputs, for monadic set variables, and respecting exponential growth and bounded visits; otherwise the regularity-reflecting property does not transfer and the automatic-structure conjecture remains open. The abstract sketches the steps but the detailed construction (likely in the section presenting the translation) needs to address cases for set variables and output-string construction.

minor comments (2)

[Definitions of models] Clarify the precise definition of 'bounded visit' restriction in both yield-Hennie machines and Ariadne transducers to ensure consistency across the equivalence proofs.
[Introduction or overview section] Add a diagram or table summarizing the three models and the directions of the translations proved.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for recognizing the significance of the results. We address the major comment below and will revise the manuscript to improve clarity on the key construction.

read point-by-point responses

Referee: [Main translation section (MSO set interpretations to yield-Hennie)] The translation from MSO set interpretations to yield-Hennie machines (main contribution) must explicitly preserve the exact string-to-string function computed, including on all inputs, for monadic set variables, and respecting exponential growth and bounded visits; otherwise the regularity-reflecting property does not transfer and the automatic-structure conjecture remains open. The abstract sketches the steps but the detailed construction (likely in the section presenting the translation) needs to address cases for set variables and output-string construction.

Authors: We agree that explicit preservation of the computed function on every input is essential for transferring regularity reflection. Section 4 defines the translation by simulating the MSO set interpretation directly on the input string: each monadic set variable is represented by a finite collection of states in the branching Hennie machine that track the positions belonging to the set, with the machine's bounded-visit discipline ensuring that the simulation respects the exponential growth bound. The output string is produced by emitting symbols according to the interpretation's output formula at the appropriate yield points. To make this fully explicit, we will revise Section 4 to include a case analysis for set variables (covering both singleton and arbitrary monadic sets) together with an inductive argument on formula structure that shows the machine computes exactly the same string-to-string function as the interpretation for every input. This expanded presentation will also restate the growth and visit bounds at each step. revision: yes

Circularity Check

0 steps flagged

Derivation relies on explicit translations to an externally established regularity-reflecting model with no self-referential reductions

full rationale

The paper establishes its main result via a direct translation from MSO set interpretations to yield-Hennie machines, citing an independent prior result (Dartois et al. 2026, different authors) that yield-Hennie machines are regularity reflecting. This transfers the property without any reduction to fitted parameters, self-definitional equations, or load-bearing self-citations within the present work. The subsequent translations to and from Ariadne transducers are constructive equivalences shown by explicit constructions, with no steps that rename known results or smuggle ansatzes via self-citation. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 2 invented entities

The central claim rests on standard properties of monadic second-order logic, finite automata, and the previously published result that yield-Hennie machines are regularity reflecting; no data-fitted parameters are used.

axioms (1)

standard math Standard properties of monadic second-order logic and finite automata
The models and translations rely on well-established results in logic and automata theory.

invented entities (2)

Ariadne transducers no independent evidence
purpose: New model of bounded-visit 2-way pushdown machines for defining expregular functions
Introduced in the paper as one of the three equivalent characterizations.
expregular functions no independent evidence
purpose: Class of string-to-string functions with exponential growth
Defined via the three models presented in the paper.

pith-pipeline@v0.9.0 · 5590 in / 1359 out tokens · 31863 ms · 2026-05-15T19:39:16.945029+00:00 · methodology

discussion (0)

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Tree transducers of linear size-to-height increase (and the additive conjunction of linear logic)
cs.FL 2026-05 unverdicted novelty 7.0

Tree-to-tree Hennie machines compute functions with linear size-to-height increase that lie between LSHI macro tree transducers and MSO set interpretations, are closed under specific compositions, contain the strict l...