Copertina

Length Generalization Bounds for Transformers

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Yang, Andy, Bergsträßer, Pascal, Zetzsche, Georg, Chiang, David, Lin, Anthony W.
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Machine Learning Formal Languages and Automata Theory Logic in Computer Science
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

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

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

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

Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages
di: Yang, Andy, et al.
Pubblicazione: (2023)

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

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

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

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

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

An efficient quantifier elimination procedure for Presburger arithmetic
di: Haase, Christoph, et al.
Pubblicazione: (2024)

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

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

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

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

The complexity of downward closures of indexed languages
di: Mandel, Richard, et al.
Pubblicazione: (2026)

Parikh's Theorem Made Symbolic
di: Hague, Matthew, et al.
Pubblicazione: (2023)

RNN Generalization to Omega-Regular Languages
di: Pert, Charles, et al.
Pubblicazione: (2025)

HornStr: Invariant Synthesis for Regular Model Checking as Constrained Horn Clauses(Technical Report)
di: Jiang, Hongjian, et al.
Pubblicazione: (2025)

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

Learning Quantitative Automata Modulo Theories
di: Hsiung, Eric, et al.
Pubblicazione: (2024)

On the Impact of the Communication Model on Realisability
di: Di Giusto, Cinzia, et al.
Pubblicazione: (2025)

Language Inclusion for Boundedly-Ambiguous Vector Addition Systems is Decidable
di: Czerwiński, Wojciech, et al.
Pubblicazione: (2022)

Extended CTG Generalization and Dynamic Adjustment of Generalization Strategies in IC3
di: Su, Yuheng, et al.
Pubblicazione: (2025)

Effective MSO-Definability for Tree-width Bounded Models of an Inductive Separation Logic of Relations
di: Bueri, Lucas, et al.
Pubblicazione: (2024)

The Finite Length Property of the Rado Graph and Friends
di: Yang, Jingjie, et al.
Pubblicazione: (2026)

The Complexity of Generalized HyperLTL with Stuttering and Contexts
di: Regaud, Gaëtan, et al.
Pubblicazione: (2025)

Random Graph Generation in Context-Free Graph Languages
di: Vastarini, Federico, et al.
Pubblicazione: (2024)

Generalized Parameter Lifting: Finer Abstractions for Parametric Markov Chains
di: Heck, Linus, et al.
Pubblicazione: (2025)

Model-Free Learning of Safe yet Effective Controllers
di: Bozkurt, Alper Kamil, et al.
Pubblicazione: (2021)

Dynamic Programming for Symbolic Boolean Realizability and Synthesis
di: Lin, Yi, et al.
Pubblicazione: (2024)

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

The Big-O Problem for Max-Plus Automata is Decidable (PSPACE-Complete)
di: Daviaud, Laure, et al.
Pubblicazione: (2023)

Determinisation and Unambiguisation of Polynomially-Ambiguous Rational Weighted Automata
di: Jecker, Ismaël, et al.
Pubblicazione: (2023)

A Direct Translation from LTL with Past to Deterministic Rabin Automata
di: Azzopardi, Shaun, et al.
Pubblicazione: (2024)

Automatic Generation of Safety-compliant Linear Temporal Logic via Large Language Model: A Self-supervised Framework
di: Li, Junle, et al.
Pubblicazione: (2025)

Improved Algorithm for Reachability in $d$-VASS
di: Fu, Yuxi, et al.
Pubblicazione: (2024)

A cyclic proof system for Guarded Kleene Algebra with Tests (full version)
di: Rooduijn, Jan, et al.
Pubblicazione: (2024)

A proof theory of right-linear (omega-)grammars via cyclic proofs
di: Das, Anupam, et al.
Pubblicazione: (2024)

The Alternation Hierarchy of First-Order Logic on Words is Decidable
di: Barloy, Corentin, et al.
Pubblicazione: (2025)