pith. sign in

arxiv: 2606.08101 · v1 · pith:I2FSCHFXnew · submitted 2026-06-06 · 🧮 math.GR

Automatic actions I. Bounded automata and orbits

Laurent Bartholdi This is my paper

Pith reviewed 2026-06-27 19:16 UTC · model grok-4.3

classification 🧮 math.GR
keywords automatic actionsbounded automataorbit relationinverse semigroupsω-regular languagesdecidabilityJulia setsFatou components
0
0 comments X

The pith

Bounded ω-regular actions of inverse semigroups make the orbit relation ω-regular.

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

The paper develops automatic actions of semigroups by ω-regular transformations on ω-regular languages, then restricts to the bounded subclass where the encoding automata lack two connected non-trivial cycles. It proves that for inverse semigroups the orbit relation under such actions is itself ω-regular. This yields decidability results for dynamical properties such as minimality and transitivity, and more broadly for any first-order sentence that quantifies over the space, specific semigroup elements, and the orbit relation. The same machinery shows that encodings of Fatou components are computable for Julia sets of post-critically finite polynomials, so first-order statements about their intersections and orbits become decidable.

Core claim

For bounded actions of inverse semigroups by ω-regular transformations, the orbit relation is also ω-regular. Consequently every first-order statement over the space of the action that involves the action of specific semigroup elements together with the orbit relation is decidable. The same boundedness condition makes the encoding of Fatou components computable for the Julia sets of post-critically finite polynomials, rendering first-order statements about their intersections, disjointness and full orbits decidable as well.

What carries the argument

Bounded ω-regular transformations, realized by Büchi automata without two connected non-trivial cycles, which force the orbit relation of an inverse-semigroup action to remain ω-regular.

Load-bearing premise

The transformations must be bounded ω-regular, meaning their Büchi automata contain no two connected non-trivial cycles.

What would settle it

An explicit bounded ω-regular action of an inverse semigroup whose orbit relation lies outside the class of ω-regular languages, or a concrete first-order sentence involving orbits that becomes undecidable under the boundedness hypothesis.

read the original abstract

We develop the theory of "automatic actions": (semi)groups acting by $\omega$-regular transformations on an $\omega$-regular language, showing that it covers a large class of heretofore-unrelated examples. We focus on the subclass of actions by "bounded" $\omega$-regular transformations, those for which the B\"uchi automata encoding the action do not have two connected non-trivial cycles. We show that, for bounded actions of inverse semigroups, the orbit relation is also $\omega$-regular. We deduce a number of corollaries, in particular decidability, for such actions, of minimality, topological transitivity, aperiodicity, and order of elements. More generally, every first-order statement over the space of the action, involving the action of specific semigroup elements as well as the relation "being in the same orbit", is decidable. We also apply this result to the study of Julia sets of post-critically finite polynomials, and show that the encoding of Fatou components is also computable; thus every first-order statement involving intersection, disjointness etc. of Fatou components or their full orbit under the polynomial, is decidable.

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 / 3 minor

Summary. The paper develops the theory of automatic actions: (semi)groups acting by ω-regular transformations on an ω-regular language. It focuses on the subclass of bounded ω-regular transformations, defined as those whose Büchi automata have no two connected non-trivial cycles. The central theorem states that for bounded actions of inverse semigroups the orbit relation is ω-regular. From this it deduces decidability of minimality, topological transitivity, aperiodicity and element orders, and more generally decidability of every first-order statement over the space that involves the action of specific semigroup elements together with the orbit relation. The result is applied to Julia sets of post-critically finite polynomials, where the encoding of Fatou components is shown to be computable, yielding decidability of first-order statements about intersections, disjointness and full orbits of Fatou components.

Significance. If the central derivation holds, the work supplies a uniform automata-theoretic framework that renders a large class of previously unrelated actions decidable, including important examples from complex dynamics. The boundedness restriction is shown to be sufficient for ω-regularity of orbits, which in turn gives a clean route to first-order decidability; the Julia-set application demonstrates concrete computability for Fatou-component encodings. These features constitute a genuine advance at the interface of automata theory, semigroup actions and holomorphic dynamics.

minor comments (3)
  1. [Abstract] Abstract, line 3: the phrase 'do not have two connected non-trivial cycles' would benefit from an immediate parenthetical gloss or forward reference to the precise automaton-theoretic definition used in §2.
  2. [Introduction] The manuscript should include an explicit list (with citations) of the 'heretofore-unrelated examples' mentioned in the first paragraph so that readers can immediately see the scope of the new framework.
  3. [Main results] When stating the general first-order decidability corollary, it would help to indicate the precise fragment of first-order logic (e.g., quantifier prefix) for which the decision procedure is effective.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful reading and positive evaluation of the manuscript. The report recommends minor revision but lists no specific major comments. We therefore have no individual points requiring rebuttal or revision at this stage. The central results on bounded automatic actions of inverse semigroups and the resulting decidability statements, including the application to Fatou components of post-critically finite polynomials, stand as presented.

