Pith. sign in

REVIEW 3 major objections 5 minor 1 cited by

On the Expressiveness and Length Generalization of Selective State-Space Models on Regular Languages

T0 review · 3 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash

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

Pith's one-line read A single-layer selective SSM with dense, input-selected transition matrices reaches at least 99.9% length-generalization accuracy on seven finite-state automata, the first selective SSM to do so.

desk verdict SD-SSM is a genuinely new architecture with strong empirical length-generalization results on FSA tasks; the theory is narrower than it looks, but the main contribution stands. read the letter →

arxiv 2412.19350 v2 pith:CQLUIWK5 submitted 2024-12-26 cs.LG cs.AIcs.CL

Aleksandar Terzić , Michael Hersche , Giacomo Camposampiero , Thomas Hofmann , Abu Sebastian , Abbas Rahimi This is my paper · ORCID
classification cs.LGcs.AIcs.CL
keywords selectivestate-spacemodelslengthgeneralizationregularlanguagesfinite-stateautomataemulationdiagonalcommutativitystatetrackinglinearrecurrences
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 asks whether selective state-space models can emulate finite-state automata and keep working on sequences far longer than the ones seen in training. It introduces SD-SSM, a single-layer selective SSM that forms each transition matrix as a softmax-weighted convex combination of dense trainable matrices, then reads out the state through layer normalization and a linear map. On the seven automata in Table 1, SD-SSM is the first selective SSM in the paper's comparison to reach at least 99.9% length-generalization accuracy, including on the non-commutative D4 and the 60-state A5. The paper also proves that a single-layer diagonal selective SSM, under its explicit FSA-to-SSM mapping with $b(u_t)=0$, can only emulate commutative automata because simultaneously diagonalizable transitions are order-invariant. This gives a theoretical handle on why diagonal variants generalize on commutative groups but not on non-commutative ones, and it isolates dense input-selected transitions and a simple readout as the design choices that restore state tracking.

What carries the argument

The central object is the SD-SSM transition-selection mechanism. For each input $u_t$, a linear map followed by softmax produces weights over $k$ trainable dense matrices $A_1,\dots,A_k$; the weighted sum is column-normalized, and the recurrence $x_{t+1}=A(u_t)x_t+Bu_t$ propagates the state. Because the selected matrices are dense and unconstrained, successive transition matrices need not commute, so the product $A(u_T)\cdots A(u_1)$ can implement any permutation of automaton states, including non-commutative ones. On the theory side, the load-bearing identity is simultaneous diagonalizability: if all $A(u_t)$ share one eigenbasis, so $A(u_t)=W\Lambda(u_t)W^{-1}$, then with $b=0$ the dynamics become $\tilde{x}_{t+1}=\Lambda(u_t)\tilde{x}_t$ in the transformed basis, and products of diagonal matrices commute, making the final state order-invariant.

What would settle it

Run SD-SSM on the seven Table 1 tasks with the reported hyperparameters and fresh random seeds: the headline claim fails if any task's best-seed accuracy stays below 99.9% on lengths up to 500. Separately, train a single-layer diagonal selective SSM with $b(u_t)=0$ on $D_{30}$; any run that reaches perfect length generalization would contradict Proposition 1, while a failure would leave the paper's mapping assumption as the only explanation.

Watch

Extended reading notes

Core claim

On its own terms, the paper establishes an empirical result and a conditional theoretical result. The empirical result is that SD-SSM, with a dictionary of $k$ dense transition matrices combined by softmax and column-wise operator normalization, followed by the recurrence $x_{t+1}=A(u_t)x_t+Bu_t$ and a LayerNorm-plus-linear readout, achieves at least 99.9% best-seed accuracy on all seven FSA tasks after training only on sequences of length up to 40 (or 90 for the larger groups), and its average accuracy stays near-perfect on most of them. The theoretical result is Proposition 1: if a single-layer selective SSM implements the paper's Section 2 mapping with $b(u_t)=0$ and its transition matrices are simultaneously diagonalizable, then the final state is independent of input order, so the model can only emulate commutative automata. The paper uses Table 4's contrast between the commutative $C_2\times C_{30}$ and the non-commutative $D_{30}$ to show that this restriction matches the empirical difficulty, while acknowledging that the $b(u_t)$ terms in the unrolled recurrence are exactly what can break commutativity when $B\ne 0$.

