Image de couverture de livre

Knee-Deep in C-RASP: A Transformer Depth Hierarchy

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Yang, Andy, Cadilhac, Michaël, Chiang, David
Format:	Preprint
Publié:	2025
Sujets:	Computation and Language Formal Languages and Automata Theory
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

A Factorization Theorem for Forest Algebras
par: Almagor, Shaull, et autres
Publié: (2026)

Two-Way One-Counter Nets Revisited
par: Almagor, Shaull, et autres
Publié: (2024)

Shuffles of Context-Free Languages along Regular Trajectories
par: Barloy, Corentin, et autres
Publié: (2026)

The Alternation Hierarchy of First-Order Logic on Words is Decidable
par: Barloy, Corentin, et autres
Publié: (2025)

Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformers
par: Yang, Andy, et autres
Publié: (2024)

Simulating Hard Attention Using Soft Attention
par: Yang, Andy, et autres
Publié: (2024)

Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages
par: Yang, Andy, et autres
Publié: (2023)

Transformers in Uniform TC$^0$
par: Chiang, David
Publié: (2024)

Length Generalization Bounds for Transformers
par: Yang, Andy, et autres
Publié: (2026)

Complexity Aspects of the Extension of Wagner's Hierarchy to $k$-Partitions
par: Podolskii, Vladimir, et autres
Publié: (2024)

A Diamond Structure in the Transducer Hierarchy
par: Kaufmann, Noah
Publié: (2021)

A Hierarchy of Nondeterminism
par: Radi, Bader Abu, et autres
Publié: (2022)

Intersection and Union Hierarchies of Deterministic Context-Free Languages and Pumping Lemmas
par: Yamakami, Tomoyuki
Publié: (2021)

Transformers as Transducers
par: Strobl, Lena, et autres
Publié: (2024)

Population Protocols over Ordered Agents
par: Blondin, Michael, et autres
Publié: (2026)

The Power of Hard Attention Transformers on Data Sequences: A Formal Language Theoretic Perspective
par: Bergsträßer, Pascal, et autres
Publié: (2024)

A* shortest string decoding for non-idempotent semirings
par: Gorman, Kyle, et autres
Publié: (2022)

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

A Bionic Natural Language Parser Equivalent to a Pushdown Automaton
par: Wei, Zhenghao, et autres
Publié: (2024)

LangSAT: A Novel Framework Combining NLP and Reinforcement Learning for SAT Solving
par: Pan, Muyu, et autres
Publié: (2025)

RESTL: Reinforcement Learning Guided by Multi-Aspect Rewards for Signal Temporal Logic Transformation
par: Fang, Yue, et autres
Publié: (2025)

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

Autoformalization in the Wild: Assessing LLMs on Real-World Mathematical Definitions
par: Zhang, Lan, et autres
Publié: (2025)

Recursive numeral systems are highly regular and easy to process
par: Prasertsom, Ponrawee, et autres
Publié: (2025)

Explorability in Pushdown Automata
par: Bedi, Ayaan, et autres
Publié: (2025)

Reachability in symmetric VASS
par: Kamiński, Łukasz, et autres
Publié: (2025)

Tutorial: $φ$-Transductions in OpenFst via the Gallic Semiring
par: Cognetta, Marco, et autres
Publié: (2025)

Cluster automata
par: Kornai, András
Publié: (2025)

MASA: LLM-Driven Multi-Agent Systems for Autoformalization
par: Zhang, Lan, et autres
Publié: (2025)

Benchmarking Testing in Automated Theorem Proving
par: Kim, Jongyoon, et autres
Publié: (2026)

Consistent Autoformalization for Constructing Mathematical Libraries
par: Zhang, Lan, et autres
Publié: (2024)

Directed Regular and Context-Free Languages
par: Ganardi, Moses, et autres
Publié: (2024)

Comparing Spoken Languages using Paninian System of Sounds and Finite State Machines
par: Prabhu, Shreekanth M, et autres
Publié: (2023)

Transducing Language Models
par: Snæbjarnarson, Vésteinn, et autres
Publié: (2026)

Bridging the Empirical-Theoretical Gap in Neural Network Formal Language Learning Using Minimum Description Length
par: Lan, Nur, et autres
Publié: (2024)

Synchronous Signal Temporal Logic for Decidable Verification of Cyber-Physical Systems
par: Roop, Partha, et autres
Publié: (2026)

Self-Replicating Mechanical Universal Turing Machine
par: Lano, Ralph P.
Publié: (2024)

Automata-based constraints for language model decoding
par: Koo, Terry, et autres
Publié: (2024)

On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning
par: Nowak, Franz, et autres
Publié: (2024)

Prefix Parsing is Just Parsing
par: Pasti, Clemente, et autres
Publié: (2026)