Imagen de Portada

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

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Yang, Andy, Cadilhac, Michaël, Chiang, David
Formato:	Preprint
Publicado:	2025
Materias:	Computation and Language Formal Languages and Automata Theory
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

A Factorization Theorem for Forest Algebras
por: Almagor, Shaull, et al.
Publicado: (2026)

Two-Way One-Counter Nets Revisited
por: Almagor, Shaull, et al.
Publicado: (2024)

Shuffles of Context-Free Languages along Regular Trajectories
por: Barloy, Corentin, et al.
Publicado: (2026)

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

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

Simulating Hard Attention Using Soft Attention
por: Yang, Andy, et al.
Publicado: (2024)

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

Transformers in Uniform TC$^0$
por: Chiang, David
Publicado: (2024)

Length Generalization Bounds for Transformers
por: Yang, Andy, et al.
Publicado: (2026)

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

A Diamond Structure in the Transducer Hierarchy
por: Kaufmann, Noah
Publicado: (2021)

A Hierarchy of Nondeterminism
por: Radi, Bader Abu, et al.
Publicado: (2022)

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

Transformers as Transducers
por: Strobl, Lena, et al.
Publicado: (2024)

Population Protocols over Ordered Agents
por: Blondin, Michael, et al.
Publicado: (2026)

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

A* shortest string decoding for non-idempotent semirings
por: Gorman, Kyle, et al.
Publicado: (2022)

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

A Bionic Natural Language Parser Equivalent to a Pushdown Automaton
por: Wei, Zhenghao, et al.
Publicado: (2024)

LangSAT: A Novel Framework Combining NLP and Reinforcement Learning for SAT Solving
por: Pan, Muyu, et al.
Publicado: (2025)

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

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

Autoformalization in the Wild: Assessing LLMs on Real-World Mathematical Definitions
por: Zhang, Lan, et al.
Publicado: (2025)

Recursive numeral systems are highly regular and easy to process
por: Prasertsom, Ponrawee, et al.
Publicado: (2025)

Explorability in Pushdown Automata
por: Bedi, Ayaan, et al.
Publicado: (2025)

Reachability in symmetric VASS
por: Kamiński, Łukasz, et al.
Publicado: (2025)

Tutorial: $φ$-Transductions in OpenFst via the Gallic Semiring
por: Cognetta, Marco, et al.
Publicado: (2025)

Cluster automata
por: Kornai, András
Publicado: (2025)

MASA: LLM-Driven Multi-Agent Systems for Autoformalization
por: Zhang, Lan, et al.
Publicado: (2025)

Benchmarking Testing in Automated Theorem Proving
por: Kim, Jongyoon, et al.
Publicado: (2026)

Consistent Autoformalization for Constructing Mathematical Libraries
por: Zhang, Lan, et al.
Publicado: (2024)

Directed Regular and Context-Free Languages
por: Ganardi, Moses, et al.
Publicado: (2024)

Comparing Spoken Languages using Paninian System of Sounds and Finite State Machines
por: Prabhu, Shreekanth M, et al.
Publicado: (2023)

Transducing Language Models
por: Snæbjarnarson, Vésteinn, et al.
Publicado: (2026)

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

Synchronous Signal Temporal Logic for Decidable Verification of Cyber-Physical Systems
por: Roop, Partha, et al.
Publicado: (2026)

Self-Replicating Mechanical Universal Turing Machine
por: Lano, Ralph P.
Publicado: (2024)

Automata-based constraints for language model decoding
por: Koo, Terry, et al.
Publicado: (2024)

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

Prefix Parsing is Just Parsing
por: Pasti, Clemente, et al.
Publicado: (2026)