Pith. sign in

REVIEW 3 major objections 4 minor 18 references

Stallings foldings for rational subsets of automatic groups

T0 review · 3 major / 4 minor · reviewed 2026-08-01 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For an L-proximate rational subset of a finitely presented automatic group, the paper's iterated folding procedure eventually accepts all L-representatives of the subset, and in the submonoid case it halts algorithmically.

desk verdict Core folding theorems are a genuine extension and look correct; the surface-group section leans on a sketched ladder argument that needs real work before the examples can be trusted. read the letter →

arxiv 2607.26284 v1 pith:NBCKGK5V submitted 2026-07-28 math.GR

Lucía Asencio-Martín , John R. Britnell , Andrew Duncan , Dominik Francoeur , Sarah Rees This is my paper · ORCID
classification math.GR MSC 20F1020F6568Q45
keywords automaticgroupsrationalsubsetsStallingsfoldingsL-proximacyL-recognisablesubmonoidmembershipsurfacesmallcancellation
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper extends the classical graph-folding technique for subgroups of free groups to arbitrary rational subsets of automatic groups. Its central result is that if a regular language Q0 is L-proximate—meaning every L-word representing an element of the subset travels close, with bounded delay, to a word of Q0—then an iterated procedure of adding relator and backtracking loops, folding them, and determinising will after finitely many rounds accept every L-representative of the subset. Consequently such a subset is L-recognisable, and hence has decidable membership. For finitely generated submonoids the procedure becomes an algorithm with an explicit halting test, so the membership problem is constructively decidable. In surface groups, small cancellation theory shows that Dehn-reduced languages are weakly L-proximate, yielding new submonoids with decidable membership.

What carries the argument

The central mechanism is an iterated three-step folding procedure (Construction 4.7). Starting with an automaton A_{n-1} for a regular language Q_{n-1}, it (1) adds an ε→r cycle for each relator r and a length-two cycle ss^{-1} for each generator at every state; (2) applies the standard algorithm that folds a regular language by closing it under free reduction; and (3) determinises the result. The key identity is Corollary 4.9: the union of all Q_n is exactly µ^{-1}(µ(Q0)), the set of all words mapping into the same subset of the group. L-proximacy is the convexity hypothesis that makes this union stabilise in time to contain the L-representatives; the halting test in Theorem 5.2 exploits th

What would settle it

Build a reduced Van Kampen diagram for uv^{-1} in a genus-2 surface group, where u is Dehn-reduced and v is a geodesic representing the same element. If the diagram is not a single vertex, a single 2-cell, or a ladder whose every 2-cell meets both boundary rails, then Lemma 6.8's (g+1)-fellow-travel conclusion—and hence the weak L-proximacy of Dehn-reduced languages—fails. More broadly, exhibiting one L-proximate Q0 whose folding sequence never contains some L-representative of µ(Q0) would disprove Theorem 4.10.

Watch

Extended reading notes

Core claim

Theorem 4.10 is the paper's central claim: for a finitely presented group G with rational structure (G,L), if Q0 is L-proximate with constants (k,c) and K=µ(Q0), then after finitely many iterations of Construction 4.7 the language Q_n contains L∩µ^{-1}(K), and K is L-recognisable. Each iteration adds relator cycles and inverse-pair cycles at every state, folds the automaton so its language is closed under free reduction, and then determinises; the proof bounds the required number of iterations by a finite maximum of rewriting-step distances between pairs of words in a ball of radius 2k+1 and c. For submonoids of the form T*, a weaker condition called weak L-proximacy suffices, and Theorem 5.

Load-bearing premise

For the general theorems, the load-bearing premise is that the chosen regular language Q0 is L-proximate; for the surface-group examples, an additional load-bearing premise is the external small-cancellation trichotomy that every reduced diagram for uv^{-1} with u Dehn-reduced and v geodesic is a single vertex, a single 2-cell, or a ladder with the claimed rail structure—the paper invokes this without proof and only sketches the ladder argument.

Editorial extensions

