Pith. sign in

REVIEW 2 major objections 7 minor 73 references

Finite-precision causal transformers without positions recognize only star-free languages, with tighter classes for simpler attention.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · grok-4.5

2026-07-30 14:49 UTC pith:6HVTL643

load-bearing objection Clean four-way hierarchy for NoPE finite-precision causal transformers, with a real FP-vs-sharp separation and tight bounds only under free wiring. the 2 major comments →

arxiv 2607.26988 v1 pith:6HVTL643 submitted 2026-07-29 cs.FL cs.LG

A Compositional Theory of Causally Masked Transformers

Franz Nowak , Ryan Cotterell , Reda Boumasmoud This is my paper
classification cs.FL cs.LG MSC 68Q7068Q4520M35
keywords transformerscausal maskingfinite precisionsemigroup theorystar-free languagesR-trivialattention mechanismsNoPE
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

This paper asks what decision problems a causally masked transformer can solve on strings of any length when precision and parameters are fixed. Instead of idealized math, it reads expressivity straight from the finite memory that attention actually builds under floating-point arithmetic and left-to-right evaluation. That memory is a query-indexed bank of accumulators: each head updates its own bank, heads run in parallel inside a layer, and layers stack hierarchically. For transformers without positional embeddings the choice of attention then fixes a clean hierarchy: width-one sliding windows give only bounded-suffix (definite) memory; sharp soft attention gives irreversible checklist-like (R-trivial) memory; mixing the two gives locally R-trivial memory; ordinary floating-point soft attention reaches the full aperiodic/star-free class and no further. Under a free-wiring assumption the four upper bounds are tight, so the algebra matches what the architecture can realize.

Core claim

Under finite precision, causal masking, fixed left-to-right evaluation and no positional embeddings, the languages recognized by transformer acceptors are exactly those whose syntactic semigroups lie in Def, R, LR or Ap according to the attention mechanism: width-one sliding-window heads yield definite languages, sharp soft attention yields R-trivial languages, cascades of window then sharp heads yield locally R-trivial languages, and ordinary floating-point soft attention yields star-free languages; free wiring makes all four bounds tight.

What carries the argument

The head memory ZH = A^Q — the finite, query-indexed family of attention accumulators — whose left-to-right updates generate a transformation semigroup; heads compose in parallel, layers by cascade/wreath product, so language expressivity reduces to which of the prime semigroups U1, U2, U3 the chosen attention can realize.

Load-bearing premise

Tightness needs the free-wiring assumption: every encoder, key/query/value map, mixer, wiring and accepting set may be an arbitrary function on the finite sets, and layers may be stacked in exactly the order the algebra demands.

What would settle it

Exhibit a fixed finite-precision NoPE transformer with ordinary left-to-right soft attention whose accepted language has non-aperiodic syntactic semigroup (e.g., parity), or show that free wiring cannot be realized by any choice of the architecture’s finite maps so that a required prime (U1, U2 or U3) is missing.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • Ordinary floating-point soft attention cannot recognize parity or any modular counting, at any depth or width.
  • Sharp soft attention is strictly weaker than full floating-point soft attention; the difference is exactly the gap between R-trivial and aperiodic memory.
  • Width-one local attention alone can retain only a bounded suffix of the input.
  • Stacking local attention below sharp soft attention yields precisely the locally R-trivial languages and nothing beyond.
  • Architecture designers can target a desired language class by choosing which attention primes the heads supply and how layers are cascaded.

Where Pith is reading between the lines

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

  • Heavy quantization shrinks the accumulator and query sets, so the same algebraic bounds become practically checkable on real hardware rather than only asymptotic.
  • Because evaluation order is load-bearing, reversing the accumulation direction would swap the R-sided conclusions for their L-sided duals; implementations that parallelize or reorder sums may therefore change the recognized class.
  • Finite or periodic position tags that still induce a semigroup morphism could be folded into the same analysis, potentially lifting the NoPE restriction without leaving the regular realm.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 7 minor