Load-bearing premise

The theoretical explanation for the diagonal models' failures rests on assuming that trained one-layer models implement the paper's Section 2 FSA-to-SSM mapping with $b(u_t)=0$; the diagonal models that actually learn the non-commutative automaton $D_{30}$ in Table 4 use $b(u_t)\ne 0$, so the proposition does not directly cover the empirical case it is meant to explain.

Editorial extensions

If this is right

  • Length generalization on regular languages does not require multi-layer stacks: a single SD-SSM layer emulates commutative and non-commutative automata up to 500 steps after training on 40.
  • Dense, input-selected transition matrices appear to be the architectural ingredient that diagonal selective SSMs lack for non-commutative state tracking; the paper's theory locates the reason in simultaneous diagonalizability.
  • The parallel-scan implementation of SD-SSM keeps training parallelizable despite dense matrices, so the expressiveness gain does not force sequential training.
  • Using a linear readout over LayerNorm instead of a nonlinear MLP is decisive on Arithmetic: replacing it drops accuracy from 99.9% to at most 71.9% in the paper's sweeps.
  • Diagonal selective SSMs remain effective for commutative or order-insensitive tasks, where the paper reports near-perfect generalization, but their in-domain success on non-commutative automata does not transfer to longer inputs.

Reading between the lines

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

  • The commutativity argument suggests a general design rule for sequence models: an input-dependent transition family that is simultaneously diagonalizable cannot implement order-sensitive computation; any architecture that wants state tracking must let successive transitions fail to commute.
  • A direct test of the paper's theory would be to train a diagonal selective SSM with $b=0$ on a non-commutative solvable group and observe whether it can even reach in-domain accuracy; if it cannot, the mapping assumption is doing the explanatory work.
  • The softmax-dictionary mechanism could be tried on natural-language state tracking tasks where order matters; if it helps, the benefit would come from the same non-commuting transition structure, not from a larger state size.
  • Because Proposition 1 only covers $B=0$, the paper leaves open whether a diagonal selective SSM with learned $b(u_t)$ can be regularized to generalize in length; an annealed or sparsified $b$ term might recover non-commutative dynamics without dense matrices.
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 / 5 minor

Summary. The paper studies whether selective state-space models can emulate finite-state automata and generalize to longer sequences. It introduces SD-SSM, a single-layer selective SSM whose transition matrix at each step is a softmax-weighted convex combination of a dictionary of dense matrices, followed by operator normalization and a LayerNorm-plus-linear readout. On seven FSA tasks, the best of three seeds reaches at least 99.9% length generalization on all tasks, with lower average accuracy on some tasks such as C2×C4 (93.3%). The paper also studies diagonal selective SSMs and proves Proposition 1: under a specific B=0 mapping with simultaneously diagonalizable transition matrices, a single-layer diagonal selective SSM is order-invariant and can only emulate commutative automata. Experiments on C2×C30 and D30 show that diagonal SSMs learn the commutative automaton in-domain and generalize better than on the non-commutative one, although the B≠0 variants are the ones that learn D30. The paper attributes the diagonal limitations to the proposition.

Significance. The empirical contribution is potentially useful: SD-SSM is a simple architecture with strong length generalization on FSA emulation, and the paper provides code and detailed hyperparameter tables, which supports reproducibility. The comparison against RNN/LSTM on very short training lengths and the parallel-scan timing are informative. Proposition 1 is correct as a linear-algebra statement under its stated assumptions, but its connection to the experiments is incomplete because the diagonal models that learn the non-commutative automaton use B≠0, which is outside the proposition's scope. The paper would be significantly strengthened by either extending the theory to input-dependent bias terms or explicitly limiting the explanatory claim.

