Cover Image

The Counting Power of Transformers

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Sälzer, Marco, Köcher, Chris, Kozachinskiy, Alexander, Zetzsche, Georg, Lin, Anthony Widjaja
Format:	Preprint
Published:	2025
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

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

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

The complexity of separability for semilinear sets and Parikh automata
by: Collins, Elias Rojas, et al.
Published: (2024)

Length Generalization Bounds for Transformers
by: Yang, Andy, et al.
Published: (2026)

Synthesis and Verification of Transformer Programs (Technical Report)
by: Jiang, Hongjian, et al.
Published: (2026)

Directed Regular and Context-Free Languages
by: Ganardi, Moses, et al.
Published: (2024)

Infinite-state Games with Energy Objectives Beyond Counters
by: Sağlam, Irmak, et al.
Published: (2026)

Language Generation: Complexity Barriers and Implications for Learning
by: Arenas, Marcelo, et al.
Published: (2025)

Reachability in Trace-Pushdown Systems
by: Köcher, Chris, et al.
Published: (2025)

Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformers
by: Yang, Andy, et al.
Published: (2024)

Fast Ramsey Quantifier Elimination in LIRA (with applications to liveness checking)
by: Lichtner, Kilian, et al.
Published: (2025)

Bounded treewidth, multiple context-free grammars, and downward closures
by: Aiswarya, C., et al.
Published: (2025)

Well-Behaved (Co)algebraic Semantics of Regular Expressions in Dafny
by: Zetzsche, Stefan, et al.
Published: (2024)

The Role of Logic and Automata in Understanding Transformers
by: Lin, Anthony W., et al.
Published: (2025)

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

Slice closures of indexed languages and word equations with counting constraints
by: Ciobanu, Laura, et al.
Published: (2024)

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

Existential Definability over the Subword Ordering
by: Baumann, Pascal, et al.
Published: (2022)

Transformers as Transducers
by: Strobl, Lena, et al.
Published: (2024)

Partial Answer of How Transformers Learn Automata
by: Zhang, Tiantian
Published: (2025)

Why Are Linear RNNs More Parallelizable?
by: Merrill, William, et al.
Published: (2026)

General Decidability Results for Systems with Continuous Counters
by: Balasubramanian, A. R., et al.
Published: (2025)

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

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

DeltaProduct: Improving State-Tracking in Linear RNNs via Householder Products
by: Siems, Julien, 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)

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

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

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

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

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

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

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

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

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

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

Transformers in Uniform TC$^0$
by: Chiang, David
Published: (2024)

A Complexity Dichotomy for Semilinear Target Sets in Automata with One Counter
by: Shakiba, Yousef, et al.
Published: (2025)

Power of Counting by Nonuniform Families of Polynomial-Size Finite Automata
by: Yamakami, Tomoyuki
Published: (2023)