Copertina

Context-Free Recognition with Transformers

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Jerad, Selim, Svete, Anej, Hao, Sophie, Cotterell, Ryan, Merrill, William
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Machine Learning Computational Complexity Computation and Language Formal Languages and Automata Theory
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

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

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

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

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

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

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

Transformers in Uniform TC$^0$
di: Chiang, David
Pubblicazione: (2024)

Intersection and Union Hierarchies of Deterministic Context-Free Languages and Pumping Lemmas
di: Yamakami, Tomoyuki
Pubblicazione: (2021)

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

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

Visibly Recursive Automata
di: Dubrulle, Kévin, et al.
Pubblicazione: (2026)

Entropy of pebble automata and space complexity
di: Montoya, J. Andres
Pubblicazione: (2026)

Complexity of Fungal Automaton Prediction
di: Formenti, Enrico, et al.
Pubblicazione: (2026)

Regular Grammars as Effective Representations of Recognizable Sets of Series-Parallel Graphs
di: Bozga, Marius, et al.
Pubblicazione: (2026)

Embedding arbitrary Boolean circuits into fungal automata with arbitrary update sequences
di: Goles, Eric, et al.
Pubblicazione: (2026)

Proceedings of the 15th International Workshop on Non-Classical Models of Automata and Applications
di: Moreira, Nelma, et al.
Pubblicazione: (2025)

Unambiguous and Co-Nondeterministic Computations of Finite Automata and Pushdown Automata Families and the Effects of Multiple Counters
di: Yamakami, Tomoyuki
Pubblicazione: (2024)

On the complexity of computing Strahler numbers
di: Ganardi, Moses, et al.
Pubblicazione: (2025)

Complexity Aspects of the Extension of Wagner's Hierarchy to $k$-Partitions
di: Podolskii, Vladimir, et al.
Pubblicazione: (2024)

Regular Expressions with Backreferences and Lookaheads Capture NLOG
di: Uezato, Yuya
Pubblicazione: (2024)

Maximal Length Cellular Automata : A Survey
di: Adak, Sumit, et al.
Pubblicazione: (2024)

Trading Determinism for Noncommutativity in Edmonds' Problem
di: Arvind, V., et al.
Pubblicazione: (2024)

Constant-Space, Constant-Randomness Verifiers with Arbitrarily Small Error
di: Gezer, M. Utkan, et al.
Pubblicazione: (2020)

Between SC and LOGDCFL: Families of Languages Accepted by Logarithmic-Space Deterministic Auxiliary Depth-k Storage Automata
di: Yamakami, Tomoyuki
Pubblicazione: (2022)

Review of Automaton Learning Algorithms with Polynomial Complexity -- Completely Solved Examples
di: Haneef, Farah
Pubblicazione: (2024)

Complexity of Unary Exclusive Nondeterministic Finite Automata
di: Kutrib, Martin, et al.
Pubblicazione: (2024)

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

Proceedings 14th International Workshop on Non-Classical Models of Automata and Applications (NCMA 2024)
di: Manea, Florin, et al.
Pubblicazione: (2024)

Studying homing and synchronizing sequences for Timed Finite State Machines with output delays
di: Vinarskii, Evgenii, et al.
Pubblicazione: (2025)

The No Endmarker Theorem for One-Way Probabilistic Pushdown Automata
di: Yamakami, Tomoyuki
Pubblicazione: (2021)

Nondeterministic Auxiliary Depth-Bounded Storage Automata and Semi-Unbounded Fan-in Cascading Circuits
di: Yamakami, Tomoyuki
Pubblicazione: (2024)

Rational-Valued Affine Verifiers in Arthur--Merlin Proof Systems
di: Chen, Zeyu, et al.
Pubblicazione: (2025)

Synthesis of Timeline-Based Planning Strategies Avoiding Determinization
di: Acampora, Renato, et al.
Pubblicazione: (2024)

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

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

Geometric Characterization of Context-Free Intersections via the Inner Segment Dichotomy
di: Silva, Jorge Miguel
Pubblicazione: (2026)

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

Infinite Time Turing Machines and their Applications
di: Weerawarana, Rukmal, et al.
Pubblicazione: (2025)

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