major comments (3)
  1. [Section 4, Proposition 1 and Table 4] Proposition 1 assumes the Sec. 2 FSA-to-SSM mapping with b(u_t)=0 (Eq. 13), but the diagonal variants in Table 4 that actually learn the non-commutative D30 automaton are precisely the B≠0 ones: the B=0 rows never exceed 8.35% accuracy on D30, while the B≠0 nonlinear-readout variant reaches 61.0%. The unrolled equations in Sec. 4 show that the b(u_t) terms are exactly what break commutativity, so a B≠0 trained model cannot be implementing the B=0 mapping. Consequently, Proposition 1 does not constrain the models whose behavior it is invoked to explain, and the paper's stated explanation of the poor length generalization of diagonal SSMs on non-commutative automata is not supported. The Conclusion's caveat 'assuming ... they indeed cannot model non-commutative automata' does not resolve this, because the B≠0 variants already provide a non-commutative update and are outside the assumption.
  2. [Abstract, Section 3, Table 1, Appendix B] The central claim that SD-SSM achieves 'perfect (≥99.9%)' length generalization is presented without qualification, but Table 1 and Table B.8 show this is the maximum over three seeds with per-task hyperparameter search (dictionary size k, lp-normalization exponent p, and learning rate all differ by task). The average C2×C4 accuracy is 93.3%, below the 99.9% threshold. A similar pattern appears in the length-efficiency analysis: Table 2 reports best-seed results, while Table C.14 shows the average SD-SSM accuracy at training length 5 is 41.3%, below the LSTM's 45.7%. The empirical evidence is valuable, but the 'perfect' and 'exhibits better length generalization' claims should be explicitly tied to best-of-three-seed selection; otherwise the abstract overstates robustness.
  3. [Section 4, 'Variants of C Diagonal SD-SSM' and Conclusion] The experimental narrative states that diagonal selective SSMs generalize significantly better on the commutative automaton than on the non-commutative one, but Table 4 shows this is not uniform across variants: with B≠0 and a nonlinear readout, C2×C30 reaches 65.8% and D30 reaches 61.0%, a much smaller gap than the B=0 rows. More importantly, the B≠0 nonlinear-readout model learns D30 in-domain, so the Conclusion's sentence that, under the paper's assumption, diagonal SSMs 'indeed cannot model non-commutative automata' is false for the models actually trained. The paper should either analyze the B≠0 case or explicitly limit the theoretical claim to B=0 models and remove the general conclusion.
minor comments (5)
  1. [Table B.10] The caption contains the typo 'Leraning rates'; it should read 'Learning rates'.
  2. [Appendix C, paragraph after Table C.14] The sentence 'it does exhibit higher variability across seeds compared to the the other models' contains a duplicated definite article.
  3. [Abstract and Section 5] The abstract's phrase 'the first selective SSM' is stronger than the qualified claim in Section 5 ('the first to demonstrate that all ... can be emulated with single layer selective SSM utilizing a linear readout'); please align the wording.
  4. [Table 1 caption] The caption refers to 'The complex ( C) diagonal model' but the symbol C is not defined before the table; consider defining it in the caption or in Section 4.
  5. [Section 3, Table 3] Table 3 reports a single timing run without variance or repetition details; since the parallel-versus-sequential comparison is a secondary claim, please state how many runs were averaged, if any.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the SD-SSM results are empirical and the theoretical proposition is an explicit conditional statement that does not feed back into the measurements.

full rationale

The paper's central contribution, SD-SSM's ≥99.9% length generalization on seven FSA tasks, is an empirical result: the model is trained on sequences up to length 40 and evaluated on lengths up to 500, with hyperparameters reported in Appendix B. No parameter of SD-SSM is fitted to the theoretical analysis, and no self-citation is used to justify the accuracy numbers. Proposition 1 is an explicitly conditional mathematical statement: under the Sec. 2 mapping with x0 = enc(qinit), b(ut) = 0, and simultaneously diagonalizable A(ut), the unrolled recurrence xt+1 = A(ut)xt is order-invariant, so only commutative automata can be emulated. The proof rests on the commuting property of diagonalizable matrices, not on the experimental outcomes. The paper itself flags the restriction ('using a restrictive assumption') and shows in the unrolled equations that b(ut) terms are exactly what break commutativity. That the proposition does not cover the B ≠ 0 diagonal models that actually learn D30 in-domain is a scope gap in the explanation, not a circular derivation: the theorem is conditional and is not used to generate the empirical table. The only self-citation (Terzić et al. 2024) points to the preprint's appendix and is not load-bearing. Baselines come from external work (Delétang et al. 2023; Liu et al. 2023), so the comparison is self-contained. No fitted input is renamed as a prediction. Consequently there is no circularity.

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