Summary. The paper develops an algebraic expressivity theory for causally masked, finite-precision transformers without positional embeddings. Attention heads are formalized as finite transition systems whose state is a query-indexed family of accumulators updated left-to-right; heads compose in parallel within layers and layers compose by cascade/wreath product. Under fixed precision and evaluation order, width-one sliding-window heads yield definite transition semigroups, sharp soft attention yields R-trivial semigroups, cascades of the two yield locally R-trivial semigroups, and ordinary floating-point soft attention yields aperiodic semigroups. Via Stiffler’s refinements of Krohn–Rhodes and an acceptor divisibility chain, the corresponding NoPE transformer acceptors recognize only definite, R-trivial, locally R-trivial, and star-free languages respectively (Theorems 29–32). Under an explicit free-wiring assumption the four bounds are tight (Corollary 34), with prime factors U1, U2, U3 realized inside the respective attention mechanisms (Lemmas 24, 26, 28).

Significance. If correct, this is a substantial contribution to the formal-language analysis of transformers. It derives expressivity from implemented finite-precision dynamics rather than idealized arithmetic or external logics, and it cleanly separates four attention regimes that map onto classical semigroup varieties (Table 1). The floating-point versus sharp soft-attention distinction—showing that left-to-right FP accumulation can realize U3 and hence full aperiodicity while the sharp variant cannot—is new and practically relevant for quantized models. The compositional route (head → core → cascade → syntactic semigroup) is uniform and reusable. Strengths include explicit assumptions (F/M/P/E), full proofs of the head-level lemmas in the appendix, tight classical correspondences (Schützenberger, Stiffler), and honest labeling of the free-wiring condition needed only for tightness. The work usefully complements concurrent LTL characterizations while explaining why numerical semantics matter.

major comments (2)
  1. [§4, Propositions 12–13, Remark 14] The expressivity upper bounds (Theorems 29–32) and the factorization/divisibility chain (Propositions 12–13) rest on the algebraic-RNN core/cascade/wreath infrastructure of the concurrent Nowak, Cotterell & Boumasmoud (2026) paper. Remark 14 asserts that monoid proofs transfer verbatim to semigroups, but a journal version should restate, in self-contained form, the precise statements of the cascade factorization and acceptor-divisibility results being invoked (at least as theorems with citations to the corresponding numbered results), so that a reader can verify the transformer specialization without reconstructing the companion paper. This is a presentation/verifiability issue, not an apparent correctness flaw.
  2. [Definition 33, Corollary 34, Definition 43, Eqs. (40)–(41)] Corollary 34’s tightness depends on the free-wiring assumption (Definition 33), which permits arbitrary wiring maps and cascade order. The concrete NoPE architecture of Definition 43 and Eqs. (40)–(41) instead fixes residual+LN+MLP wirings. The upper bounds correctly apply to that constrained class, but the lower-bound constructions are only claimed inside the free-wiring enlargement. The manuscript should state explicitly in §5 and near Table 1 that tightness is not claimed for residual wirings as written, and briefly indicate whether the Stiffler cascades can be simulated through residual connections or remain open. Without that clarification the abstract’s “all four bounds are tight” is easy to over-read as applying to standard transformer wiring.
minor comments (7)
  1. [Figure 1] Figure 1 is conceptually helpful but under-specified in the caption: the symbols S(·), U, V*, and the stacked wreath markers are not tied back to numbered definitions. A short caption walk-through would help non-algebraists.
  2. [Figure 2] Figure 2’s checklist / last-number intuition is good; labeling each panel with the corresponding variety (Def / R / LR / Ap) in the figure itself, not only in the legend block, would improve scanability.
  3. [Definition 16] Definition 16 (sharp soft attention) is central to the R-trivial bound. One sentence relating it to common practical approximations (e.g., score thresholding or underflow-to-zero) would help motivate the definition beyond the algebraic convenience.
  4. [Lemma 27] In the proof sketch of Lemma 27, “order-preserving map of a finite chain” is correct under the stated FP semantics; consider citing that fl-addition of a nonnegative increment is monotone, since some non-IEEE or mixed-precision regimes break this.
  5. [§6] Related Work: the concurrent Li & Cotterell (2026) LTL results on local+soft attention are acknowledged; a one-line comparison table (algebraic vs LTL assumptions) would make the complementarity sharper.
  6. [Abstract, §1] Minor typography: several words are missing spaces after commas or between glued tokens in the abstract and early sections (e.g., “Whattypesof”, “finite-precisiontransformersolvefor”), apparently from PDF extraction; ensure the camera-ready source has clean spacing.
  7. [Remark 42] Remark 42 on why semigroups (not monoids) are required is important and well taken; consider promoting a shortened version into the main §2 so readers see early why Def and LR would collapse at monoid level.