If this is right

  • If a rational subset K is L-proximate with respect to some regular Q0, then K is L-recognisable: the set of L-words representing K is regular.
  • L-recognisability of a rational subset of an automatic group implies that its membership problem is decidable.
  • For a finitely generated submonoid T* that is weakly L-proximate, Theorem 5.2 provides an algorithm that computes an automaton for the L-representatives, making the membership problem constructively decidable.
  • In surface groups, any submonoid generated by words that are Dehn-reduced, or within N simultaneous Dehn-reductions of Dehn-reduced words, is L-recognisable and has constructively decidable membership; the examples constructed in Section 6.3 are not covered by earlier results on Magnus submonoids.
  • For arbitrary L-proximate rational subsets, decidability of membership follows, but constructively finding the recogniser remains open outside the submonoid case, as noted in Remark 5.4.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Since L-proximacy is in fact equivalent to L-recognisability, the paper's real contribution is a uniform construction: once proximity is known, foldings built from any generating Q0 will find the recogniser. The hard open question left implicit is how to certify L-proximacy of a given Q0 without already knowing the recogniser.
  • The surface-group criterion suggests a broader principle: in hyperbolic groups with geodesic language, any language whose words fellow-travel geodesics within a uniform bound should be weakly proximate. Extending the ladder argument beyond surface groups could yield many more decidable submonoids.
  • The halting test is tied to the flower automaton's single start-accept state. Finding an analogous completion test for general rational subsets, where start and accept states differ, is the natural next step; the paper notes only partial conditions here.
  • The folding procedure is likely to transfer to other automatic structures with well-behaved normal-form languages, such as right-angled Artin groups, where proximity could be checked through geodesic combing; the paper lists this as a direction for future work.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper extends Stallings folding techniques from subgroups to rational subsets/submonoids of automatic groups. It defines L-proximacy and weak L-proximacy for a regular language Q with respect to a rational structure (G,L), then gives an iterative rewriting-and-folding procedure; the main general theorem (Theorem 4.10) states that if Q is L-proximate then after finitely many iterations the procedure recognises all L-representatives of µ(Q), so µ(Q) is L-recognisable. For finitely generated submonoids, Theorem 5.2 gives a halting test that turns the procedure into an effective algorithm under the weaker weak-L-proximacy hypothesis. The final section applies these results to surface groups, using small cancellation theory to show that Dehn-reduced languages are weakly L-proximate with respect to geodesics, yielding a criterion (Theorem 6.11) and examples of submonoids with constructively decidable membership problem.

Significance. If the results are correct, the paper gives a genuine extension of the Kharlampovich–Miasnikov–Weil framework from L-quasi-convex subgroups to rational subsets satisfying a stronger convexity-type condition. Theorem 4.10 is a nontrivial algorithmic derivation, not a restatement of the definitions, and Theorem 5.2 supplies a concrete halting test. The surface-group application is a useful source of new examples of submonoids with decidable membership. The paper is also honest about limitations: the general rational-subset case has no halting test, and some questions are left open. The main weaknesses are three underproved but load-bearing points: Lemma 4.1 is proved only by example, Lemma 6.8's ladder fellow-travel bound is only sketched, and Proposition 6.12 is stated without proof. These are fixable, and the core folding theorems are not affected by the surface-group issues.

major comments (3)
  1. [§4.1, Lemma 4.1] This lemma is load-bearing: it is used in Lemma 4.4 to convert alternating eDR/eDred rewriting into eDR^k followed by eDred^*, and hence in Proposition 4.8, Corollary 4.9, and Theorem 4.10. The proof is only an illustrative example, with the statement that the general proof follows the same lines. As written this is not a proof. Please provide a complete argument (or a reference) covering arbitrary relator insertions and arbitrary free reductions.
  2. [§6.2, Lemma 6.8] The reduction of the diagram to a vertex, a single 2-cell, or a ladder is plausible, but the subsequent passage from the ladder structure to the numerical fellow-travel bounds is asserted without proof. In the ladder case the assertions that every cell meets both rails, that cells along u contribute at most 2g boundary edges, and that internal arcs have length at most 1 are not shown to imply that every vertex of u is within g+1 of v and that the relevant vertices of v are at most 2g−2 edges apart. A rigorous geometric argument (or a precise statement of the result being quoted) is needed, since Lemma 6.9 and all of §6.3 depend on it.
  3. [§6.3, Proposition 6.12] This proposition is stated without proof. It is used to guarantee that T* is Dehn-reduced, hence weakly L-proximate, and is the basis for the examples in Example 6.13. Please supply a proof that the three conditions prevent the appearance of any Dehn-reducible subword in arbitrary concatenations of words of T, including subwords that cross concatenation boundaries.