The central SD-SSM result is empirical and depends on per-task hyperparameters and seed selection. The theoretical claim depends on the explicitly stated assumption that models implement the Sec. 2 mapping with B=0. No new physical entities are introduced.

free parameters (3)
  • per-task dictionary size k (SD-SSM) = Parity 8, Even Pairs 8, Cycle 8, Arithmetic 18, C2xC4 6, D4 6, A5 6
    Chosen by hyperparameter search per task (Table B.8); the central perfect length generalization claim uses these task-specific values.
  • per-task lp-normalization exponent p (SD-SSM) = 1.2, 1.4, 1.3, 1.2, 1.3, 1.2, 1.3 in the same task order
    Varied over [1.0,1.5] via search; the operator normalization and therefore model stability depend on p.
  • per-task learning rates = SD-SSM: 1e-4 to 5e-3; C diagonal: 1e-4 to 5e-3 depending on task
    Learning rate is a tuned hyperparameter with a strong effect on whether models learn the automata.
assumptions (3)
  • standard math Products of simultaneously diagonalizable matrices commute.
    Core of Proposition 1 in Sec. 4.
  • domain assumption For the theoretical restriction, trained diagonal selective SSMs are assumed to implement the FSA-to-SSM mapping of Sec. 2 with B=0 and one-hot orthogonal state encodings.
    Stated explicitly before Proposition 1 and in the Conclusion; if a model implements a different mapping, non-commutative automata are not excluded.
  • standard math Orthogonal state encodings exist for any finite set Q and can be embedded in R^{|Q|}.
    Used in the constructive mapping in Sec. 2.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the Expressiveness and Length Generalization of Selective State-Space Models on Regular Languages." pith.science (2026). https://pith.science/paper/CQLUIWK5

@misc{pith2026241219350,
  author       = {Pith},
  title        = {Pith review of: On the Expressiveness and Length Generalization of Selective State-Space Models on Regular Languages},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CQLUIWK5}},
  note         = {Machine review of arXiv:2412.19350}
}
read the original abstract

Selective state-space models (SSMs) are an emerging alternative to the Transformer, offering the unique advantage of parallel training and sequential inference. Although these models have shown promising performance on a variety of tasks, their formal expressiveness and length generalization properties remain underexplored. In this work, we provide insight into the workings of selective SSMs by analyzing their expressiveness and length generalization performance on regular language tasks, i.e., finite-state automaton (FSA) emulation. We address certain limitations of modern SSM-based architectures by introducing the Selective Dense State-Space Model (SD-SSM), the first selective SSM that exhibits perfect length generalization on a set of various regular language tasks using a single layer. It utilizes a dictionary of dense transition matrices, a softmax selection mechanism that creates a convex combination of dictionary matrices at each time step, and a readout consisting of layer normalization followed by a linear map. We then proceed to evaluate variants of diagonal selective SSMs by considering their empirical performance on commutative and non-commutative automata. We explain the experimental results with theoretical considerations. Our code is available at https://github.com/IBM/selective-dense-state-space-model.

Figures

Figures reproduced from arXiv: 2412.19350 by the authors.

