Cover Image

The Expressive Capacity of State Space Models: A Formal Language Perspective

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Sarrof, Yash, Veitsman, Yana, Hahn, Michael
Format:	Preprint
Published:	2024
Subjects:	Computation and Language Formal Languages and Automata Theory Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

An Algebraic View of the Expressivity of Recurrent Language Models
by: Nowak, Franz, et al.
Published: (2026)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

What Formal Languages Can Transformers Express? A Survey
by: Strobl, Lena, et al.
Published: (2023)

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

The Power of Hard Attention Transformers on Data Sequences: A Formal Language Theoretic Perspective
by: Bergsträßer, Pascal, et al.
Published: (2024)

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

FormalAlign: Automated Alignment Evaluation for Autoformalization
by: Lu, Jianqiao, et al.
Published: (2024)

Extending AALpy with Passive Learning: A Generalized State-Merging Approach
by: von Berg, Benjamin, et al.
Published: (2025)

Bridging the Empirical-Theoretical Gap in Neural Network Formal Language Learning Using Minimum Description Length
by: Lan, Nur, et al.
Published: (2024)

Simulating Hard Attention Using Soft Attention
by: Yang, Andy, et al.
Published: (2024)

Constructing a BPE Tokenization DFA
by: Berglund, Martin, et al.
Published: (2024)

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

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

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

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

Learning Deterministic Finite-State Machines from the Prefixes of a Single String is NP-Complete
by: Dumitru, Radu Cosmin, et al.
Published: (2026)

A General Information Extraction Framework Based on Formal Languages
by: Schmid, Markus L.
Published: (2025)

Softmax Transformers are Turing-Complete
by: Jiang, Hongjian, et al.
Published: (2025)

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

On Decidability and Expressive Power of Fusion Grammars
by: Pshenitsyn, Tikhon
Published: (2023)

TR2MTL: LLM based framework for Metric Temporal Logic Formalization of Traffic Rules
by: Manas, Kumar, et al.
Published: (2024)

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

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

Comparing Spoken Languages using Paninian System of Sounds and Finite State Machines
by: Prabhu, Shreekanth M, et al.
Published: (2023)

NILE: Formalizing Natural-Language Descriptions of Formal Languages
by: Kneisel, Tristan, et al.
Published: (2026)

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

A Detailed Account of Compositional Automata Learning through Alphabet Refinement
by: Henry, Leo, et al.
Published: (2025)