minor comments (4)
  1. [Definition 3.1 and 3.2] The reparametrisation function f is defined on [0,|w|], but the inequality is written 'for all 0≤i≤|w′|'; it should be 0≤i≤|w|. The same mis-indexing appears in Definition 3.2.
  2. [§6.3, proof of Theorem 6.11] In the proof, 'v asynchronously (g+1)-fellow travels with v' should presumably read 'v ... with w'; otherwise the variable is confused.
  3. [§2.1 and throughout] Several typos: 'worda' for 'words' in §2.1; 'Theorem 3.1' in the first line of §3 should be 'Definition 3.1'; Lemma 4.4 refers to 'Theorem 4.1' where Lemma 4.1 is meant.
  4. [§3.6, proof of Proposition 3.6] The equality 'w′_{g(i)} = w″_i' is equality of group elements/vertices, not of words. Please clarify notation to avoid a formal error.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the folding theorem is a genuine algorithmic derivation and the surface-group part rests on external small-cancellation results, not on self-citation.

full rationale

The central claim (Theorem 4.10) is not a restatement of its hypothesis. Definition 3.1 of L-proximacy supplies, for each L-representative w of K=µ(Q0), a Q0-word w' with asynchronous k-fellow-travel and asynchronicity bounded by c. The proof then decomposes w' into chunks γ(i) of length ≤c, connects the k-close vertices by geodesics δ(i), and forms loops α(i)=δ(i-1)^{-1}w(i)δ(i) of length ≤2k+1. Because G is finitely presented, only finitely many such pairs (α,γ) exist, so a single n bounds the number of rewriting steps needed for all of them; Lemma 4.11 concatenates this bound and the Benois folding closure converts α into w. Thus the full set L∩µ^{-1}(K) is shown to lie in Q_n. Proposition 3.8's 'if' direction is immediate, but its 'only if' direction is explicitly deferred to Theorem 4.10 and is not used as input. No parameter is fitted and no 'prediction' is forced by construction. The only citation with author overlap is [12] (Holt–Rees–Röver), used for textbook automaton constructions; it is not load-bearing. The Section 6 application invokes external small-cancellation results [16,18] to prove Lemma 6.8; that lemma is only sketched, but a sketched proof of an external geometric claim is a correctness risk, not circularity, since the claimed fellow-travel bound is not assumed in the definition of weak L-proximacy. The main theorems therefore stand independently of any circular dependence.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

No free parameters are fitted; the constants k and c in the definition of L-proximacy are hypotheses of the theorems, not values chosen to force conclusions. The paper introduces two new properties (L-proximacy, weak-L-proximacy) but these are definitions of properties of given objects, not new entities.

assumptions (6)
  • domain assumption Automatic groups are finitely presented and have solvable word problem; multiplier automata exist.
    Used throughout to justify the folding procedure and the halting test; standard from [6,14].
  • standard math Benois' theorem and algorithm: free reduction of a regular language is regular, and an automaton can be constructed.
    Used in Construction 4.7; cited [1,2].
  • standard math The rewriting system eD_R ∪ eD_red is complete for the group congruence, so any two equal words can be connected by insertions of relators and partial free reductions.
    Used in Corollary 4.5 and Theorem 4.10; the proof of Lemma 4.1 is only sketched by example in the paper.
  • standard math The standard surface-group presentation satisfies C(4)-T(4), with all pieces of length 1.
    Used in Section 6 to apply the small-cancellation trichotomy; standard result.
  • domain assumption McCammond–Wise fan/ladder trichotomy [16, Thm 9.4] and Wise's shell/ladder corollary [18, Cor 2.8].
    Load-bearing external results for Lemma 6.8; not proved in this paper.
  • standard math Dehn's algorithm/rewriting system for surface groups and the fact that genus-g surface groups (g>1) are hyperbolic and automatic with geodesic language.
    Used throughout Section 6; standard.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Stallings foldings for rational subsets of automatic groups." pith.science (2026). https://pith.science/paper/NBCKGK5V

