Buchumschlag

The Power of Hard Attention Transformers on Data Sequences: A Formal Language Theoretic Perspective

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Bergsträßer, Pascal, Köcher, Chris, Lin, Anthony Widjaja, Zetzsche, Georg
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Formal Languages and Automata Theory
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

The Counting Power of Transformers
von: Sälzer, Marco, et al.
Veröffentlicht: (2025)

The complexity of separability for semilinear sets and Parikh automata
von: Collins, Elias Rojas, et al.
Veröffentlicht: (2024)

Fast Ramsey Quantifier Elimination in LIRA (with applications to liveness checking)
von: Lichtner, Kilian, et al.
Veröffentlicht: (2025)

Length Generalization Bounds for Transformers
von: Yang, Andy, et al.
Veröffentlicht: (2026)

Softmax Transformers are Turing-Complete
von: Jiang, Hongjian, et al.
Veröffentlicht: (2025)

Infinite-state Games with Energy Objectives Beyond Counters
von: Sağlam, Irmak, et al.
Veröffentlicht: (2026)

Transformers are Inherently Succinct
von: Bergsträßer, Pascal, et al.
Veröffentlicht: (2025)

Bounded treewidth, multiple context-free grammars, and downward closures
von: Aiswarya, C., et al.
Veröffentlicht: (2025)

Directed Regular and Context-Free Languages
von: Ganardi, Moses, et al.
Veröffentlicht: (2024)

Reachability in Trace-Pushdown Systems
von: Köcher, Chris, et al.
Veröffentlicht: (2025)

Well-Behaved (Co)algebraic Semantics of Regular Expressions in Dafny
von: Zetzsche, Stefan, et al.
Veröffentlicht: (2024)

Separability in Büchi Vass and Singly Non-Linear Systems of Inequalities
von: Baumann, Pascal, et al.
Veröffentlicht: (2024)

Existential Definability over the Subword Ordering
von: Baumann, Pascal, et al.
Veröffentlicht: (2022)

Certified Symbolic Finite Transducers: Formalization and Applications to String Analysis
von: Kan, Shuanglong, et al.
Veröffentlicht: (2025)

Slice closures of indexed languages and word equations with counting constraints
von: Ciobanu, Laura, et al.
Veröffentlicht: (2024)

A General Information Extraction Framework Based on Formal Languages
von: Schmid, Markus L.
Veröffentlicht: (2025)

Verifying Unboundedness via Amalgamation
von: Anand, Ashwani, et al.
Veröffentlicht: (2024)

Synthesis and Verification of Transformer Programs (Technical Report)
von: Jiang, Hongjian, et al.
Veröffentlicht: (2026)

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

Measure-Theoretic Aspects of Star-Free and Group Languages
von: Sin'ya, Ryoma, et al.
Veröffentlicht: (2025)

A Formal Approach for Tuning Stochastic Oscillators
von: Ballarini, Paolo, et al.
Veröffentlicht: (2024)

WEX: Formal Specifications for Windows in Stream Processing
von: Hitarth, S, et al.
Veröffentlicht: (2022)

Closure Properties of General Grammars -- Formally Verified
von: Dvorak, Martin, et al.
Veröffentlicht: (2023)

General Decidability Results for Systems with Continuous Counters
von: Balasubramanian, A. R., et al.
Veröffentlicht: (2025)

Formalized Run-Time Analysis of Active Learning -- Coalgebraically in Agda
von: Wißmann, Thorsten
Veröffentlicht: (2026)

Mind the Gap: A Formal Investigation of the Relationship Between Log and Model Complexity -- Extended Version
von: Schalk, Patrizia, et al.
Veröffentlicht: (2025)

A Complexity Dichotomy for Semilinear Target Sets in Automata with One Counter
von: Shakiba, Yousef, et al.
Veröffentlicht: (2025)

Automated Formal Verification of Area-Optimized Safety Registers in Automotive SoCs
von: Zhang, Shuhang, et al.
Veröffentlicht: (2025)

AGDES: Automatic Generation of Dependent Event Sequences
von: Guzman, Alexander Obeid
Veröffentlicht: (2026)

An Automata-Based Method to Formalize Psychological Theories -- The Case Study of Lazarus and Folkman's Stress Theory
von: Finkel, Alain, et al.
Veröffentlicht: (2025)

A Unifying Perspective on Succinct Data Representations
von: Kimelfeld, Benny, et al.
Veröffentlicht: (2023)

Simulating Hard Attention Using Soft Attention
von: Yang, Andy, et al.
Veröffentlicht: (2024)

Realisability and Complementability of Multiparty Session Types
von: Di Giusto, Cinzia, et al.
Veröffentlicht: (2025)

The Expressive Capacity of State Space Models: A Formal Language Perspective
von: Sarrof, Yash, et al.
Veröffentlicht: (2024)

On the Expressive Power of Regular Expressions with Backreferences
von: Nogami, Taisei, et al.
Veröffentlicht: (2023)

The Power-Set Construction for Tree Algebras
von: Blumensath, Achim
Veröffentlicht: (2022)

On Decidability and Expressive Power of Fusion Grammars
von: Pshenitsyn, Tikhon
Veröffentlicht: (2023)

The complexity of downward closures of indexed languages
von: Mandel, Richard, et al.
Veröffentlicht: (2026)

Backward Responsibility in Transition Systems Using General Power Indices
von: Baier, Christel, et al.
Veröffentlicht: (2024)

Half-flips are 5-avoidable
von: Ochem, Pascal
Veröffentlicht: (2026)