Circularity Check

1 steps flagged

No significant circularity: transformer-to-semigroup bounds are derived from head dynamics plus classical Stiffler/Schützenberger; prior algebraic-RNN paper is reused as infrastructure, not as the target claim.

specific steps
  1. self citation load bearing [§4 Propositions 12–13; Remark 14]
    "This is the factorization lemma of Nowak, Cotterell, and Boumasmoud (2026, Lem. 3.12), specialized to transformer cores; the proofs transfer to semigroups by Remark 14. ... This is the acceptor divisibility chain of Nowak, Cotterell, and Boumasmoud (2026), at semigroup level. ... The results of Nowak, Cotterell, and Boumasmoud (2026, §3) are stated for monoids and are used here for semigroups. Their proofs transfer verbatim..."

    The composition and S(L)≺W divisibility steps that lift head semigroups to full acceptor bounds are justified by citation to the authors' concurrent algebraic-RNN paper rather than re-proved in full here. This is load-bearing for the route from heads to languages, but not circular in the strong sense: the prior results are general (parameter-free, assumptions do not include the transformer language classes), and the paper re-verifies applicability to transformer cores. The attention-specific content and classical variety theorems remain independent.

full rationale

The load-bearing upper bounds (Theorems 29–32) are obtained by (i) proving head transition semigroups lie in Def / R / Ap from the explicit accumulator updates (Lemmas 23, 25, 27), (ii) closing under parallel composition and wreath products via external Stiffler and Krohn–Rhodes theorems, and (iii) transferring language membership through the acceptor divisibility chain. Those head lemmas are self-contained analyses of floating-point / sharp / window dynamics; they do not define the target language classes in terms of the architecture. Tightness (Corollary 34) is explicitly conditional on free-wiring (Definition 33) and on realizing the primes U1–U3 (Lemmas 24, 26, 28)—an implementability hypothesis, not a fitted or self-definitional prediction. The only self-citation of note is Nowak, Cotterell & Boumasmoud (2026) for core/cascade/factorization infrastructure (Propositions 12–13, Remark 14); the paper re-specializes those lemmas to transformer cores and does not import the language-class conclusions from that work. Classical Schützenberger aperiodicity↔star-free and Stiffler decompositions are external. No fitted-input-as-prediction, uniqueness-from-authors, or renaming circularity appears. Score 1 only for mild methodological dependence on overlapping-author infrastructure that is not itself the claimed expressivity result.

Axiom & Free-Parameter Ledger

0 free parameters · 7 axioms · 3 invented entities

The central hierarchy is a theorem under explicitly listed modeling axioms (finite precision, causal mask, NoPE, fixed left-to-right fold) plus classical semigroup decomposition theorems. No parameters are fitted. The main non-standard modeling choices are sharp attention, free wiring for tightness, and the identification of head memory with the query-indexed accumulator family. Invented entities are definitional abstractions of the architecture, not physical posits.

axioms (7)
  • domain assumption All arithmetic is constant-precision floating-point with a fixed left-to-right evaluation order for attention accumulation (assumptions F and E).
    Load-bearing for aperiodicity vs R-triviality; associativity would erase the FP-specific memory behavior used in Lemmas 27–28.
  • domain assumption No positional embeddings; encoder is a length-independent map e: Σ → D^d (assumption P, Definition 43).
    Required for the encoder to induce a semigroup morphism; with unbounded positions the divisibility chain of Proposition 13 fails (section 'A Note on Positional Embeddings').
  • domain assumption Causal masking: attention at t depends only on inputs ≤ t (assumption M).
    Makes the head a left-to-right fold and the state a prefix sufficient statistic (Proposition 9).
  • ad hoc to paper Sharp soft attention: if a score does not change the denominator under FP, the whole update is suppressed (Definition 16).
    A modified semantics introduced to obtain R-triviality; not identical to standard production softmax.
  • ad hoc to paper Free-wiring assumption: arbitrary finite maps for encoders, Q/K/V, mixers, wirings, acceptors, and prescribed cascade order (Definition 33).
    Used only for tightness (Corollary 34); upper bounds do not need it.
  • standard math Stiffler's decomposition theorems for Def, R, LR and Krohn–Rhodes/Schützenberger for Ap/star-free (Theorems 46–50, Corollary 47).
    Classical finite-semigroup results invoked to lift head primes to language classes.
  • domain assumption Transformer cores are algebraic cores in the sense of Nowak, Cotterell & Boumasmoud (2026); cascade/divisibility lemmas transfer from monoids to semigroups (Remark 14).
    Framework dependency; proofs claimed to transfer because generators are indexed by X not X∪{ε}.