@misc{pith2026260726284,
  author       = {Pith},
  title        = {Pith review of: Stallings foldings for rational subsets of automatic groups},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NBCKGK5V}},
  note         = {Machine review of arXiv:2607.26284}
}
abstract

Let $G$ be an automatic group with associated regular language $L$. We describe a procedure for constructing an automaton which recognises elements of a given submonoid or rational subset $K$ of $G$. This builds on work of Kharlampovich, Miasnikov and Weil, on the case where $K$ is a subgroup of $G$. Our construction succeeds, after sufficiently many iterations, whenever $K$ satisfies a certain convexity property, which we call $L$-proximity. We show how to test whether the construction is complete in the case that $K$ is a submonoid; we have no such test for the general case of a rational subset $K$. We focus particularly on the case of a surface group $G$ of genus $g>1$, where $L$ is the language of geodesic words in the standard generators. We use small cancellation theory to obtain a method for constructing $L$-recognisable submonoids of $G$.

Figures

Figures reproduced from arXiv: 2607.26284 by the authors.

Figure 1
Figure 1. L-representatives of a rational subset: L and Q are regular subsets of (S ±) ∗ and the projection µ: L → G makes (G, L) a rational structure. The subset K = µ(Q) is rational in G, and its set of L-representatives is µ −1 (K) ∩ L which is not, in general, either regular or equal to Q ∩ L. Proof. Let h ∈ G. Lemma 3.10 of [14] implies that it is possible algorithmically to construct an automaton Bh which accepts precis… view at source ↗
Figure 2
Figure 2. Illustration of the paths in the Cayley graph defined in Theorem 3.1. In particular, w and w ′ asynchronously fellow travel (see [6] for a definition), with a (linear) restriction on their asynchronicity. A weaker notion of convexity, useful when working with submonoids of groups, is obtained by dropping the constant c: Definition 3.2. Let (G, L) be a rational structure for a group G = ⟨S⟩, and let Q be a regular su… view at source ↗
Figure 3
Figure 3. The paths defined in the proof of Theorem 3.6. define tj to be a word of minimal T-length in (T ±) ∗ such that µ(tj ) = h −1 j−1hj . Then setting qj = t1 · · ·tj for each j (with q0 = ϵ), we see that µ(qj ) = hj for all j. Since dS(hj , hj+1) ≤ 2k + 1, we see that |h −1 j hj+1|S ≤ 2k + 1, and hence that |h −1 j hj+1|T ≤ c. Since the elements tj have minimal T-length by assumption, it follows that |tj |S ≤ cℓ for all… view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: The paths defined in Theorem 3.7 At the end of Section 2 we pointed out that a subgroup is L-quasi-convex if and only if it is L-recognisable. Similarly, we have the following [PITH_FULL_IMAGE:figures/full_fig_p011_4.png]
Figure 5
Figure 5. Figure 5: Notation for the proof of Theorem 4.10 See [PITH_FULL_IMAGE:figures/full_fig_p016_5.png]
Figure 6
Figure 6. Figure 6: Three examples of words in Σ2 depicted as paths (in bold) along the Cayley graph of Σ2, which tessellates the hyperbolic plane with octagons. The leftmost path is not Dehn-reduced be￾cause it exhibits backtracking, the middle one is not Dehn-reduced because it goes aro…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 1 linked inside Pith

  1. [1]

    Silva,Rational subsets of groups, Handbook of Automata Theory (Jean- ´Eric Pin, ed.), vol

    Laurent Bartholdi and Pedro V. Silva,Rational subsets of groups, Handbook of Automata Theory (Jean- ´Eric Pin, ed.), vol. 2, EMS Press, Z¨ urich, Switzerland, 2021, pp. 841–869

    2021

  2. [2]

    Mich` ele Benois,Parties rationelle du groupe libre, C. R. Acad. Sci. Paris, S` er. A269(1969), 1188–1190

    1969

  3. [3]

    Michael Ben–Zvi, Robert Kropholler, and Rylee Alanza Lyman,Folding-like techniques for CAT(0)cube complexes, Math. Proc. Cambridge Philos. Soc.173(2022), no. 1, 227–238

    2022

  4. [4]

    Bridson and Andr´ e Haefliger,Metric spaces of non-positive curvature, Grundlehren der mathematischen Wissenschaften, Springer Berlin, Heidelberg, 2011

    Martin R. Bridson and Andr´ e Haefliger,Metric spaces of non-positive curvature, Grundlehren der mathematischen Wissenschaften, Springer Berlin, Heidelberg, 2011

    2011

  5. [5]

    Pallavi Dani and Ivan Levcovitz,Subgroups of right-angled Coxeter groups via Stallings-like techniques, J. Comb. Algebra5(2021), no. 3, 237–295. 24 L. ASENCIO-MART ´IN, J. BRITNELL, A. DUNCAN, D. FRANCOEUR, AND S. REES

    2021

  6. [6]

    D. B. A. Epstein, J. W. Cannon, D. F. Holt, S. V. F. Levy, M. S. Paterson, and W. P. Thurston,Word processing in groups, CRC Press, 1992

    1992

  7. [7]

    Gray,Magnus submonoids and membership prob- lems in one-relator, surface and hyperbolic groups, September 2025, preprint at https://arxiv.org/abs/2412.04932

    Islam Foniqi and Robert D. Gray,Magnus submonoids and membership prob- lems in one-relator, surface and hyperbolic groups, September 2025, preprint at https://arxiv.org/abs/2412.04932

    arXiv 2025

  8. [8]

    S. M. Gersten and H. B. Short,Rational subgroups of biautomatic groups, Ann. of Math.134 (1991), no. 1, 125–158

    1991