Circularity Check

0 steps flagged

No significant circularity; central claim is a derived theorem from the boundedness definition

full rationale

The paper defines bounded ω-regular actions explicitly as those whose Büchi automata have no two connected non-trivial cycles. It then states a theorem that under this restriction, for inverse semigroup actions, the orbit relation is ω-regular (yielding decidability corollaries). This is presented as a non-trivial derivation rather than a definitional restatement or fit. No self-citation load-bearing steps, uniqueness theorems, or ansatz smuggling are visible in the abstract or described logic. The result is not equivalent to its inputs by construction; it is a property proved from the automata restriction. The derivation chain appears self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 2 invented entities

The central claim rests on the newly introduced notions of automatic and bounded actions together with standard facts from automata theory; no numerical free parameters appear in the abstract.

axioms (1)
  • standard math Büchi automata and ω-regular languages satisfy the standard closure and decidability properties established in automata theory.
    The paper invokes these properties to define automatic actions and to conclude decidability of first-order statements.
invented entities (2)
  • automatic action no independent evidence
    purpose: Unify semigroup actions realized by ω-regular transformations on ω-regular languages.
    New overarching concept introduced to cover a large class of examples.
  • bounded ω-regular transformation no independent evidence
    purpose: Restrict to automata without two connected non-trivial cycles so that orbit relations become ω-regular.
    Central technical restriction defined in the paper to obtain the main theorems.

pith-pipeline@v0.9.1-grok · 5731 in / 1303 out tokens · 29762 ms · 2026-06-27T19:16:26.788034+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