Figure 1
Figure 1. The parity automaton with Q={Even, Odd} and Σ = {0, 1}. The automaton starts in the Even state, toggles on input 1, and makes no transition on input 0. where Q is a finite set of states, Σ is a finite input alphabet, δ : Q × Σ → Q is the transition function, qinit ∈ Q is a designated initial state, and F ⊆ Q is the set of accepting states. In this work, we are not interested in the set F, and qinit is only of limite… view at source ↗
Figure 2
Figure 2. The SD-SSM model consists of three main steps. [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Cayley diagrams of C2 ×C4 and the D4 automata, both with two actions: toggle (blue) and move (red) (Carter 2009). C2 × C4 is commutative. Starting at any state, ap￾plying toggle followed by move results in the same state as move followed by toggle. The same does not hold for D4. Variants of C Diagonal SD-SSM B = 0? Yes No No Readout Linear Nonlin. Linear Nonlin. Linear C2 × C30 100 87.6 65.8 81.7 100 D30 8.35 8.35 1… view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. SHiPPO: Recurrent Memory with Transported Polynomial Projections

    cs.LG 2026-07 conditional novelty 7.0 of 10

    SHiPPO transports HiPPO coefficient memories via right actions into Sylvester dynamics, and diagnostics show this recovers order-sensitive memory changes that high-rank writes cannot.

Reference graph

Works this paper leans on

46 extracted references · 35 canonical work pages · cited by 1 Pith paper

  1. [1]

    , " * write output.state after.block = add.period write newline

    ENTRY address archivePrefix author booktitle chapter edition editor eid eprint howpublished institution isbn journal key month note number organization pages publisher school series title type volume year label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'before.a...

    work page

  2. [2]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in capitalize " " * FUNCT...

  3. [3]

    L.; Kiros, J

    Ba, J. L.; Kiros, J. R.; and Hinton, G. E. 2016. Layer Normalization . arXiv preprint arXiv:1607.06450

    arXiv 2016

  4. [4]

    Bhattamishra, S.; Ahuja, K.; and Goyal, N. 2020. On the Ability and Limitations of Transformers to Recognize Formal Languages . In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing ( EMNLP ) , 7096--7116. Association for Computational Linguistics

    work page 2020

  5. [5]

    Blelloch, G. E. 1990. Prefix Sums and Their Applications

    work page 1990

  6. [6]

    Carter, N. C. 2009. Visual group theory. Classroom resource materials. Washington, D.C.: Mathematical Association of America

    work page 2009

  7. [7]

    M.; Orvieto, A.; Walker, B.; Salvi, C.; and Lyons, T

    Cirone, N. M.; Orvieto, A.; Walker, B.; Salvi, C.; and Lyons, T. 2024. Theoretical Foundations of Deep Selective State - Space Models . arXiv preprint arXiv:2402.19047

    arXiv 2024

  8. [8]

    Dao, T. 2024. Flash A ttention-2: Faster Attention with Better Parallelism and Work Partitioning. In International Conference on Learning Representations (ICLR)

    2024

Show all 46 references
  1. [9]

    L.; Fernando, A.; Botev, A.; Cristian-Muraru, G.; Gu, A.; Haroun, R.; Berrada, L.; Chen, Y.; Srinivasan, S.; Desjardins, G.; Doucet, A.; Budden, D.; Teh, Y

    De, S.; Smith, S. L.; Fernando, A.; Botev, A.; Cristian-Muraru, G.; Gu, A.; Haroun, R.; Berrada, L.; Chen, Y.; Srinivasan, S.; Desjardins, G.; Doucet, A.; Budden, D.; Teh, Y. W.; Pascanu, R.; De Freitas, N.; and Gulcehre, C. 2024. Griffin: Mixing Gated Linear Recurrences with ...

    2024 arXiv

  2. [10]

    K.; Catt, E.; Cundy, C.; Hutter, M.; Legg, S.; Veness, J.; and Ortega, P

    Delétang, G.; Ruoss, A.; Grau-Moya, J.; Genewein, T.; Wenliang, L. K.; Catt, E.; Cundy, C.; Hutter, M.; Legg, S.; Veness, J.; and Ortega, P. A. 2023. Neural Networks and the Chomsky Hierarchy . In The Eleventh International Conference on Learning Representations ( ICLR )

    2023

  3. [11]

    Dewdney, A. K. 1977. Threshold matrices and the state assignment problem for neural nets. In Proceedings of the 8th SouthEastern Conference on Combinatorics, Graph Theory and Computing, 227–245

    1977

  4. [12]

    Elman, J. L. 1990. Finding Structure in Time . Cognitive Science, 14(2): 179--211

    1990

  5. [13]

    Fan, T.-H.; Chi, T.-C.; and Rudnicky, A. I. 2024. Advancing Regular Language Reasoning in Linear Recurrent Neural Networks . In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics : Human Language Technologies ( Vol...

    2024

  6. [14]

    Y.; Dao, T.; Saab, K

    Fu, D. Y.; Dao, T.; Saab, K. K.; Thomas, A. W.; Rudra, A.; and Ré, C. 2023. Hungry Hungry Hippos : Towards Language Modeling with State Space Models . In International Conference on Learning Representations ( ICLR )

    2023

  7. [15]

    K.; Zela, A.; Hutter, F.; and Pontil, M

    Grazzi, R.; Siems, J.; Franke, J. K.; Zela, A.; Hutter, F.; and Pontil, M. 2024. Unlocking State-Tracking in Linear RNN s Through Negative Eigenvalues. In NeurIPS 2024 Workshop on Mathematics of Modern Machine Learning

    2024

  8. [16]

    Gu, A.; and Dao, T. 2023. Mamba: Linear - Time Sequence Modeling with Selective State Spaces . arXiv preprint arXiv:2312.00752

    2023 arXiv

  9. [17]

    Gu, A.; Dao, T.; Ermon, S.; Rudra, A.; and Re, C. 2020. HiPPO : Recurrent Memory with Optimal Polynomial Projections . In Advances in Neural Information Processing Systems ( NeurIPS ) , volume 33, 1474--1487

    2020

  10. [18]

    Gu, A.; Goel, K.; Gupta, A.; and R \'e , C. 2022. On the Parameterization and Initialization of Diagonal State Space Models. In Advances in Neural Information Processing Systems (NeurIPS), volume 35, 35971--35983

    2022

  11. [19]

    Gu, A.; Goel, K.; and Ré, C. 2022. Efficiently Modeling Long Sequences with Structured State Spaces . In International Conference on Learning Representations ( ICLR )

    2022

  12. [20]

    Gu, A.; Johnson, I.; Goel, K.; Saab, K.; Dao, T.; Rudra, A.; and Ré, C. 2021. Combining Recurrent , Convolutional , and Continuous -time Models with Linear State - Space Layers . In Advances in Neural Information Processing Systems ( NeurIPS ) , volume 34, 572--585

    2021

  13. [21]

    Gupta, A.; Gu, A.; and Berant, J. 2022. Diagonal State Spaces are as Effective as Structured State Spaces . In Advances in Neural Information Processing Systems ( NeurIPS ) , volume 35, 22982--22994

    2022

  14. [22]

    Hahn, M. 2020. Theoretical Limitations of Self - Attention in Neural Sequence Models . Transactions of the Association for Computational Linguistics, 8: 156--171

    2020

  15. [23]

    Hochreiter, S.; and Schmidhuber, J. 1997. Long Short - Term Memory . Neural Computation, 9(8): 1735--1780

    1997

  16. [24]

    Indyk, P. 1995. Optimal simulation of automata by neural nets. In STACS 95, 337--348. Berlin, Heidelberg: Springer Berlin Heidelberg

    1995

  17. [25]

    Joulin, A.; and Mikolov, T. 2015. Inferring algorithmic patterns with stack-augmented recurrent nets. In Advances in Neural Information Processing Systems (NeurIPS), 190–198. Cambridge, MA, USA: MIT Press

    2015

  18. [26]

    Krohn, K.; and Rhodes, J. 1965. Algebraic Theory of Machines . I . Prime Decomposition Theorem for Finite Semigroups and Machines . Transactions of the American Mathematical Society, 116: 450--464

    1965

  19. [27]

    T.; Goel, S.; Krishnamurthy, A.; and Zhang, C

    Liu, B.; Ash, J. T.; Goel, S.; Krishnamurthy, A.; and Zhang, C. 2023. Transformers Learn Shortcuts to Automata . In The Eleventh International Conference on Learning Representations ( ICLR )

    2023

  20. [28]

    Martin, E.; and Cundy, C. 2018. Parallelizing Linear Recurrent Neural Nets Over Sequence Length . In International Conference on Learning Representations ( ICLR )

    2018

  21. [29]

    Merrill, W.; Petty, J.; and Sabharwal, A. 2024. The Illusion of State in State - Space Models . In International Conference on Machine Learning ( ICML )

    2024

  22. [30]

    Merrill, W.; and Sabharwal, A. 2023. The Parallelism Tradeoff : Limitations of Log - Precision Transformers . Transactions of the Association for Computational Linguistics, 11: 531--545

    2023

  23. [31]

    Minsky, M. 1954. Neural Nets and the Brain Model Problem. Ph.D. thesis, Princeton University, Austin

    1954

  24. [32]

    Minsky, M. L. 1967. Computation: finite and infinite machines. USA: Prentice-Hall, Inc

    1967

  25. [33]

    Orvieto, A.; De, S.; Gulcehre, C.; Pascanu, R.; and Smith, S. L. 2024. Universality of Linear Recurrences Followed by Non -linear Projections : Finite - Width Guarantees and Benefits of Complex Eigenvalues . In International Conference on Machine Learning ( ICML ) . PMLR

    2024

  26. [34]

    L.; Gu, A.; Fernando, A.; Gulcehre, C.; Pascanu, R.; and De, S

    Orvieto, A.; Smith, S. L.; Gu, A.; Fernando, A.; Gulcehre, C.; Pascanu, R.; and De, S. 2023. Resurrecting Recurrent Neural Networks for Long Sequences . In International Conference on Machine Learning ( ICML ) . PMLR

    2023

  27. [35]

    Y.; Dao, T.; Baccus, S.; Bengio, Y.; Ermon, S.; and Ré, C

    Poli, M.; Massaroli, S.; Nguyen, E.; Fu, D. Y.; Dao, T.; Baccus, S.; Bengio, Y.; Ermon, S.; and Ré, C. 2023. Hyena Hierarchy : Towards Larger Convolutional Language Models . arXiv preprint arXiv:2302.10866

    2023 arXiv

  28. [36]

    Ruoss, A.; Delétang, G.; Genewein, T.; Grau-Moya, J.; Csordás, R.; Bennani, M.; Legg, S.; and Veness, J. 2023. Randomized Positional Encodings Boost Length Generalization of Transformers . In Proceedings of the 61st Annual Meeting of the Association for Computational Linguisti...

    2023

  29. [37]

    Sarrof, Y.; Veitsman, Y.; and Hahn, M. 2024. The Expressive Capacity of State Space Models: A Formal Language Perspective. arXiv preprint: 2405.17394

    2024

  30. [38]

    Siegelmann, H.; and Sontag, E. 1995. On the Computational Power of Neural Nets. Journal of Computer and System Sciences, 50(1): 132--150

    1995

  31. [39]

    Smith, J. T. H.; Warrington, A.; and Linderman, S. W. 2023. Simplified State Space Layers for Sequence Modeling . In The Eleventh International Conference on Learning Representations ( ICLR )

    2023

  32. [40]

    Straubing, H. 1994. Finite automata, formal logic, and circuit complexity. CHE: Birkhauser Verlag

    1994

  33. [41]

    Strobl, L.; Merrill, W.; Weiss, G.; Chiang, D.; and Angluin, D. 2024. What Formal Languages Can Transformers Express ? A Survey . Transactions of the Association for Computational Linguistics, 12

    2024

  34. [42]

    Suzgun, M.; Gehrmann, S.; Belinkov, Y.; and Shieber, S. M. 2019. Memory-Augmented Recurrent Neural Networks Can Learn Generalized Dyck Languages. arXiv preprint arXiv:1911.03329

    2019 arXiv

  35. [43]

    Svete, A.; and Cotterell, R. 2023. Efficiently Representing Finite-state Automata With Recurrent Neural Networks. arXiv preprint arXiv:2310.05161v3

    2023 arXiv

  36. [44]

    Terzić, A.; Hersche, M.; Camposampiero, G.; Hofmann, T.; Sebastian, A.; and Rahimi, A. 2024. On the Expressiveness and Length Generalization of Selective State-Space Models on Regular Languages. arXiv preprint

    2024

  37. [45]

    N.; Kaiser, L.; and Polosukhin, I

    Vaswani, A.; Shazeer, N.; Parmar, N.; Uszkoreit, J.; Jones, L.; Gomez, A. N.; Kaiser, L.; and Polosukhin, I. 2017. Attention Is All You Need . In Advances in Neural Information Processing Systems ( NeurIPS ) , volume 30

    2017

  38. [46]

    Zubić, N.; Soldá, F.; Sulser, A.; and Scaramuzza, D. 2024. Limits of Deep Learning : Sequence Modeling through the Lens of Complexity Theory . arXiv preprint arXiv:2405.16674

    2024 arXiv

Pith tools

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