From the 1 of 5 linked papers with an AI index.
Showing cs.FLShow all
3 papers · 1 filter
cs.FL2026
A Compositional Theory of Causally Masked Transformers
Franz Nowak, Ryan Cotterell, Reda Boumasmoud
The paper develops an algebraic framework to characterize what decision problems finite‑precision, causally masked transformers can solve, linking attention mechanisms to memory re…
cs.FL2026
An Algebraic View of the Expressivity of Recurrent Language Models
Franz Nowak, Ryan Cotterell, Reda Boumasmoud
What formal languages can a recurrent neural language model recognize? Formal results in the literature conflict: some authors report Turing-completeness, while others show equival…
cs.FL2026
Transformers are Inherently Succinct
Pascal BergsträÃer, Ryan Cotterell, Anthony W. Lin
We study succinctness as a measure of the expressive power of transformers. Succinctness -- how compactly a formalism can describe a language relative to other formalisms -- is a c…