{"ID":2921146,"CreatedAt":"2026-06-02T02:42:49.606572591Z","UpdatedAt":"2026-06-04T06:21:04.369492701Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.01765","arxiv_id":"2606.01765","title":"An Algebraic View of the Expressivity of Recurrent Language Models","abstract":"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.","short_abstract":"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 alg...","url_abs":"https://arxiv.org/abs/2606.01765","url_pdf":"https://arxiv.org/pdf/2606.01765v1","authors":"[\"Franz Nowak\",\"Ryan Cotterell\",\"Reda Boumasmoud\"]","published":"2026-06-01T06:47:58Z","proceeding":"cs.FL","tasks":"[\"cs.FL\",\"cs.CL\",\"cs.LG\"]","methods":"[\"Language Model\"]","has_code":false}