pith. sign in

arxiv: 2606.30013 · v1 · pith:4W6Y3R54new · submitted 2026-06-29 · 💻 cs.FL

Preservation Theorems for Transducer Outputs

Val\'erie Berth\'e , Herman Goulet-Ouellet , Toghrul Karimov , Dominique Perrin , Mihir Vahanwala This is my paper

Pith reviewed 2026-06-30 03:47 UTC · model grok-4.3

classification 💻 cs.FL
keywords deterministic transducersinfinite wordsrecurrencemorphic wordsfactor frequenciesKrohn-Rhodes theoremshift spaces
0
0 comments X

The pith

Deterministic transducers preserve recurrence, morphic structure, and factor frequencies of infinite words.

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

The paper shows that running a deterministic finite-state transducer on an infinite word transfers several combinatorial properties from the input to the output word. A sympathetic reader would care because this identifies which structural features of sequences survive finite-state processing, a common operation in automata theory and symbolic dynamics. The argument proceeds by decomposing the transducer via the Krohn-Rhodes theorem and then applying ergodic-theoretic arguments on the associated shift spaces to track the listed properties.

Core claim

For any deterministic finite-state transducer A and any infinite word x, if x is recurrent then A(x) is recurrent; if x is morphic then A(x) is morphic; and if x possesses well-defined factor frequencies then so does A(x).

What carries the argument

The Krohn-Rhodes theorem, which decomposes any finite automaton into a cascade of simpler automata whose action on words can be analyzed separately using the ergodic theory of shift spaces.

If this is right

  • Recurrence passes from input to output under any deterministic finite-state transduction.
  • The class of morphic words is closed under deterministic finite-state transduction.
  • Existence of factor frequencies is invariant under deterministic finite-state transduction.

Where Pith is reading between the lines

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

  • The same preservation may extend to other shift-space invariants that are stable under finite-to-one factor maps.
  • One could test whether the results survive when the transducer is allowed a finite number of nondeterministic choices.
  • The approach suggests checking preservation for properties defined by forbidden patterns rather than frequencies.

Load-bearing premise

The Krohn-Rhodes decomposition together with the ergodic theory of shift spaces suffice to transfer the listed combinatorial properties through the transducer.

What would settle it

An explicit recurrent infinite word x and a deterministic transducer A such that A(x) fails to be recurrent.

Figures

Figures reproduced from arXiv: 2606.30013 by Dominique Perrin, Herman Goulet-Ouellet, Mihir Vahanwala, Toghrul Karimov, Val\'erie Berth\'e.