invented entities (3)
  • Query-indexed head state Z_H = A^Q (attention memory as finite accumulator family) independent evidence
    purpose: Serves as the sufficient statistic of the prefix for all future queries and the carrier of the head transition semigroup.
    Definitional abstraction of implemented online attention; justified by Proposition 9 sufficiency, not an extra physical object.
  • Sharp soft-attention update rule no independent evidence
    purpose: Defines a restricted soft-attention dynamics whose transition semigroup is R-trivial and can realize U2.
    Paper-introduced variant; independent interest only insofar as it approximates underflow-to-zero behavior in low precision.
  • Transformer core / algebraic transformer acceptor (parallel heads, cascade layers, accepting core) independent evidence
    purpose: Compositional interface from architecture to wreath products and syntactic-semigroup bounds.
    Specialization of the authors’ algebraic RNN notion to attention cores; existence is by construction from the architecture equations.

pith-pipeline@v1.2.0-daily-grok45 · 22094 in / 3851 out tokens · 76999 ms · 2026-07-30T14:49:02.665490+00:00 · methodology

0 comments
read the original abstract

What types of decision problems can a causally masked, finite-precision transformer solve for inputs of arbitrary length? Existing answers often rely on idealized arithmetic, but under finite precision, rounding and evaluation order can change what information attention retains and therefore what the model can compute. We develop an algebraic formalization that derives expressivity directly from the model's implemented dynamics. Its central object is its memory; the finite internal state computed by attention that summarizes the information from the prefix available to all future queries. Each attention head updates its own state independently within a layer, while layers compose hierarchically, providing a uniform route from model assumptions to expressivity bounds. Applying this method to transformers without positional embeddings, we obtain an expressivity hierarchy governed by the attention type under specific numerical semantics. Width-one sliding-window attention supports bounded-suffix memory, while a modified form of soft attention supports irreversible, checklist-like state, and combining the two mechanisms provides an interplay of both. Ordinary left-to-right floating-point soft attention can realize more expressive memory operations than any of the above. Algebraically, the four cases correspond to definite, R-trivial, locally R-trivial, and aperiodic semigroups. Under an explicit free-wiring assumption, all four bounds are tight.

Figures

Figures reproduced from arXiv: 2607.26988 by Franz Nowak, Reda Boumasmoud, Ryan Cotterell.