37 extracted references · 19 canonical work pages · 3 internal anchors

  1. [1]

    Anderson and Ian F

    Jared E. Anderson and Ian F. Putnam, Topological invariants for substitution tilings and their associated C˚-algebras, Ergodic Theory Dynam. Systems 18 (1998), no. 3, 509–537. MR2000a:46112

    1998

  2. [2]

    33 (2022), no

    Daniele D’Angeli, Dominik Francoeur, Emanuele Rodaro, and Jan Philipp Wächter, On the orbits of automaton semigroups and groups , Algebra Discrete Math. 33 (2022), no. 1, 1–29, available at arXiv:1903.00222. MR4440434

    arXiv 2022

  3. [3]

    Vince Bárány, Łukasz Kaiser, and Alex Rabinovich, Expressing cardinality quantifiers in monadic second-order logic over trees , Fund. Inform. 100 (2010), no. 1-4, 1–17. MR2741933

    2010

  4. [4]

    Laurent Bartholdi, The growth of Grigorchuk’s torsion group , Internat. Math. Res. Notices 20 (1998), 1049–1054, DOI 10.1155/S1073792898000622, available at arXiv:math/0012108. MR1656258 (99i:20049)

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1155/s1073792898000622 1998

  5. [5]

    Laurent Bartholdi and Ivan Mitrofanov, The word and order problems for self-similar and automata groups , Groups Geom. Dyn. 14 (2020), no. 2, 705–728, DOI 10.4171/GGD/560, available at arXiv:1710.10109. MR4118634

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.4171/ggd/560 2020

  6. [6]

    Laurent Bartholdi, Monadic second-order logic and the domino problem on self-similar graphs, Groups Geom. Dyn. 16 (2022), 37, DOI 10.4171/ggd/689, available at arXiv: 2011.02735. MR4536435

    work page doi:10.4171/ggd/689 2022

  7. [7]

    Laurent Bartholdi, Volodymyr Nekrashevych, and Tianyi Zheng, Growth of groups with linear Schreier graphs (2022), submitted, available at arXiv:2204.01792

    arXiv 2022

  8. [8]

    (2025), work in progress

    Laurent Bartholdi and Ivan Mitrofanov, Automatic actions II. (2025), work in progress

    2025

  9. [9]

    Thuswaldner, and Reem Yassawi, Recognizability for sequences of morphisms , Ergodic Theory Dynam

    Valérie Berthé, Wolfgang Steiner, Jörg M. Thuswaldner, and Reem Yassawi, Recognizability for sequences of morphisms , Ergodic Theory Dynam. Systems 39 (2019), no. 11, 2896–2931, DOI 10.1017/etds.2017.144. MR4015135

    work page doi:10.1017/etds.2017.144 2019

  10. [10]

    Bezuglyi, J

    S. Bezuglyi, J. Kwiatkowski, and K. Medynets, Aperiodic substitution systems and their Bratteli diagrams , Ergodic Theory Dynam. Systems 29 (2009), no. 1, 37–72, DOI 10.1017/S0143385708000230. MR2470626

    work page doi:10.1017/s0143385708000230 2009

  11. [11]

    Achim Blumensath and Erich Grädel, Automatic structures, 15th Annual IEEE Symposium on Logic in Computer Science (Santa Barbara, CA, 2000), IEEE Comput. Soc. Press, Los Alamitos, CA, 2000, pp. 51–62, DOI 10.1109/LICS.2000.855755. MR1946085

    work page doi:10.1109/lics.2000.855755 2000

  12. [12]

    Bondarenko, Natalia V

    Ievgen V. Bondarenko, Natalia V. Bondarenko, Said N. Sidki, and Flavia R. Zapata, On the conjugacy problem for finite-state automorphisms of regular rooted trees , Groups Geom. Dyn. 7 (2013), no. 2, 323–355, DOI 10.4171/GGD/184. With an appendix by Raphaël M. Jungers. MR3054572

    work page doi:10.4171/ggd/184 2013

  13. [13]

    Bondarenko and Volodymyr V

    Ievgen V. Bondarenko and Volodymyr V. Nekrashevych, Post-critically finite self-similar groups, Algebra Discrete Math. 4 (2003), 21–32. MR2070400 (2005d:20041)

    2003

  14. [14]

    34 LAURENT BARTHOLDI

    Ievgen Bondarenko and Jan Philipp Wächter, On Orbits and the Finiteness of Bounded Automaton Groups (2019), available at arXiv:1912.06897. 34 LAURENT BARTHOLDI

    arXiv 2019

  15. [15]

    Richard Büchi, Weak second-order arithmetic and finite automata , Z

    J. Richard Büchi, Weak second-order arithmetic and finite automata , Z. Math. Logik Grund- lagen Math. 6 (1960), 66–92, DOI 10.1002/malq.19600060105. MR125010

    work page doi:10.1002/malq.19600060105 1960

  16. [16]

    1960 Internat

    , On a decision method in restricted second order arithmetic , Logic, Methodology and Philosophy of Science (Proc. 1960 Internat. Congr.), Stanford Univ. Press, Stanford, CA, 1962, pp. 1–11. MR0183636

    1960

  17. [17]

    Jean-Marie Dumont and Alain Thomas, Systemes de numeration et fonctions fractales re- latifs aux substitutions , Theoret. Comput. Sci. 65 (1989), no. 2, 153–169, DOI 10.1016/0304- 3975(89)90041-8 (French, with English summary). MR1020484

    work page doi:10.1016/0304- 1989

  18. [18]

    Durand, B

    F. Durand, B. Host, and C. Skau, Substitutional dynamical systems, Bratteli diagrams and dimension groups , Ergodic Theory Dynam. Systems 19 (1999), no. 4, 953–993, DOI 10.1017/S0143385799133947. MR1709427

    work page doi:10.1017/s0143385799133947 1999

  19. [19]

    David B. A. Epstein, James W. Cannon, Derek F. Holt, Silvio V. F. Levy, Michael S. Paterson, and William P. Thurston, Word processing in groups , Jones and Bartlett Publishers, 1992

    1992

  20. [20]

    Erschler and Tianyi Zheng, Growth of periodic Grigorchuk groups, Invent

    Anna G. Erschler and Tianyi Zheng, Growth of periodic Grigorchuk groups, Invent. Math. 219 (2020), no. 3, 1069–1155, DOI 10.1007/s00222-019-00922-0, available at arXiv:1802.09077. MR4055184

    work page doi:10.1007/s00222-019-00922-0 2020

  21. [21]

    Systems Theory 25 (1992), no

    Christiane Frougny, Representations of numbers and finite automata , Math. Systems Theory 25 (1992), no. 1, 37–60, DOI 10.1007/BF01368783. MR1139094

    work page doi:10.1007/bf01368783 1992

  22. [22]

    Gluškov, Abstract theory of automata , Uspehi Mat

    Victor M. Gluškov, Abstract theory of automata , Uspehi Mat. Nauk 16 (1961), no. 5 (101), 3–62. MR25#1976

    1961

  23. [23]

    Grigorchuk, On Burnside’s problem on periodic groups , Funkcional

    Rostislav I. Grigorchuk, On Burnside’s problem on periodic groups , Funkcional. Anal. i Prilo en. 14 (1980), no. 1, 53–54. English translation: Functional Anal. Appl. 14 (1980), 41–43. MR81m:20045

    1980

  24. [24]

    , On the Milnor problem of group growth , Dokl. Akad. Nauk SSSR 271 (1983), no. 1, 30–33. MR85g:20042

    1983

  25. [25]

    Leibniz Int

    Łukasz Kaiser, Sasha Rubin, and Vince Bárány, Cardinality and counting quantifiers on omega-automatic structures , STACS 2008: 25th International Symposium on Theoretical Aspects of Computer Science, LIPIcs. Leibniz Int. Proc. Inform., vol. 1, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2008, pp. 385–396. MR2873751

    2008

  26. [26]

    Olga Kharlampovich, Bakhadyr Khoussainov, and Alexei Miasnikov, From automatic structures to automatic groups , Groups Geom. Dyn. 8 (2014), no. 1, 157–198, DOI 10.4171/GGD/221. MR3209707

    work page doi:10.4171/ggd/221 2014

  27. [27]

    Sci., vol

    Bakhadyr Khoussainov and Anil Nerode, Automatic presentations of structures , Logic and computational complexity (Indianapolis, IN, 1994), Lecture Notes in Comput. Sci., vol. 960, Springer, Berlin, 1995, pp. 367–392, DOI 10.1007/3-540-60178-3_93. MR1449670

    work page doi:10.1007/3-540-60178-3_93 1994

  28. [28]

    Symbolic Logic 73 (2008), no

    Dietrich Kuske and Markus Lohrey, First-order and counting theories of ω-automatic struc- tures, J. Symbolic Logic 73 (2008), no. 1, 129–150, DOI 10.2178/jsl/1208358745. MR2387935

    work page doi:10.2178/jsl/1208358745 2008

  29. [29]

    Brigitte Mossé, Puissances de mots et reconnaissabilité des points fixes d’une substitu- tion, Theoret. Comput. Sci. 99 (1992), no. 2, 327–334, DOI 10.1016/0304-3975(92)90357-L (French). MR1168468

    work page doi:10.1016/0304-3975(92)90357-l 1992

  30. [30]

    Volodymyr Nekrashevych, Self-similar inverse semigroups and Smale spaces , Internat. J. Algebra Comput. 16 (2006), no. 5, 849–874, DOI 10.1142/S0218196706003153. MR2274718

    work page doi:10.1142/s0218196706003153 2006

  31. [31]

    Nekrashevych, Self-similar groups , Mathematical Surveys and Monographs, vol

    Volodymyr V. Nekrashevych, Self-similar groups , Mathematical Surveys and Monographs, vol. 117, American Mathematical Society, Providence, RI, 2005. MR2162164 (2006e:20047)

    2005

  32. [32]

    , Palindromic subshifts and simple periodic groups of intermediate growth , Ann. of Math. (2) 187 (2018), no. 3, 667–719, DOI 10.4007/annals.2018.187.3.2, available at arXiv: 1601.01033. MR3779956

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.4007/annals.2018.187.3.2 2018

  33. [33]

    Published electronically at http://oeis.org

    OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences , 2024. Published electronically at http://oeis.org

    2024

  34. [34]

    The mathematical structures of equilibrium sta- tistical mechanics

    David Ruelle, Thermodynamic formalism , 2nd ed., Cambridge Mathematical Library, Cam- bridge University Press, Cambridge, 2004. The mathematical structures of equilibrium sta- tistical mechanics. MR2129258

    2004

  35. [35]

    Ville Salo, Decidability and universality of quasiminimal subshifts , J. Comput. System Sci. 89 (2017), 288–314, DOI 10.1016/j.jcss.2017.05.017. MR3681244

    work page doi:10.1016/j.jcss.2017.05.017 2017

  36. [36]

    Vershik and Alexander N

    Anatoly M. Vershik and Alexander N. Livshits, Adic models of ergodic transformations, spec- tral theory, substitutions, and related topics , Representation theory and dynamical systems, Adv. Soviet Math., vol. 9, Amer. Math. Soc., Providence, RI, 1992, pp. 185–204. MR1166202 AUTOMATIC ACTIONS I. BOUNDED AUTOMATA AND ORBITS 35

    1992

  37. [37]

    Williams, Expanding attractors , Inst

    Robert F. Williams, Expanding attractors , Inst. Hautes Études Sci. Publ. Math. 43 (1974), 169–203. MR0348794 Institut Camille Jordan, Université Claude Bernard, Lyon Email address : laurent.bartholdi@gmail.com

    1974