Copertina

An Algebraic View of the Expressivity of Recurrent Language Models

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Nowak, Franz, Cotterell, Ryan, Boumasmoud, Reda
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Formal Languages and Automata Theory Computation and Language Machine Learning
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Transducing Language Models
di: Snæbjarnarson, Vésteinn, et al.
Pubblicazione: (2026)

On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning
di: Nowak, Franz, et al.
Pubblicazione: (2024)

A Fast Algorithm for Computing Prefix Probabilities
di: Nowak, Franz, et al.
Pubblicazione: (2023)

Transformers Can Represent $n$-gram Language Models
di: Svete, Anej, et al.
Pubblicazione: (2024)

The Expressive Capacity of State Space Models: A Formal Language Perspective
di: Sarrof, Yash, et al.
Pubblicazione: (2024)

Revisiting Padded Transformer Expressivity: Which Architectural Choices Matter and Which Don't
di: Svete, Anej, et al.
Pubblicazione: (2026)

Language Models over Canonical Byte-Pair Encodings
di: Vieira, Tim, et al.
Pubblicazione: (2025)

On The Expressivity of Recurrent Neural Cascades
di: Knorozova, Nadezda Alexandrovna, et al.
Pubblicazione: (2023)

Unique Hard Attention: A Tale of Two Sides
di: Jerad, Selim, et al.
Pubblicazione: (2025)

Context-Free Recognition with Transformers
di: Jerad, Selim, et al.
Pubblicazione: (2026)

A Close Analysis of the Subset Construction
di: Baburin, Ivan, et al.
Pubblicazione: (2024)

Transformers are Inherently Succinct
di: Bergsträßer, Pascal, et al.
Pubblicazione: (2025)

Exact Expressive Power of Transformers with Padding
di: Merrill, William, et al.
Pubblicazione: (2025)

Prefix Parsing is Just Parsing
di: Pasti, Clemente, et al.
Pubblicazione: (2026)

Sampling from Your Language Model One Byte at a Time
di: Hayase, Jonathan, et al.
Pubblicazione: (2025)

Unraveling Syntax: How Language Models Learn Context-Free Grammars
di: Schulz, Laura Ying, et al.
Pubblicazione: (2025)

From Formal Language Theory to Statistical Learning: Finite Observability of Subregular Languages
di: Hayashi, Katsuhiko, et al.
Pubblicazione: (2025)

On the Expressiveness of State Space Models via Temporal Logics
di: Alsmann, Eric, et al.
Pubblicazione: (2026)

MLRegTest: A Benchmark for the Machine Learning of Regular Languages
di: van der Poel, Sam, et al.
Pubblicazione: (2023)

Expressive Reward Synthesis with the Runtime Monitoring Language
di: Donnelly, Daniel, et al.
Pubblicazione: (2025)

Bifocal Attention: Harmonizing Geometric and Spectral Positional Embeddings for Algorithmic Generalization
di: Awadhiya, Kanishk
Pubblicazione: (2026)

Simulating Hard Attention Using Soft Attention
di: Yang, Andy, et al.
Pubblicazione: (2024)

DeltaProduct: Improving State-Tracking in Linear RNNs via Householder Products
di: Siems, Julien, et al.
Pubblicazione: (2025)

Unlocking State-Tracking in Linear RNNs Through Negative Eigenvalues
di: Grazzi, Riccardo, et al.
Pubblicazione: (2024)

Comparison of different Unique hard attention transformer models by the formal languages they can recognize
di: Ryvkin, Leonid
Pubblicazione: (2025)

Constructing a BPE Tokenization DFA
di: Berglund, Martin, et al.
Pubblicazione: (2024)

Correct and Optimal: the Regular Expression Inference Challenge
di: Valizadeh, Mojtaba, et al.
Pubblicazione: (2023)

The Counting Power of Transformers
di: Sälzer, Marco, et al.
Pubblicazione: (2025)

Algebraic Characterization of FO-definable Languages of Higher-Dimensional Automata
di: Erlich, Enzo, et al.
Pubblicazione: (2026)

On the Expressive Power of Regular Expressions with Backreferences
di: Nogami, Taisei, et al.
Pubblicazione: (2023)

On Decidability and Expressive Power of Fusion Grammars
di: Pshenitsyn, Tikhon
Pubblicazione: (2023)

Continuous Diffusion Models Can Obey Formal Syntax
di: Kim, Jinwoo, et al.
Pubblicazione: (2026)

Warm Starting State-Space Models with Automata Learning
di: Fishell, William, et al.
Pubblicazione: (2026)

Stochastic Alignments: Matching an Observed Trace to Stochastic Process Models
di: Li, Tian, et al.
Pubblicazione: (2025)

SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism
di: Marzouk, Reda, et al.
Pubblicazione: (2025)

MinMax Recurrent Neural Cascades
di: Ronca, Alessandro
Pubblicazione: (2026)

The Illusion of State in State-Space Models
di: Merrill, William, et al.
Pubblicazione: (2024)

Formal-LLM: Integrating Formal Language and Natural Language for Controllable LLM-based Agents
di: Li, Zelong, et al.
Pubblicazione: (2024)

On the Expressivity of Recurrent Neural Cascades with Identity
di: Knorozova, Nadezda Alexandrovna, et al.
Pubblicazione: (2024)

Probabilistic Regular Tree Priors for Scientific Symbolic Reasoning
di: Schneider, Tim, et al.
Pubblicazione: (2023)