{"id":"a789f1b1-8f87-4a77-bdcc-b7cf6fe12c55","arxiv_id":"2607.26284","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A folding procedure constructs automata that recognize the L-representatives of any L-proximate rational subset of an automatic group, and yields decidable-membership submonoids of surface groups.","lead":"The authors extend Stallings' folding algorithm from subgroups to arbitrary rational subsets of automatic groups, building a finite automaton that recognizes all L-representatives of the subset whenever a geometric 'L-proximity' condition is met. They then use small cancellation theory to exhibit new submonoids of surface groups whose membership problem is decidable.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The paper's advertised surface-group examples rest on Lemma 6.8, whose ladder fellow-travel bound is only sketched and depends on external small-cancellation results; a failure there would leave §6.3 unsupported, though Theorems 4.10 and 5.2 stand.","rationale":"I agree with the reader's verdict. The core folding theorems (4.10 and 5.2) appear mathematically sound: the omitted proof of Lemma 4.1 is a presentation gap, but the statement is a standard diamond property and can be filled without changing the argument. The surface-group application is the least secure part of the paper because it combines unproved external small-cancellation theorems with a numerical fellow-travel bound that is only sketched. Since the reader already set a CONDITIONAL verdict and identified the same weakest assumption, no change is needed. The concern is load-bearing for the paper's advertised new examples, not for the main theoretical contribution.","tokens_in":21773,"tokens_out":34228,"duration_ms":281006,"concrete_test":"For genus 2, enumerate all Dehn-reduced words u over the standard generators with |u| ≤ 30 (using Dehn's algorithm), compute a geodesic representative v with v =_G u, and check whether u asynchronously 3-fellow-travels with v with asynchronicity ≤ 4 (g+1=3, 2g=4). A single violation would refute Lemma 6.8; if none appears, the bound is supported for the tested range, though a complete proof of the ladder geometry would still be needed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing concern is the surface-group application in Section 6, specifically Lemma 6.8. The lemma asserts that for a Dehn-reduced word u and a geodesic v with the same group element, a reduced Van Kampen diagram for uv^{-1} is a single vertex, a single 2-cell, or a ladder, and that in the ladder case the rails yield an asynchronous (g+1)-fellow-travel bound with asynchronicity at most 2g. This is the step that makes Dehn-reduced languages weakly L-proximate (Lemma 6.9), and hence underpins all the new submonoid examples in §6.3. The proof is only a sketch: it invokes [16, Thm 9.4] and [18, Cor 2.8] for the trichotomy, but the passage from 'ladder' to the specific numerical bounds is asserted without a detailed geometric argument. In particular, the claims that every cell of the ladder intersects both rails, that cells along u contribute at most 2g boundary edges, and that these facts imply every vertex of u is within g+1 of v are not demonstrated. If any of these geometric assertions fails—e.g., if a ladder cell has a long boundary arc on one rail, or if the distance between corresponding rail vertices exceeds g+1—then Dehn-reduced languages need not be weakly L-proximate, and the submonoid examples of §6.3 would be unsupported. The core folding theorems (4.10, 5.2) are independent of this section, so the main theoretical claim is not at risk.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":22061,"tokens_out":27093,"duration_ms":236156,"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":[{"comment":"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.","section":"§4.1, Lemma 4.1"},{"comment":"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.","section":"§6.2, Lemma 6.8"},{"comment":"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.","section":"§6.3, Proposition 6.12"}],"minor_comments":[{"comment":"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.","section":"Definition 3.1 and 3.2"},{"comment":"In the proof, 'v asynchronously (g+1)-fellow travels with v' should presumably read 'v ... with w'; otherwise the variable is confused.","section":"§6.3, proof of Theorem 6.11"},{"comment":"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.","section":"§2.1 and throughout"},{"comment":"The equality 'w′_{g(i)} = w″_i' is equality of group elements/vertices, not of words. Please clarify notation to avoid a formal error.","section":"§3.6, proof of Proposition 3.6"}],"recommendation":"major_revision","confidential_remarks":"The core algorithmic results (Theorems 4.10 and 5.2) appear coherent and interesting; I see no circularity or artificial fitting. The main risk is the incompleteness of Lemma 4.1 and of the surface-group geometric bounds in Lemma 6.8 and Proposition 6.12. If those are filled in carefully, the paper should be acceptable; the theoretical core does not depend on the surface-group section."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"What you should know: this is a serious extension of the Kharlampovich–Miasnikov–Weil folding framework from subgroups to rational subsets and submonoids. The main object, L-proximacy, is a reasonable convexity condition, and the two central results—Theorem 4.10, which says that L-proximate rational subsets are L-recognisable after finitely many foldings, and Theorem 5.2, which gives a halting test for submonoids—are new and appear to be proved correctly. The core derivation does not hide circularity: it starts with L-proximacy and actually constructs the recognizing automaton. The surface-group application is the part that should worry you. Lemma 6.8, which claims that a Dehn-reduced word and a geodesic for the same element in a surface group fellow-travel with a (g+1)-bound, is load-bearing for all the new submonoid examples, and its proof is only a sketch. The trichotomy from McCammond–Wise and Wise is invoked, but the passage from 'ladder' to the specific numerical bound on asynchronicity is asserted rather than demonstrated. If that lemma fails, the examples in Section 6.3 have no support. The core theorems do not depend on it, so the paper's central contribution is not at risk. There are also smaller issues. Lemma 4.1, which shows that rewriting steps can be interchanged, is not actually proved—the authors give an example and say the general proof is tedious. That needs to be supplied. Definition 3.1 has a mis-indexed inequality: the fellow-travel condition should hold for all i up to |w|, not |w'|. The cross-referencing is a mess in places. These are cosmetic or minor, but they make the paper harder to check. The authors are honest about limitations: they flag that they have no halting test for general rational subsets, and they ask Question 3.10 about whether weak L-proximacy can be replaced by T*-proximacy. That is good practice. Who should read this: anyone working on rational subsets or Stallings foldings in automatic groups. It deserves a serious referee and likely publication after revision, but the referee should demand a real proof of Lemma 4.1 and a detailed geometric argument for Lemma 6.8. Send it out.","headline":"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.","tokens_in":22674,"tokens_out":1691,"would_cite":true,"duration_ms":18435,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["20F10","20F65","68Q45"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["automatic groups","rational subsets","Stallings foldings","L-proximacy","L-recognisable subsets","submonoid membership","surface groups","small cancellation"],"falsifier":"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.","tokens_in":21562,"feed_emoji":"🔁","tokens_out":8205,"duration_ms":74044,"temperature":0.7,"pith_summary":"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.","feed_headline":"Iterated folding recognises proximate rational subsets","feed_subtitle":"The procedure terminates with an automaton for exactly the L-words of K; submonoids get a halting test.","key_machinery":"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","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["Folding recognizes rational subsets that are L-proximate","Iterated Stallings folding, with halting only for submonoids","L-proximity ensures folding completion, no test for rational sets","Automatic groups: folding automata for proximate subsets","Submonoid test, rational subset gap in folding recognition"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Folding recognizes rational subsets that are L-proximate","Iterated Stallings folding, with halting only for submonoids","L-proximity ensures folding completion, no test for rational sets","Automatic groups: folding automata for proximate subsets","Submonoid test, rational subset gap in folding recognition"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000433,"raw_usage":{"total_tokens":2034,"prompt_tokens":725,"completion_tokens":1309,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":469,"completion_tokens_details":{"reasoning_tokens":1225}},"tokens_in":469,"tokens_out":1309,"duration_ms":9549,"temperature":1.0,"reasoning_tokens":1225,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T00:16:55.424958+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}