Buchumschlag

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

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Yang, Andy, Cadilhac, Michaël, Chiang, David
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Computation and Language 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

A Factorization Theorem for Forest Algebras
von: Almagor, Shaull, et al.
Veröffentlicht: (2026)

Two-Way One-Counter Nets Revisited
von: Almagor, Shaull, et al.
Veröffentlicht: (2024)

Shuffles of Context-Free Languages along Regular Trajectories
von: Barloy, Corentin, et al.
Veröffentlicht: (2026)

The Alternation Hierarchy of First-Order Logic on Words is Decidable
von: Barloy, Corentin, et al.
Veröffentlicht: (2025)

Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformers
von: Yang, Andy, et al.
Veröffentlicht: (2024)

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

Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages
von: Yang, Andy, et al.
Veröffentlicht: (2023)

Transformers in Uniform TC$^0$
von: Chiang, David
Veröffentlicht: (2024)

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

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

A Diamond Structure in the Transducer Hierarchy
von: Kaufmann, Noah
Veröffentlicht: (2021)

A Hierarchy of Nondeterminism
von: Radi, Bader Abu, et al.
Veröffentlicht: (2022)

Intersection and Union Hierarchies of Deterministic Context-Free Languages and Pumping Lemmas
von: Yamakami, Tomoyuki
Veröffentlicht: (2021)

Transformers as Transducers
von: Strobl, Lena, et al.
Veröffentlicht: (2024)

Population Protocols over Ordered Agents
von: Blondin, Michael, et al.
Veröffentlicht: (2026)

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

A* shortest string decoding for non-idempotent semirings
von: Gorman, Kyle, et al.
Veröffentlicht: (2022)

Nondeterministic Auxiliary Depth-Bounded Storage Automata and Semi-Unbounded Fan-in Cascading Circuits
von: Yamakami, Tomoyuki
Veröffentlicht: (2024)

A Bionic Natural Language Parser Equivalent to a Pushdown Automaton
von: Wei, Zhenghao, et al.
Veröffentlicht: (2024)

LangSAT: A Novel Framework Combining NLP and Reinforcement Learning for SAT Solving
von: Pan, Muyu, et al.
Veröffentlicht: (2025)

RESTL: Reinforcement Learning Guided by Multi-Aspect Rewards for Signal Temporal Logic Transformation
von: Fang, Yue, et al.
Veröffentlicht: (2025)

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

Autoformalization in the Wild: Assessing LLMs on Real-World Mathematical Definitions
von: Zhang, Lan, et al.
Veröffentlicht: (2025)

Recursive numeral systems are highly regular and easy to process
von: Prasertsom, Ponrawee, et al.
Veröffentlicht: (2025)

Explorability in Pushdown Automata
von: Bedi, Ayaan, et al.
Veröffentlicht: (2025)

Reachability in symmetric VASS
von: Kamiński, Łukasz, et al.
Veröffentlicht: (2025)

Tutorial: $φ$-Transductions in OpenFst via the Gallic Semiring
von: Cognetta, Marco, et al.
Veröffentlicht: (2025)

Cluster automata
von: Kornai, András
Veröffentlicht: (2025)

MASA: LLM-Driven Multi-Agent Systems for Autoformalization
von: Zhang, Lan, et al.
Veröffentlicht: (2025)

Benchmarking Testing in Automated Theorem Proving
von: Kim, Jongyoon, et al.
Veröffentlicht: (2026)

Consistent Autoformalization for Constructing Mathematical Libraries
von: Zhang, Lan, et al.
Veröffentlicht: (2024)

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

Comparing Spoken Languages using Paninian System of Sounds and Finite State Machines
von: Prabhu, Shreekanth M, et al.
Veröffentlicht: (2023)

Transducing Language Models
von: Snæbjarnarson, Vésteinn, 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)

Synchronous Signal Temporal Logic for Decidable Verification of Cyber-Physical Systems
von: Roop, Partha, et al.
Veröffentlicht: (2026)

Self-Replicating Mechanical Universal Turing Machine
von: Lano, Ralph P.
Veröffentlicht: (2024)

Automata-based constraints for language model decoding
von: Koo, Terry, et al.
Veröffentlicht: (2024)

On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning
von: Nowak, Franz, et al.
Veröffentlicht: (2024)

Prefix Parsing is Just Parsing
von: Pasti, Clemente, et al.
Veröffentlicht: (2026)