{"id":"3e247ab2-4862-4d55-baea-85b7806cf206","arxiv_id":"2412.09688","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A Boolean 1D TQFT-with-defects construction for regular languages is shown to be functorial under transducers and generalized to context-free grammars via an operadic Chomsky-Schützenberger theorem.","lead":"This paper extends a recent construction that turns finite automata, machines that recognize regular languages, into one-dimensional topological quantum field theories with defects. It proves the construction behaves well under language transformations and extends it to more complex context-free grammars through categorical tools.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Modified pullback in Def. 3.2 uses 'largest invariant subspace,' but sink states are invariant, so α^*ΦM≠Φ_{α^{-1}(M)}; this breaks the transducer natural transformations on which Prop. 4.10 relies.","rationale":"The paper's central claim rests on two pillars: the operadic TQFT construction for categorical context-free grammars (Proposition 4.9) and the reduction to tree-contour grammars via functoriality under transducers (Proposition 4.10). Proposition 4.9 is plausible and largely self-contained. The reader located the weak point in the imported Melliès–Zeilberger theorem. I agree that the dependence on [17] needs to be made explicit, but a more immediate internal flaw appears before any appeal to [17]: Definition 3.2's 'largest invariant subspace' does not match the automaton-theoretic pullback used throughout Sections 3 and 4. In the Boolean semiring, zero-image basis vectors are invariant, so the largest invariant subspace retains exactly the states that the pullback should discard. The small three-state example above shows the mismatch concretely. Since Theorem 4.6 relies on this definition, the functoriality under transducers needed by Proposition 4.10 is not proved as written. The flaw is repairable, and the overall approach may still be correct, so the verdict remains CONDITIONAL rather than moving to REJECT. The manuscript should repair Definition 3.2, re-verify Lemma 3.2, Theorem 3.3, and Theorem 4.6, and then state precisely what is imported from [17].","tokens_in":25644,"tokens_out":12428,"duration_ms":137226,"concrete_test":"Recompute Lemma 3.2 with the small automaton M over {A,B} with states {s,t,u}, transitions s--A-->t, t--B-->s, u--B-->u, and α:{a}*→{A,B}* given by α(a)=A. Under Definition 3.2, compute the largest T_A-invariant subspace of B^{{s,t,u}}: it is B^{{s,t,u}} because T_A(δ_u)=0. Compare with Φ_{α^{-1}(M)}(+)=B^{{s,t}} as required by Lemma 3.2. If the two differ, Definition 3.2 must be replaced by the submodule generated by the images of the T_{α(a)} in Theorem 3.3 and Theorem 4.6; otherwise the transducer natural transformations do not have the claimed domain and codomain.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Definition 3.2 defines the modified pullback α^*Φ(+) as the largest subspace invariant under all operators Φ(c_{α(a)}). Under that definition, any basis vector sent to 0 is invariant, so every state not hit by an α-transition remains in the pullback. This contradicts Lemma 3.2, which identifies α^*ΦM with Φ_{α^{-1}(M)}. Concretely, let M have states {s,t,u} with transitions s--A-->t, t--B-->s, u--B-->u, and let α(a)=A. Then Q_{M,α}={s,t}, so Φ_{α^{-1}(M)}(+)=B^{{s,t}}, but the largest T_A-invariant subspace of B^{{s,t,u}} is the whole space, since T_A(δ_u)=0. Thus α^*ΦM(+)≠Φ_{α^{-1}(M)}(+), and the natural transformations in Theorem 3.3 are not well-defined as stated. Theorem 4.6 invokes the same modified pullback for categorical context-free grammars, so the functoriality under transducers used in Proposition 4.10 is not established even if the Melliès–Zeilberger theorem [17] is fully correct. The issue is internal and repairable: the pullback should be defined using the submodule generated by the images of the pulled-back defect operators (the states occurring as endpoints of α-transitions), not the largest invariant subspace.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper extends the Boolean 1D TQFT-with-defects construction of Gustafson, Im, Kaldawy, Khovanov, and Lihn from finite state automata to a category whose morphisms are transducers, then to categorical finite state automata and to categorical context-free grammars viewed as morphisms of colored operads P: O_S → W_C. The advertised results are functoriality under transducers (Theorems 3.3, 4.3, 4.6), a cohomological interpretation of certain subregular language classes (Section 3.3), and a reduction of all categorical context-free grammar TQFTs to tree-contour grammars via the Melliès–Zeilberger version of the Chomsky–Schützenberger theorem (Proposition 4.10). The paper is exploratory and contains a number of local gaps and typos, but its intended categorical/operadic bridge between automata theory and defect TQFTs is clear.","tokens_in":25899,"tokens_out":17114,"duration_ms":168249,"significance":"If the main theorems were correct, the paper would give a useful functorial and operadic framework for the language–TQFT correspondence: transducer morphisms would lift to natural transformations, context-free grammars would be encoded as operad maps, and the Chomsky–Schützenberger theorem would reduce the whole construction to tree-contour grammars. The paper is explicit, has no fitted parameters, and transparently relies on the external theorem [17]. However, as written, the central functoriality statements are not established because of an incorrect modified pullback definition, and the subregular cohomology claim is not valid for arbitrary automata computing a language. These are local, repairable defects, so the framework remains promising, but the current version cannot serve as a rigorous foundation for the context-free results.","major_comments":[{"comment":"Definition 3.2 defines the modified pullback α^*Φ(+) as the largest subspace invariant under all operators Φ(c_{α(a)}), but Lemma 3.2 and the proof of Theorem 3.3 require this subspace to be B^{Q_{M,α}}, the span of states occurring in α-transitions. These are not equal: if a state is not the source of any α(a)-transition, its basis vector is annihilated by all T_{α(a)} and hence lies in every invariant subspace. Concretely, let M have states {s,t,u}, transitions s--A-->t, t--B-->s, u--B-->u, and let α(a)=A. Then Q_{M,α}={s,t}, so Lemma 3.2 identifies α^*Φ_M(+) with B^{{s,t}}, but the largest T_A-invariant subspace of B^{{s,t,u}} is the whole space because T_A(δ_u)=0. The proof of Theorem 3.3 explicitly uses the equality α^*Φ_M = Φ_{α^{-1}(M)}, so Theorem 3.3 is not established as stated. The repair is local: replace 'largest invariant subspace' by the Boolean submodule spanned by all states that occur as sources or targets of transitions labelled by α(a), and then re-check the naturality argument.","section":"§3.2, Definition 3.2 and Lemma 3.2"},{"comment":"The inference from inadmissible k-factors to vanishing of products of defect operators is not valid for arbitrary FSAs computing the given language. Earlier in §3.2 the paper correctly stresses that the TQFT depends on the automaton, not only the language, yet §3.3 asserts for (AB)^n that 'TB is a coboundary operator (T_B^2=0) on any of the spaces Φ_M(ϵ), and so is TA.' This is false in general. Add to the standard two-state automaton for (AB)^n an extra state r with a transition r--A-->r (and, if desired, make r reachable by adding q0--A-->r and keeping q0 final); the recognized language is unchanged, but T_A^2(δ_r)=δ_r, so T_A is not square-zero. The cohomological structure of SL2 languages therefore needs an explicit hypothesis on the automaton, such as a canonical minimal automaton, together with a proof, rather than being presented as a language-level consequence.","section":"§3.3"},{"comment":"The same defect propagates to the context-free setting. Theorem 4.6 is stated using 'the modified pullbacks as in Definition 3.2', and its proof identifies Π_{Wα}Ψ_G(+) with B(X_{C,S}∩Obj(Q_T)). This is exactly the equality that fails for the largest-invariant-subspace definition. Consequently the natural transformations γ_T : Wα^*Ψ_G → Wβ^*Ψ_{G'} are not established, and Proposition 4.10, which concludes that all context-free TQFTs are determined by tree-contour grammars and functoriality under transducers, has no valid proof at present. The authors should repair Definition 3.2, or avoid modified pullbacks in this theorem, and then verify that the naturality diagram in Theorem 4.6 commutes with the corrected pullback.","section":"§4.5–4.6, Theorem 4.6 and Proposition 4.10"},{"comment":"Proposition 4.10 makes essential use of the Melliès–Zeilberger theorem [17], which is legitimate, but the proof as written does not verify that the hypotheses of Proposition 4.9 and Theorem 4.6 are met after the reduction. In particular, Theorem 4.6 assumes that α is injective on objects and that the operad map is C-chromatic, while the factorization step introduces the color-surjective morphism φCol: O_S→O_{φColS}; the argument that the original, possibly non-C-chromatic, grammar G is a transducer image of a C-chromatic tree-contour grammar is compressed into a diagram and is not self-contained. Please state the precise theorem from [17] that is being used and check the two hypotheses explicitly; otherwise Proposition 4.10 is conditional on an unstated strengthening of [17].","section":"§4.6, Proposition 4.10"}],"minor_comments":[{"comment":"In the first paragraph, 'and and additional operadic structure' contains a duplicated word that should be removed.","section":"Introduction"},{"comment":"The text repeats 'FM(+) = BQ∨' after defining FM(+)=BQ; the second occurrence should be FM(−)=BQ∨.","section":"§3.1"},{"comment":"There are numerous typos, including 'wth', 'inital', and inconsistent spelling of Melliès; a thorough proofreading pass is needed before publication.","section":"Throughout"},{"comment":"The definition of H_{ab}(Φ_M(ϵ),T) := Ker(T_a)/Image(T_b) uses quotients and kernels of Boolean semimodules without specifying the relevant universal properties; this should be clarified, especially since the paper otherwise works with spans of B-modules.","section":"§3.3"},{"comment":"The proof of Proposition 2.4 is very terse; in particular, the transition from the automaton for α^{-1}(L)∩L_reg to the automaton for β(α^{-1}(L)∩L_reg) is described only informally via 'subdivisions' and should be formalized with a precise definition of the intermediate state set Q'.","section":"§2.2"}],"recommendation":"major_revision","confidential_remarks":"The core issue is that Definition 3.2 is internally inconsistent with Lemma 3.2, and the same error propagates into Theorem 4.6. This is a load-bearing point, but it is local and repairable, so I recommend major revision rather than rejection. The Section 3.3 overclaim about arbitrary automata should also be corrected or explicitly restricted. I have no concerns about novelty or citation practices; the reliance on [17] is appropriate, provided the exact hypotheses are stated."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe paper does something genuinely new: it makes the automaton-to-Boolean-1D-TQFT construction functorial with respect to transducers, and then extends the whole picture to context-free grammars via the Melliès–Zeilberger categorical Chomsky–Schützenberger theorem. The operadic formalism in Sections 4.5–4.6 is a real step beyond the existing literature, and the writing is clear about what is being assumed.\n\nThe soft spots are serious, though. Definition 3.2 defines the modified pullback α*Φ as the largest subspace invariant under the defect operators. As the stress-test note observes, this does not match Lemma 3.2's identification with Φ_{α^{-1}(M)}. With a sink state u, the largest invariant subspace is the whole space, because T_A(δ_u)=0, so every basis vector is invariant; the intended subspace consists only of states that occur as endpoints of α-transitions. That discrepancy breaks the natural transformations in Theorem 3.3 and Theorem 4.6, and those natural transformations are exactly what Proposition 4.10 relies on to reduce all context-free TQFTs to tree-contour grammars. The fix is straightforward—define the pullback as the submodule generated by the images of the pulled-back defect operators—but as written the central functoriality claim is not established.\n\nSection 3.3 overreaches in a different way. The claim that a non-admissible 2-factor implies T_a T_{a'} = 0 is not a property of the language; it depends on the chosen automaton. A non-minimal automaton for (AB)^n can have extra states that make the product nonzero. The cohomological structure is a feature of the specific TQFT, not of the SL2 language, and the section needs to say so.\n\nAlso, the context-free reduction itself is largely imported from [17]. That is fine, but the authors should be clearer about which statements are new and which are directly taken from Melliès–Zeilberger.\n\nDespite these problems, the paper deserves a serious referee. The topic is timely, the categorical framework is appropriate, and the main bug is genuinely repairable. With the pullback fixed and the subregular section corrected, this could become a useful organizing contribution. My own verdict would be revise-and-resubmit, not accept.\n\nI would bring it to reading group only if people want to wrestle with the pullback issue. I would not cite it in its current form.","headline":"A promising extension of the automata-to-TQFT program with a real, fixable bug in the modified pullback definition; the central functoriality claim does not currently hold as stated.","tokens_in":26502,"tokens_out":3317,"would_cite":false,"duration_ms":33480,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q45","18M85","81T45"],"pacs":[],"model":"deepseek-v4-flash","headline":"A functorial construction turns context-free grammars into 1D TQFTs with defects, reducing them to tree-contour grammars.","keywords":["Boolean 1D TQFTs with defects","finite state automata","context-free grammars","Chomsky-Schützenberger theorem","categorical transducers","tree-contour grammars","colored operads","subregular languages"],"falsifier":"Compute, for the grammar $S\\to aSbS\\mid \\epsilon$, the operator $T_{a\\square b}$ from equation (4.9) and compare it with the operator obtained by first mapping this grammar through its contour functor $\\tau_G$ to a tree-contour grammar and then applying the transducer of Proposition 4.10; any difference on a basis state $\\delta_C$ would falsify the main reduction. Alternatively, check that the natural transformation $\\gamma_T$ of Theorem 4.6 commutes for a simple two-state transducer; a failure on a cup or half-line cobordism would falsify the claimed functoriality.","tokens_in":25390,"feed_emoji":"🧵","tokens_out":8142,"duration_ms":72344,"temperature":0.7,"pith_summary":"The paper argues that the recently introduced assignment of Boolean 1D TQFTs with defects to finite automata is not ad hoc: it is functorial under transducers, and it extends from regular to context-free grammars. The key move is to use a categorical version of the Chomsky–Schützenberger theorem, in which every context-free grammar is represented as a transducer image of a tree-contour grammar, the categorical analogue of the Dyck language. If correct, the TQFT associated to any context-free grammar is completely determined by the TQFTs of tree-contour grammars plus functoriality under transducers. The paper also shows that certain subregular language classes, such as strictly local and locally testable languages, leave cohomological or global traces on the TQFT side.","feed_headline":"Context-free grammars become 1D TQFTs via tree contours","feed_subtitle":"This ties formal languages to topological field theories, with tree-contour grammars as the universal building block.","key_machinery":"The central objects are the colored operad of spliced arrows $\\mathcal{W}_{\\mathcal{C}}$, whose operations are words $w_0\\square w_1\\square\\cdots\\square w_n$ with square gaps as inputs, and the contour category $\\mathrm{Cont}(\\mathcal{O}_{\\mathcal{S}})$, whose arrows trace the contours of trees in a free operad and whose associated tree-contour grammars are the categorical Dyck languages. A context-free grammar is encoded as a morphism of operads $P:\\mathcal{O}_{\\mathcal{S}}\\to\\mathcal{W}_{\\mathcal{C}}$, and the categorical Chomsky–Schützenberger theorem factors any such $P$ through the universal tree-contour morphism $\\mathcal{O}_{\\mathcal{S}}\\to\\mathcal{W}_{\\mathrm{Cont}(\\mathcal{O}_{\\mathcal{S}})}$ via a functor $\\tau_G$. The TQFT side is carried by the colored operad $\\mathcal{O}_{\\mathrm{Cob},\\mathcal{C}}$ of 1D cobordisms with defects and rectangular boxes cut out, composed by plugging matching boundary data; Proposition 4.9 converts a grammar into a morphism $\\Xi_G:\\mathcal{O}_{\\mathrm{Cob},\\mathcal{C}}\\to\\mathcal{O}_{\\mathcal{B}\\text{-Mod}}$, and Proposition 4.10 uses the contour factorization together with transducer naturality to reduce this morphism to tree contours.","core_discovery":"On the paper's own terms, the central discovery is that the passage from machines and grammars to 1D TQFTs with defects is a structural functor rather than a collection of examples. For finite automata, a transducer between automata induces a natural transformation between the associated Boolean 1D TQFTs with defects, after replacing the target category by spans of Boolean semimodules and using modified pullbacks. For categorical context-free grammars, seen as operad homomorphisms $P:\\mathcal{O}_{\\mathcal{S}}\\to\\mathcal{W}_{\\mathcal{C}}$, the same functoriality holds; the associated TQFT becomes a morphism of colored operads, from an operad of 1D cobordisms with defects to an operad of Boolean semimodule operations. The categorical Chomsky–Schützenberger theorem then yields Proposition 4.10: every such TQFT is completely determined by its values on tree-contour grammars and by functoriality under transducers. Additionally, strictly local languages produce cohomological structures from forbidden factors, while locally testable languages require a global cobordism-level condition.","pith_inferences":["If the reduction is made constructive, it suggests an algorithm for computing a context-free TQFT by first computing the tree-contour TQFT and then applying the transducer, potentially simplifying semiring parsing of context-free languages.","The cohomological structures attached to strictly local languages may be invariants of the language rather than the automaton; checking whether two minimal automata for the same language yield isomorphic cohomology would be a direct test.","The same operadic machinery may extend to higher-dimensional automata and 2D TQFTs with defects, where Frobenius algebra descriptions could give algebraic invariants; the paper itself lists this as future work.","Locally testable languages' global cobordism condition resembles a cohomology of the endomorphism monoid action, and making that precise could give a model-theoretic-to-TQFT dictionary for subregular classes beyond SL and LT."],"forward_implications":["For every categorical context-free grammar, the associated Boolean 1D TQFT with defects is determined by the tree-contour grammar of its species and the transducer realizing the grammar.","Strictly local languages of order 2 give cohomological structures $H_{ab}=\\ker(T_a)/\\operatorname{im}(T_b)$ for non-admissible factors, and higher-order strictly local languages give analogous structures for forbidden $k$-factors.","Locally testable languages cannot be captured by local composition of defects; they require the global set of cobordisms containing required factors, with commuting actions of the two endomorphism monoids.","Transducer morphisms between automata become natural transformations between TQFTs, so the TQFT construction is a functor from automata and cobordisms to spans of Boolean semimodules.","The operadic reformulation allows composition of defect TQFTs by plugging cobordisms into boxes, yielding a compositional calculus for context-free language TQFTs."],"supporting_citations":[{"why":"Supplies the Boolean 1D TQFT-with-defects construction for finite automata that this paper makes functorial and extends to grammars.","marker":"[10]"},{"why":"States the categorical Chomsky–Schützenberger theorem and the factorization through tree-contour grammars on which Proposition 4.10 directly rests.","marker":"[17]"},{"why":"Introduces categorical finite automata and categorical context-free grammars as operad morphisms, including the transducer action used throughout Section 4.","marker":"[16]"},{"why":"Constructs the category of formal languages with rational transductions and the composition law that the automaton category and its transducer morphisms mirror.","marker":"[7]"},{"why":"Proves that every rational transduction is computed by a transducer, grounding the correspondence action on automata used in Theorem 3.3.","marker":"[1]"},{"why":"Gives the original Chomsky–Schützenberger reduction of context-free languages to Dyck languages, whose categorical analogue is the tree-contour representation.","marker":"[5]"}],"fun_headline_variants":["Formal languages become TQFTs via a functorial construction","Tree-contour grammars generate all 1D TQFTs from languages","Transducers induce natural maps between language-TQFTs","Operads unify context-free grammars and TQFT defects"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is the categorical Chomsky–Schützenberger theorem itself: every categorical context-free grammar must factor through a tree-contour grammar by a functor and be realizable as a transducer image of a color-injective tree-contour grammar; if that companion theorem fails, the paper's reduction to tree-contour TQFTs collapses.","fun_headline_variants_meta":{"raw":{"variants":["Formal languages become TQFTs via a functorial construction","Tree-contour grammars generate all 1D TQFTs from languages","Transducers induce natural maps between language-TQFTs","Operads unify context-free grammars and TQFT defects"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000221,"raw_usage":{"total_tokens":1432,"prompt_tokens":907,"completion_tokens":525,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":523,"completion_tokens_details":{"reasoning_tokens":448}},"tokens_in":523,"tokens_out":525,"duration_ms":4942,"temperature":1.0,"reasoning_tokens":448,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T16:51:10.752091+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute, for the grammar $S\\to aSbS\\mid \\epsilon$, the operator $T_{a\\square b}$ from equation (4.9) and compare it with the operator obtained by first mapping this grammar through its contour functor $\\tau_G$ to a tree-contour grammar and then applying the transducer of Proposition 4.10; any difference on a basis state $\\delta_C$ would falsify the main reduction. Alternatively, check that the natural transformation $\\gamma_T$ of Theorem 4.6 commutes for a simple two-state transducer; a failure on a cup or half-line cobordism would falsify the claimed functoriality.","supporting_citations":[{"cited_title":"Automata and one-dimensional TQFTs with defects","cited_arxiv_id":"2301.00700","evidence_quote":"Supplies the Boolean 1D TQFT-with-defects construction for finite automata that this paper makes functorial and extends to grammars."},{"cited_title":"Parsing as a lifting problem and the Chomsky-Sch\\\"utzenberger representation theorem","cited_arxiv_id":"2212.09060","evidence_quote":"Introduces categorical finite automata and categorical context-free grammars as operad morphisms, including the transducer action used throughout Section 4."},{"cited_title":"Formal languages, spin systems, and quasicrystals","cited_arxiv_id":"2405.12485","evidence_quote":"Constructs the category of formal languages with rational transductions and the composition law that the automaton category and its transducer morphisms mirror."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Proves that every rational transduction is computed by a transducer, grounding the correspondence action on automata used in Theorem 3.3."},{"cited_title":"Computer program- ming and formal systems","cited_arxiv_id":null,"evidence_quote":"Gives the original Chomsky–Schützenberger reduction of context-free languages to Dyck languages, whose categorical analogue is the tree-contour representation."}],"review_version":1}