An Algebraic View of the Expressivity of Recurrent Language Models
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910279923662848 |
|---|---|
| author | Nowak, Franz Cotterell, Ryan Boumasmoud, Reda |
| author_facet | Nowak, Franz Cotterell, Ryan Boumasmoud, Reda |
| contents | What formal languages can a recurrent neural language model recognize? Formal results in the literature conflict: some authors report Turing-completeness, while others show equivalence to regular languages. The reason for this discrepancy is that the underlying arithmetic model differs. The paper develops a unified algebraic account of the expressivity of recurrent neural networks, starting with a formal account of various arithmetic models. This account reduces expressivity to an algebraic question, e.g., whether a network's syntactic monoid divides a certain wreath product. As a case study, the paper revisits diagonal state-space models: the same architecture cannot implement an even-modulus counter once floating-point recurrences are enforced, yet realizes every even-modulus counter under unsigned-integer quantization. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2606_01765 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | An Algebraic View of the Expressivity of Recurrent Language Models Nowak, Franz Cotterell, Ryan Boumasmoud, Reda Formal Languages and Automata Theory Computation and Language Machine Learning What formal languages can a recurrent neural language model recognize? Formal results in the literature conflict: some authors report Turing-completeness, while others show equivalence to regular languages. The reason for this discrepancy is that the underlying arithmetic model differs. The paper develops a unified algebraic account of the expressivity of recurrent neural networks, starting with a formal account of various arithmetic models. This account reduces expressivity to an algebraic question, e.g., whether a network's syntactic monoid divides a certain wreath product. As a case study, the paper revisits diagonal state-space models: the same architecture cannot implement an even-modulus counter once floating-point recurrences are enforced, yet realizes every even-modulus counter under unsigned-integer quantization. |
| title | An Algebraic View of the Expressivity of Recurrent Language Models |
| topic | Formal Languages and Automata Theory Computation and Language Machine Learning |
| url | https://arxiv.org/abs/2606.01765 |