Figure 1
Figure 1. Figure 1: Summary of main results. Arrow from block [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
read the original abstract

Suppose we have a deterministic finite-state transducer $A$ and an infinite word $x$, and run $A$ on $x$ to obtain an infinite word $A(x)$. Which properties of $x$ are guaranteed to also hold for $A(x)$? In this paper, we study this preservation question for various well-known combinatorial properties, e.g., recurrence, being morphic, and having factor frequencies. The celebrated Krohn-Rhodes theorem provides the framework for proving our preservation results, and our techniques are based on the ergodic theory of symbolic dynamical systems, i.e., shift spaces.

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.

Referee Report

0 major / 2 minor

Summary. The paper studies preservation of combinatorial properties of infinite words under deterministic finite-state transducers. It claims that if x is recurrent, morphic, or has well-defined factor frequencies, then so does A(x) for any such transducer A, with proofs based on the Krohn-Rhodes decomposition of the transducer's semigroup together with ergodic-theoretic arguments on the induced map on shift spaces.

Significance. If the claims hold, the results give a systematic way to transfer recurrence, morphicity, and frequency properties across transducer outputs, linking automata theory with symbolic dynamics via an established decomposition theorem. The framework is reusable and the reliance on Krohn-Rhodes plus ergodic theory is a methodological strength.

minor comments (2)
  1. The abstract lists three example properties but does not enumerate the full set considered; the introduction should state the complete list of properties for which preservation is proved.
  2. Notation for the transducer output A(x) and the induced shift-space map should be introduced with a short diagram or example in §2 to aid readers unfamiliar with the ergodic setting.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the supportive summary, recognition of the significance of linking automata theory with symbolic dynamics via the Krohn-Rhodes theorem, and the recommendation of minor revision. No specific major comments are listed in the report.

Circularity Check

0 steps flagged

No significant circularity; derivation rests on external theorems

full rationale

The paper's preservation results for recurrence, morphicity, and factor frequencies under deterministic finite-state transducers are derived by applying the Krohn-Rhodes theorem (an external 1965 result by unrelated authors) together with standard ergodic theory on shift spaces. These are independent, pre-existing mathematical frameworks invoked as the proof structure rather than derived or fitted within the paper. No self-definitional equations, fitted inputs renamed as predictions, load-bearing self-citations, or ansatz smuggling appear in the abstract or described approach. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper rests on the Krohn-Rhodes theorem and standard results from ergodic theory of symbolic dynamical systems; no free parameters or invented entities are indicated in the abstract.

axioms (2)
  • standard math Krohn-Rhodes theorem provides a decomposition framework applicable to transducer preservation questions
    Abstract states it supplies the framework for proving preservation results.
  • domain assumption Ergodic theory of shift spaces can be used to analyze preservation of combinatorial properties under transducers
    Abstract identifies this as the technical basis alongside Krohn-Rhodes.

pith-pipeline@v0.9.1-grok · 5634 in / 1278 out tokens · 47678 ms · 2026-06-30T03:47:21.431442+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

44 extracted references · 1 canonical work pages · 1 internal anchor

  1. [1]

    The ubiquitous Prouhet-Thue-Morse sequence

    Jean-Paul Allouche and Jeffrey Shallit. The ubiquitous Prouhet-Thue-Morse sequence. In Sequences and their applications (Singapore, 1998) , Springer Ser. Discrete Math. Theor. Comput. Sci., pages 1–16. Springer, London, 1999

    1998

  2. [2]

    Automatic Sequences: Theory, Applications, Generalizations

    Jean-Paul Allouche and Jeffrey Shallit. Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press, 2003

    2003

  3. [3]

    Aperiodic order

    Micael Baake and Uwe Grimm. Aperiodic order. Vol. 1, volume 149 of Encyclopedia of Mathematics and its Application . Cambridge University Press, 2013

    2013

  4. [4]

    Measure and Integration Theory

    Heinz Bauer. Measure and Integration Theory . De Gruyter, Berlin, New York, 2001

    2001

  5. [5]

    Normal numbers and finite automata

    Verónica Becher and Pablo Ariel Heiber. Normal numbers and finite automata. Theoretical Computer Science, 477:109–116, 2013

    2013

  6. [6]

    On the decidability of monadic second-order logic with arithmetic predicates

    Valérie Berthé, Toghrul Karimov, Joris Nieuwveld, Joël Ouaknine, Mihir Vahan- wala, and James Worrell. On the decidability of monadic second-order logic with arithmetic predicates. In Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science , pages 1–14, 2024

    2024

  7. [7]

    The monadic theory of toric words

    Valérie Berthé, Toghrul Karimov, Joris Nieuwveld, Joël Ouaknine, Mihir Va- hanwala, and James Worrell. The monadic theory of toric words. Theoretical Computer Science, 1025:114959, 2025

    2025

  8. [8]

    Beyond substitutive dynamical systems: S-adic expansions, 2017

    Valérie Berthé and Vincent Delecroix. Beyond substitutive dynamical systems: S-adic expansions, 2017

    2017

  9. [9]

    Density of group languages in shift spaces, 2024

    Valérie Berthé, Herman Goulet-Ouellet, Carl-Fredrik Nyberg-Brodda, Dominique Perrin, and Karl Petersen. Density of group languages in shift spaces, 2024

    2024

  10. [10]

    Boshernitzan

    Michael D. Boshernitzan. A condition for unique ergodicity of minimal symbolic flows. Ergodic Theory and Dynamical Systems , 12(3):425–428, 1992

    1992

  11. [11]

    Preservation of normality by unambiguous transducers

    Olivier Carton. Preservation of normality by unambiguous transducers. In Developments in language theory , volume 13257 of Lecture Notes in Comput. Sci. , pages 90–101. Springer, Cham, [2022] ©2022

    2022

  12. [12]

    Preservation of normality by transducers

    Olivier Carton and Elisa Orduna. Preservation of normality by transducers. Inform. and Comput., 282:Paper No. 104650, 9, 2022

    2022

  13. [13]

    Skew products over rotations with exotic properties

    Jon Chaika. Skew products over rotations with exotic properties. Geometriae Dedicata, 168(1):369–385, 2014. 7We acknowledge that this fact was known to Olivier Carton and Vincent Delecroix. Conference’17, July 2017, Washington, DC, USA Valérie Berthé, Herman Goulet-Ouellet, Toghrul Karimov, Dominique Perrin, and Mihir Vahanwala

    2014

  14. [14]

    Green’s relations and their use in automata theory

    Thomas Colcombet. Green’s relations and their use in automata theory. In Adrian- Horia Dediu, Shunsuke Inenaga, and Carlos Martín-Vide, editors, Language and Automata Theory and Applications, pages 1–21, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg

    2011

  15. [15]

    A condition of Boshernitzan and uniform convergence in the multiplicative ergodic theorem

    David Damanik and Daniel Lenz. A condition of Boshernitzan and uniform convergence in the multiplicative ergodic theorem. Duke Mathematical Journal, 133(1):95 – 123, 2006

    2006

  16. [16]

    Zero-measure cantor spectrum for schrödinger operators with low-complexity potentials

    David Damanik and Daniel Lenz. Zero-measure cantor spectrum for schrödinger operators with low-complexity potentials. Journal de Mathématiques Pures et Appliquées, 85(5):671–686, 2006

    2006

  17. [17]

    Lifting generic points

    Tomasz Downarowicz and Benjamin Weiss. Lifting generic points. Ergodic Theory and Dynamical Systems , 44(9):2565–2580, 2024

    2024

  18. [18]

    Durand, B

    F. Durand, B. Host, and C. Skau. Substitutional dynamical systems, brat- teli diagrams and dimension groups. Ergodic Theory and Dynamical Systems , 19(4):953–993, 1999

    1999

  19. [19]

    Linearly recurrent subshifts have a finite number of non-periodic subshift factors

    Fabien Durand. Linearly recurrent subshifts have a finite number of non-periodic subshift factors. Ergodic Theory and Dynamical Systems , 20, 08 2008

    2008

  20. [20]

    Decidability of the HD0L ultimate periodicity problem

    Fabien Durand. Decidability of the HD0L ultimate periodicity problem. RAIRO - Theoretical Informatics and Applications, 47, 11 2011

    2011

  21. [21]

    HD0L 𝜔-equivalence and periodicity problems in the primitive case

    Fabien Durand. HD0L 𝜔-equivalence and periodicity problems in the primitive case. Unif. Distrib. Theory, 7(1):199–215, 2012

    2012

  22. [22]

    Decidability of uniform recurrence of morphic sequences

    Fabien Durand. Decidability of uniform recurrence of morphic sequences. Inter- national Journal of Foundations of Computer Science , 24(01):123–146, 2013

    2013

  23. [23]

    Dimension Groups and Dynamical Sys- tems: Substitutions, Bratteli Diagrams and Cantor Systems

    Fabien Durand and Dominique Perrin. Dimension Groups and Dynamical Sys- tems: Substitutions, Bratteli Diagrams and Cantor Systems . Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2022

    2022

  24. [24]

    Stabil- ity properties for subgroups generated by return words

    France Gheeraert, Herman Goulet-Ouellet, Julien Leroy, and Pierre Stas. Stabil- ity properties for subgroups generated by return words. European Journal of Combinatorics, 130:104224, 2025

    2025

  25. [25]

    Episturmian words: a survey

    Amy Glen and Jacques Justin. Episturmian words: a survey. RAIRO - Theoretical Informatics and Applications, 43(3):403–442, 3 2009

    2009

  26. [26]

    Suffix-connected languages

    Herman Goulet-Ouellet. Suffix-connected languages. Theoretical Computer Science, 923:126–143, 2022

    2022

  27. [27]

    M Guénais and F Parreau. Valeurs propres de transformations liées aux rotations irrationnelles et aux fonctions en escalier (eigenvalues of transformations arising from irrational rotations and step functions) (2006). arXiv preprint math/0605250

    work page internal anchor Pith review Pith/arXiv arXiv 2006

  28. [28]

    On the simplification of infinite morphic words

    Juha Honkala. On the simplification of infinite morphic words. Theoretical Computer Science, 410(8):997–1000, 2009

    2009

  29. [29]

    Algorithmic verification of linear dynamical systems, 2023

    Toghrul Karimov. Algorithmic verification of linear dynamical systems, 2023

    2023

  30. [30]

    Algebraic theory of machines

    Kenneth Krohn and John Rhodes. Algebraic theory of machines. i. prime de- composition theorem for finite semigroups and machines. Transactions of The American Mathematical Society - TRANS AMER MATH SOC , 116, 04 1965

    1965

  31. [31]

    Mariusz Lemańczyk and Mieczysław K. Mentzen. Topological ergodicity of real cocycles over minimal rotations. Monatshefte für Mathematik, 134(3):227–246, 2002

    2002

  32. [32]

    On the Krohn-Rhodes Cascaded Decomposition Theorem , pages 260–

    Oded Maler. On the Krohn-Rhodes Cascaded Decomposition Theorem , pages 260–

  33. [33]

    Springer Berlin Heidelberg, Berlin, Heidelberg, 2010

    2010

  34. [34]

    Robert McNaughton and Seymour A. Papert. Counter-Free Automata (M.I.T. research monograph no. 65). The MIT Press, 1971

    1971

  35. [35]

    Meyer and C

    A.R. Meyer and C. Thompson. Remarks on algebraic decomposition of automata. Mathematical Systems Theory, 3:110–118, 1969

    1969

  36. [36]

    Muchnik, A

    A. Muchnik, A. Semenov, and M. Ushakov. Almost periodic sequences.Theoretical Computer Science, 304(1):1–33, 2003

    2003

  37. [37]

    Yu. L. Pritykin. Finite-automaton transformations of strictly almost-periodic sequences. Mathematical Notes, 80(5):710–714, 2006

    2006

  38. [38]

    Pytheas Fogg

    N. Pytheas Fogg. Substitutions in dynamics, arithmetics and combinatorics, volume 1794 of Lecture Notes in Mathematics . Springer-Verlag, Berlin, 2002

    2002

  39. [39]

    Substitution Dynamical Systems - Spectral Analysis , volume 1294 of Lecture Notes in Mathematics

    Martine Queffélec. Substitution Dynamical Systems - Spectral Analysis , volume 1294 of Lecture Notes in Mathematics . Springer, Berlin, Heidelberg, 2nd edition, 2010

    2010

  40. [40]

    On the number of invariant measures for flows on orientable surfaces

    Evgueni A Sataev. On the number of invariant measures for flows on orientable surfaces. Mathematics of the USSR-Izvestiya , 9(4):813, 1975

    1975

  41. [41]

    The logical approach to automatic sequences—exploring combina- torics on words with Walnut, volume 482 of London Mathematical Society Lecture Note Series

    Jeffrey Shallit. The logical approach to automatic sequences—exploring combina- torics on words with Walnut, volume 482 of London Mathematical Society Lecture Note Series. Cambridge University Press, Cambridge, 2023

    2023

  42. [42]

    Strict ergodicity in zero dimensional dynamical systems and the Kronecker-Weyl theorem mod

    William A Veech. Strict ergodicity in zero dimensional dynamical systems and the Kronecker-Weyl theorem mod. 2. Transactions of the American Mathematical Society, 140:1–33, 1969

    1969

  43. [43]

    An introduction to ergodic theory , volume 79

    Peter Walters. An introduction to ergodic theory , volume 79. Springer Science & Business Media, 2000

    2000

  44. [44]

    Über die Gleichverteilung von Zahlen mod

    Hermann Weyl. Über die Gleichverteilung von Zahlen mod. Eins. Mathematische Annalen, 77(3):313–352, 1916

    1916