Figure 1
Figure 1. Figure 1: Abstraction of a transformer to an algebraic object to a syntactic semigroup. [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Illustration of the types of tasks that attention can [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗

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

73 extracted references · 1 canonical work pages

  1. [1]

    The Expressive Capacity of State Space Models:

    Sarrof, Yash and Veitsman, Yana and Hahn, Michael , booktitle=. The Expressive Capacity of State Space Models:. 2024 , bdsk-url-1=

    2024

  2. [2]

    Unlocking State-Tracking in Linear

    Grazzi, Riccardo and Siems, Julien and Zela, Arber and Franke, J\". Unlocking State-Tracking in Linear. International Conference on Learning Representations , editor =. 2025 , Bdsk-Url-1 =

    2025

  3. [3]

    Finite Automata, Formal Logic, and Circuit Complexity , year=

    Howard Straubing , editor=. Finite Automata, Formal Logic, and Circuit Complexity , year=

  4. [4]

    Algebraic Theory of Machines

    Kenneth Krohn and John Rhodes , journal=. Algebraic Theory of Machines

  5. [5]

    Seeing Convolution Through the Eyes of Finite Transformation Semigroup Theory:

    Andrew Hryniowski and Alexander Wong , year=. Seeing Convolution Through the Eyes of Finite Transformation Semigroup Theory:. 1905.10901 , archiveprefix=

    Pith/arXiv arXiv 1905

  6. [6]

    and Sontag, Eduardo D

    Siegelmann, Hava T. and Sontag, Eduardo D. , title=. 1992 , isbn=. doi:10.1145/130385.130432 , booktitle=

    arXiv 1992

  7. [7]

    arXiv preprint arXiv:2310.12942 , url=

    On the Representational Capacity of Recurrent Neural Language Models , author=. arXiv preprint arXiv:2310.12942 , url=. 2023 , eprint=

    Pith/arXiv arXiv 2023

  8. [8]

    Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers) , month=

    Lower Bounds on the Expressivity of Recurrent Neural Language Models , author=. Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers) , month=. 2024 , address=. doi:10.18653/v1/2024.naacl-long.380 , pages=

    doi:10.18653/v1/2024.naacl-long.380 2024

  9. [9]

    On the Practical Computational Power of Finite Precision

    Weiss, Gail and Goldberg, Yoav and Yahav, Eran , editor=. On the Practical Computational Power of Finite Precision. Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers) , month=. 2018 , address=. doi:10.18653/v1/P18-2117 , pages=

    doi:10.18653/v1/p18-2117 2018

  10. [10]

    Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing , month=

    Recurrent Neural Language Models as Probabilistic Finite-state Automata , author=. Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing , month=. 2023 , address=. doi:10.18653/v1/2023.emnlp-main.502 , pages=

    doi:10.18653/v1/2023.emnlp-main.502 2023

  11. [11]

    , booktitle=

    Indyk, P. , booktitle=. Optimal simulation of automata by neural nets , year=

  12. [12]

    Proceedings of the Workshop on Deep Learning and Formal Languages: Building Bridges , month=

    Sequential Neural Networks as Automata , author=. Proceedings of the Workshop on Deep Learning and Formal Languages: Building Bridges , month=. 2019 , address=. doi:10.18653/v1/W19-3901 , pages=

    doi:10.18653/v1/w19-3901 2019

  13. [13]

    Chain-of-Thought Prompting Elicits Reasoning in Large Language Models , url=

    Wei, Jason and Wang, Xuezhi and Schuurmans, Dale and Bosma, Maarten and ichter, brian and Xia, Fei and Chi, Ed and Le, Quoc V and Zhou, Denny , booktitle=. Chain-of-Thought Prompting Elicits Reasoning in Large Language Models , url=

  14. [14]

    Turing, A. M. , title=. Proceedings of the London Mathematical Society , volume=. doi:https://doi.org/10.1112/plms/s2-42.1.230 , url=. https://londmathsoc.onlinelibrary.wiley.com/doi/pdf/10.1112/plms/s2-42.1.230 , year=

    doi:10.1112/plms/s2-42.1.230

  15. [15]

    2021 , eprint=

    Evaluating Large Language Models Trained on Code , author=. 2021 , eprint=

    2021

  16. [16]

    2303.08774 , archiveprefix=

    OpenAI , year=. 2303.08774 , archiveprefix=

    Pith/arXiv arXiv

  17. [17]

    Advances in Neural Information Processing Systems , editor=

    Solving Quantitative Reasoning Problems with Language Models , author=. Advances in Neural Information Processing Systems , editor=. 2022 , url=

    2022

  18. [18]

    Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) , month=

    On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning , author=. Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) , month=. 2024 , address=. doi:10.18653/v1/2024.acl-long.676 , pages=

    doi:10.18653/v1/2024.acl-long.676 2024

  19. [19]

    Proceedings of the 41st International Conference on Machine Learning , articleno=

    Merrill, William and Petty, Jackson and Sabharwal, Ashish , title=. Proceedings of the 41st International Conference on Machine Learning , articleno=. 2024 , publisher=

    2024

  20. [20]

    Anderson and Amo Alonso, Carmen and Sejnowski, Terrence J

    Karuvally, Arjun and Nowak, Franz and Keller, T. Anderson and Amo Alonso, Carmen and Sejnowski, Terrence J. and Siegelmann, Hava T. , booktitle=. Bridging Expressivity and Scalability with Adaptive Unitary. 2025 , url=. 2507.05238 , archiveprefix=

    arXiv 2025

  21. [21]

    Wang, Maolin and Rasoulinezhad, Seyedramin and Leong, Philip H. W. and So, Hayden K.-H. , journal=. 2022 , volume=. doi:10.1109/TPDS.2022.3149787 , url=

    arXiv 2022

  22. [22]

    Proceedings of the IEEE conference on computer vision and pattern recognition , pages=

    Quantization and training of neural networks for efficient integer-arithmetic-only inference , author=. Proceedings of the IEEE conference on computer vision and pattern recognition , pages=. 2018 , url=

    2018

  23. [23]

    and Keutzer, Kurt , booktitle=

    Kim, Sehoon and Gholami, Amir and Yao, Zhewei and Mahoney, Michael W. and Keutzer, Kurt , booktitle=

  24. [24]

    arXiv preprint arXiv:2109.09828 , year=

    Sari, Eyy. arXiv preprint arXiv:2109.09828 , year=

    Pith/arXiv arXiv

  25. [25]

    Training Integer-Only Deep Recurrent Neural Networks , year=

    Nia, Vahid Partovi and Sari, Eyy\". Training Integer-Only Deep Recurrent Neural Networks , year=. doi:10.1007/s42979-023-01920-z , journal=

    doi:10.1007/s42979-023-01920-z

  26. [26]

    Transactions of the Association for Computational Linguistics , volume=

    Theoretical Limitations of Self-Attention in Neural Sequence Models , author=. Transactions of the Association for Computational Linguistics , volume=. 2020 , address=. doi:10.1162/tacl_a_00306 , pages=

    doi:10.1162/tacl_a_00306 2020

  27. [27]

    Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) , month=

    Overcoming a Theoretical Limitation of Self-Attention , author=. Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) , month=. 2022 , address=. doi:10.18653/v1/2022.acl-long.527 , pages=

    doi:10.18653/v1/2022.acl-long.527 2022

  28. [28]

    Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP) , month=

    On the Ability and Limitations of Transformers to Recognize Formal Languages , author=. Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP) , month=. 2020 , address=. doi:10.18653/v1/2020.emnlp-main.576 , pages=

    doi:10.18653/v1/2020.emnlp-main.576 2020

  29. [29]

    Journal of Machine Learning Research , year=

    Jorge Pérez and Pablo Barceló and Javier Marinkovic , title=. Journal of Machine Learning Research , year=

  30. [30]

    Transactions of the Association for Computational Linguistics , volume=

    Saturated Transformers are Constant-Depth Threshold Circuits , author=. Transactions of the Association for Computational Linguistics , volume=. 2022 , address=. doi:10.1162/tacl_a_00493 , pages=

    doi:10.1162/tacl_a_00493 2022

  31. [31]

    What Formal Languages Can Transformers Express?

    Strobl, Lena and Merrill, William and Weiss, Gail and Chiang, David and Angluin, Dana , journal=. What Formal Languages Can Transformers Express?. 2024 , address=. doi:10.1162/tacl_a_00663 , pages=

    doi:10.1162/tacl_a_00663 2024

  32. [32]

    Proceedings of the 2018 Conference of the North

    Recurrent Neural Networks as Weighted Language Recognizers , author=. Proceedings of the 2018 Conference of the North. 2018 , address=. doi:10.18653/v1/N18-1205 , pages=

    doi:10.18653/v1/n18-1205 2018

  33. [33]

    The Parallelism Tradeoff:

    Merrill, William and Sabharwal, Ashish , journal=. The Parallelism Tradeoff:. 2023 , address=. doi:10.1162/tacl_a_00562 , pages=

    doi:10.1162/tacl_a_00562 2023

  34. [34]

    Proceedings of the 38th International Conference on Machine Learning , series=

    Linear Transformers are Secretly Fast Weight Programmers , author=. Proceedings of the 38th International Conference on Machine Learning , series=. 2021 , publisher=

    2021

  35. [35]

    International Conference on Learning Representations , year=

    Efficiently Modeling Long Sequences with Structured State Spaces , author=. International Conference on Learning Representations , year=

  36. [36]

    International Conference on Learning Representations , year=

    Simplified State Space Layers for Sequence Modeling , author=. International Conference on Learning Representations , year=

  37. [37]

    First Conference on Language Modeling , year=

    Mamba: Linear-Time Sequence Modeling with Selective State Spaces , author=. First Conference on Language Modeling , year=

  38. [38]

    Findings of the Association for Computational Linguistics: EMNLP 2023 , month=

    Peng, Bo and Alcaide, Eric and Anthony, Quentin and Albalak, Alon and Arcadinho, Samuel and Biderman, Stella and Cao, Huanqi and Cheng, Xin and Chung, Michael and Derczynski, Leon and Du, Xingjian and Grella, Matteo and Gv, Kranthi and He, Xuzheng and Hou, Haowen and Kazienko, Przemyslaw and Kocon, Jan and Kong, Jiaming and Koptyra, Bart. Findings of the ...

    doi:10.18653/v1/2023.findings-emnlp.936 2023

  39. [39]

    and Wu, Tianyi and Wuttke, Daniel and Zhou-Zheng, Christian , year=

    Peng, Bo and Zhang, Ruichong and Goldstein, Daniel and Alcaide, Eric and Hou, Haowen and Lu, Janna and Merrill, William and Song, Guangyu and Tan, Kaifeng and Utpala, Saiteja and Wilce, Nathan and Wind, Johan S. and Wu, Tianyi and Wuttke, Daniel and Zhou-Zheng, Christian , year=. 2503.14456 , archiveprefix=

    Pith/arXiv arXiv

  40. [40]

    Transformers are

    Katharopoulos, Angelos and Vyas, Apoorv and Pappas, Nikolaos and Fleuret, Fran. Transformers are. Proceedings of the 37th International Conference on Machine Learning , series=. 2020 , publisher=

    2020

  41. [41]

    2023 , publisher=

    Modeling sequences with structured state spaces , author=. 2023 , publisher=

    2023

  42. [42]

    2025 , eprint=

    Grokking at the Edge of Numerical Stability , author=. 2025 , eprint=

    2025

  43. [43]

    1976 , publisher=

    Automata, Languages, and Machines , author=. 1976 , publisher=

    1976

  44. [44]

    Moore , title =

    Edward F. Moore , title =. Annals of Mathematics Studies , volume =. 1956 , pages =

    1956

  45. [45]

    Mealy , title =

    George H. Mealy , title =. Bell System Technical Journal , volume =. 1955 , url =

    1955

  46. [46]

    Sch. Une th. S. 1955 , url=

    1955

  47. [47]

    ACM computing surveys (CSUR) , volume=

    What every computer scientist should know about floating-point arithmetic , author=. ACM computing surveys (CSUR) , volume=. 1991 , url=

    1991

  48. [48]

    Neural computation , volume=

    Long short-term memory , author=. Neural computation , volume=. 1997 , url=

    1997

  49. [49]

    Cognitive science , volume=

    Finding structure in time , author=. Cognitive science , volume=. 1990 , url=

    1990

  50. [50]

    Learning phrase representations using

    Cho, Kyunghyun and Van Merri. Learning phrase representations using. arXiv preprint arXiv:1406.1078 , year=

    Pith/arXiv arXiv

  51. [51]

    IEEE Transactions on Computers , volume=

    Monotonicity of multi-term floating-point adders , author=. IEEE Transactions on Computers , volume=. 2024 , url=

    2024

  52. [52]

    Lecture notes LIAFA, Universit

    Mathematical foundations of automata theory , author=. Lecture notes LIAFA, Universit. 2010 , url=

    2010

  53. [53]

    Korsky and Robert C

    Samuel A. Korsky and Robert C. Berwick , year=. On the Computational Power of. 1906.06349 , archivePrefix=

    Pith/arXiv arXiv 1906

  54. [54]

    Lee Giles , doi =

    John Stogin and Ankur Mali and C. Lee Giles , doi =. A provably stable neural network. Information Sciences , keywords =. 2024 , Bdsk-Url-1 =

    2024

  55. [55]

    and Giles, C

    Omlin, Christian W. and Giles, C. Lee , title =. 1996 , issue_date =. doi:10.1145/235809.235811 , journal =

    arXiv 1996

  56. [56]

    On pseudovarieties , url =

    Samuel Eilenberg and Marcel-Paul Sch. On pseudovarieties , url =. Advances in Mathematics , number =. 1976 , Bdsk-Url-1 =. doi:https://doi.org/10.1016/0001-8708(76)90029-3 , issn =

    doi:10.1016/0001-8708(76)90029-3 1976

  57. [57]

    and Yahav, Eran

    Merrill, William and Weiss, Gail and Goldberg, Yoav and Schwartz, Roy and Smith, Noah A. and Yahav, Eran. A Formal Hierarchy of RNN Architectures. Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics. 2020. doi:10.18653/v1/2020.acl-main.43

    doi:10.18653/v1/2020.acl-main.43 2020

  58. [58]

    , title =

    Elman, Jeffrey L. , title =. Cognitive Science , year =. doi:https://doi.org/10.1207/s15516709cog1402\_1 , url =

    doi:10.1207/s15516709cog1402

  59. [59]

    1954 , publisher=

    Theory of neural-analog reinforcement systems and its application to the brain-model problem , author=. 1954 , publisher=

    1954

  60. [60]

    Proceedings of the 38th International Conference on Machine Learning , pages =

    Thinking Like Transformers , author =. Proceedings of the 38th International Conference on Machine Learning , pages =. 2021 , editor =

    2021

  61. [61]

    Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages , url =

    Yang, Andy and Chiang, David and Angluin, Dana , booktitle =. Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages , url =. 2024 , Bdsk-Url-1 =. doi:10.52202/079017-0327 , editor =

    doi:10.52202/079017-0327 2024

  62. [62]

    2021 , isbn =

    Handbook of Automata Theory , author =. 2021 , isbn =

    2021

  63. [63]

    ArXiv , year=

    Bitformer: An efficient Transformer with bitwise operation-based attention for Big Data Analytics at low-cost low-precision devices , author=. ArXiv , year=

  64. [64]

    39th Annual Conference on Neural Information Processing Systems (NeurIPS 2025) , year=

    Characterizing the Expressivity of Fixed-Precision Transformer Language Models , author=. 39th Annual Conference on Neural Information Processing Systems (NeurIPS 2025) , year=

    2025

  65. [65]

    Forty-third International Conference on Machine Learning , year=

    An Algebraic View of the Expressivity of Recurrent Language Models , author=. Forty-third International Conference on Machine Learning , year=

  66. [66]

    ArXiv , year=

    Online normalizer calculation for softmax , author=. ArXiv , year=

  67. [67]

    Dao, Tri and Fu, Dan and Ermon, Stefano and Rudra, Atri and R. Flash. Advances in neural information processing systems , volume=

  68. [68]

    Chapter 1

    Price Stiffler , doi =. Chapter 1. Extension of the fundamental theorem of finite semigroups , url =. Advances in Mathematics , number =. 1973 , Bdsk-Url-1 =

    1973

  69. [69]

    Brzozowski and Faith E

    J.A. Brzozowski and Faith E. Fich , doi =. Languages of R-trivial monoids , url =. Journal of Computer and System Sciences , number =. 1980 , Bdsk-Url-1 =

    1980

  70. [70]

    Methods of the algebraic theory of machines: I

    Kenneth Krohn and Richard Mateosian and John Rhodes , doi =. Methods of the algebraic theory of machines: I. Decomposition theorem for generalized machines; Properties preserved under series and parallel compositions of machines , url =. Journal of Computer and System Sciences , number =. 1967 , Bdsk-Url-1 =

    1967

  71. [71]

    The Eleventh International Conference on Learning Representations , year=

    Transformers Learn Shortcuts to Automata , author=. The Eleventh International Conference on Learning Representations , year=

  72. [72]

    Characterizing the Expressivity of Local Attention in Transformers

    Li, Jiaoda and Cotterell, Ryan. Characterizing the Expressivity of Local Attention in Transformers. Proceedings of the 64th Annual Meeting of the A ssociation for C omputational L inguistics (Volume 1: Long Papers). 2026. doi:10.18653/v1/2026.acl-long.1739

    work page doi:10.18653/v1/2026.acl-long.1739 2026

  73. [73]

    2021 , MONTH = Sep, DOI =

    Pin, Jean-. 2021 , MONTH = Sep, DOI =

    2021