Show all 18 references
  1. [9]

    Ghys and P

    E. Ghys and P. de la Harpe (eds.),Hyperbolic groups, Progress in Mathematics, vol. 111, Birkh¨ auser Basel, 1990

    1990

  2. [10]

    Math.130(1997), no

    Rostislav Grigorchuk and Tatiana Nagnibeda,Complete growth functions of hyperbolic groups, Invent. Math.130(1997), no. 1, 159–188

    1997

  3. [11]

    Hermiler,Rewriting systems for coxeter groups, J

    Susan M. Hermiler,Rewriting systems for coxeter groups, J. Pure Appl. Algebra92(1994), no. 2, 137––148

    1994

  4. [12]

    Holt, Sarah Rees, and Claas E

    Derek F. Holt, Sarah Rees, and Claas E. R¨ over,Groups, languages and automata, London Mathematical Society Student Texts, Cambridge University Press, Cambridge, 2017

    2017

  5. [13]

    Hopcroft and Jeffrey D

    John E. Hopcroft and Jeffrey D. Ullman,Introduction to automata theory, languages, and computation, Addison-Wesley Series in Computer Science, Addison-Wesley, 1979

    1979

  6. [14]

    Algebra488(2017), 442–483

    Olga Kharlampovich, Alexei Miasnikov, and Pascal Weil,Stallings graphs for quasi-convex subgroups, J. Algebra488(2017), 442–483

    2017

  7. [15]

    R. C. Lyndon and P. E. Schupp,Combinatorial group theory, Springer-Verlag, Berlin, Heidel- berg, New York, 1977

    1977

  8. [16]

    McCammond and Daniel T

    Jonathan P. McCammond and Daniel T. Wise,Fans and ladders in small cancellation theory, Proc. London Math. Soc.84(2002), no. 3, 599–644

    2002

  9. [17]

    Stallings,Topology of finite graphs, Invent

    John R. Stallings,Topology of finite graphs, Invent. Math.71(1983), 551–565

    1983

  10. [18]

    Wise,Cubulating small cancellation groups, Geom

    Daniel T. Wise,Cubulating small cancellation groups, Geom. Funct. Anal.14(2004), no. 1, 150–214. School of Mathematics, Statistics and Physics, Newcastle University, Newcastle upon Tyne NE1 7RU, United Kingdom Email address:L.Asencio-Martin2@newcastle.ac.uk School of Mathemati...

    2004

Pith tools

Reviewed August 1, 2026 · model on record in the stance chip above.