Title: An Algebraic Perspective on the Expressive Power of Recurrent Language Models

Abstract: Which formal languages are within the recognition capabilities of recurrent neural language models? Existing literature presents conflicting findings: certain studies assert Turing-completeness, whereas others demonstrate equivalence to regular languages. This divergence arises from differences in the underlying arithmetic models employed. This work establishes a unified algebraic framework to analyze the expressivity of recurrent neural networks, beginning with a formal characterization of diverse arithmetic models. By translating expressivity into an algebraic problem—such as determining whether a network’s syntactic monoid divides a specific wreath product—this approach clarifies the theoretical landscape. As a practical application, the paper re-examines diagonal state-space models. It reveals that while floating-point recurrences prevent the implementation of an even-modulus counter, the same architecture successfully realizes every even-modulus counter when unsigned-integer quantization is applied.

Source: arXiv Generated at: 2026-06-02 00:00:00 UTC