Copertina

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

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Yang, Andy, Cadilhac, Michaël, Chiang, David
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	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

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

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

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

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

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

Simulating Hard Attention Using Soft Attention
di: Yang, Andy, et al.
Pubblicazione: (2024)

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

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

Length Generalization Bounds for Transformers
di: Yang, Andy, et al.
Pubblicazione: (2026)

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

A Diamond Structure in the Transducer Hierarchy
di: Kaufmann, Noah
Pubblicazione: (2021)

A Hierarchy of Nondeterminism
di: Radi, Bader Abu, et al.
Pubblicazione: (2022)

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

Transformers as Transducers
di: Strobl, Lena, et al.
Pubblicazione: (2024)

Population Protocols over Ordered Agents
di: Blondin, Michael, et al.
Pubblicazione: (2026)

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

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

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

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

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

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

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

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

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

Explorability in Pushdown Automata
di: Bedi, Ayaan, et al.
Pubblicazione: (2025)

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

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

Cluster automata
di: Kornai, András
Pubblicazione: (2025)

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

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

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

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

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

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

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

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

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

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

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

Prefix Parsing is Just Parsing
di: Pasti, Clemente, et al.
Pubblicazione: (2026)