Cover Image

On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Nowak, Franz, Svete, Anej, Butoi, Alexandra, Cotterell, Ryan
Format:	Preprint
Published:	2024
Subjects:	Computation and Language Formal Languages and Automata Theory
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

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

Context-Free Recognition with Transformers
by: Jerad, Selim, et al.
Published: (2026)

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

A Fast Algorithm for Computing Prefix Probabilities
by: Nowak, Franz, et al.
Published: (2023)

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

A Close Analysis of the Subset Construction
by: Baburin, Ivan, et al.
Published: (2024)

Prefix Parsing is Just Parsing
by: Pasti, Clemente, et al.
Published: (2026)

CoT-TL: Low-Resource Temporal Knowledge Representation of Planning Instructions Using Chain-of-Thought Reasoning
by: Manas, Kumar, et al.
Published: (2024)

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

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

On the Representation and State Complexity of Block Languages
by: Duarte, Guilherme, et al.
Published: (2024)

The Expressive Capacity of State Space Models: A Formal Language Perspective
by: Sarrof, Yash, et al.
Published: (2024)

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

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

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

Regular Languages in the Sliding Window Model
by: Ganardi, Moses, et al.
Published: (2024)

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

Reasoning about Reasoning: BAPO Bounds on Chain-of-Thought Token Complexity in LLMs
by: Tomlinson, Kiran, et al.
Published: (2026)

Passive Learning of Lattice Automata from Recurrent Neural Networks
by: Slimi, Jaouhar, et al.
Published: (2025)

Reasoning about Rare-Event Reachability in Stochastic Vector Addition Systems via Affine Vector Spaces
by: Jeppson, Joshua, et al.
Published: (2025)

Universally Wheeler Languages
by: Becker, Ruben, et al.
Published: (2025)

Quantitative Language Automata
by: Henzinger, Thomas A., et al.
Published: (2025)

Positive Varieties of Lattice Languages
by: Inoue, Yusuke, et al.
Published: (2025)

On the Separability Problem of VASS Reachability Languages
by: Keskin, Eren, et al.
Published: (2024)

Operational State Complexity of Block Languages
by: Duarte, Guilherme, et al.
Published: (2024)

On the Complexity of Language Membership for Probabilistic Words
by: Amarilli, Antoine, et al.
Published: (2025)

Stochastic Languages at Sub-stochastic Cost
by: Agarwal, Smayan, et al.
Published: (2025)

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

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

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

TuringQ: Benchmarking AI Comprehension in Theory of Computation
by: Zahraei, Pardis Sadat, et al.
Published: (2024)

Tokenization as Finite-State Transduction
by: Cognetta, Marco, et al.
Published: (2024)

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

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

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

Knee-Deep in C-RASP: A Transformer Depth Hierarchy
by: Yang, Andy, et al.
Published: (2025)

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

Explorability in Pushdown Automata
by: Bedi, Ayaan, et al.
Published: (2025)