Imagen de Portada

Language Generation: Complexity Barriers and Implications for Learning

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Arenas, Marcelo, Barceló, Pablo, Cofré, Luis, Kozachinskiy, Alexander
Formato:	Preprint
Publicado:	2025
Materias:	Computation and Language Artificial Intelligence Formal Languages and Automata Theory Machine Learning
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

The Counting Power of Transformers
por: Sälzer, Marco, et al.
Publicado: (2025)

$L^*LM$: Learning Automata from Examples using Natural Language Oracles
por: Vazquez-Chanlatte, Marcell, et al.
Publicado: (2024)

InductionBench: LLMs Fail in the Simplest Complexity Class
por: Hua, Wenyue, et al.
Publicado: (2025)

Formal-LLM: Integrating Formal Language and Natural Language for Controllable LLM-based Agents
por: Li, Zelong, et al.
Publicado: (2024)

Compositional Automata Embeddings for Goal-Conditioned Reinforcement Learning
por: Yalcinkaya, Beyazit, et al.
Publicado: (2024)

Provably Correct Automata Embeddings for Optimal Automata-Conditioned Reinforcement Learning
por: Yalcinkaya, Beyazit, et al.
Publicado: (2025)

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

Expressive Reward Synthesis with the Runtime Monitoring Language
por: Donnelly, Daniel, et al.
Publicado: (2025)

The Lottery LLM Hypothesis, Rethinking What Abilities Should LLM Compression Preserve?
por: Tang, Zhenheng, et al.
Publicado: (2025)

Exploring Major Transitions in the Evolution of Biological Cognition With Artificial Neural Networks
por: Voudouris, Konstantinos, et al.
Publicado: (2025)

Automata Extraction from Transformers
por: Zhang, Yihao, et al.
Publicado: (2024)

FormalAlign: Automated Alignment Evaluation for Autoformalization
por: Lu, Jianqiao, et al.
Publicado: (2024)

Tractable Offline Learning of Regular Decision Processes
por: Deb, Ahana, et al.
Publicado: (2024)

Learning Formal Specifications from Membership and Preference Queries
por: Shah, Ameesh, et al.
Publicado: (2023)

Scalable Anytime Algorithms for Learning Fragments of Linear Temporal Logic
por: Raha, Ritam, et al.
Publicado: (2021)

The Role of Logic and Automata in Understanding Transformers
por: Lin, Anthony W., et al.
Publicado: (2025)

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

From Formal Language Theory to Statistical Learning: Finite Observability of Subregular Languages
por: Hayashi, Katsuhiko, et al.
Publicado: (2025)

MLRegTest: A Benchmark for the Machine Learning of Regular Languages
por: van der Poel, Sam, et al.
Publicado: (2023)

Unraveling Syntax: How Language Models Learn Context-Free Grammars
por: Schulz, Laura Ying, et al.
Publicado: (2025)

Robust Probabilistic Model Checking with Continuous Reward Domains
por: Ji, Xiaotong, et al.
Publicado: (2025)

Lost in Transmission: When and Why LLMs Fail to Reason Globally
por: Schnabel, Tobias, et al.
Publicado: (2025)

Neural Networks as Universal Finite-State Machines: A Constructive Deterministic Finite Automaton Theory
por: Dhayalkar, Sahil Rajesh
Publicado: (2025)

Hilbert: Recursively Building Formal Proofs with Informal Reasoning
por: Varambally, Sumanth, et al.
Publicado: (2025)

Extracting Robust Register Automata from Neural Networks over Data Sequences
por: Hong, Chih-Duo, et al.
Publicado: (2025)

MinMax Recurrent Neural Cascades
por: Ronca, Alessandro
Publicado: (2026)

Probabilistic Regular Tree Priors for Scientific Symbolic Reasoning
por: Schneider, Tim, et al.
Publicado: (2023)

Analyzing constrained LLM through PDFA-learning
por: Carrasco, Matías, et al.
Publicado: (2024)

The Sparse Tsetlin Machine: Sparse Representation with Active Literals
por: Østby, Sebastian, et al.
Publicado: (2024)

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

MUSTARD: Mastering Uniform Synthesis of Theorem and Proof Data
por: Huang, Yinya, et al.
Publicado: (2024)

Automata-Conditioned Cooperative Multi-Agent Reinforcement Learning
por: Yalcinkaya, Beyazit, et al.
Publicado: (2025)

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

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

Sampling from Your Language Model One Byte at a Time
por: Hayase, Jonathan, et al.
Publicado: (2025)

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

SELP: Generating Safe and Efficient Task Plans for Robot Agents with Large Language Models
por: Wu, Yi, et al.
Publicado: (2024)

Infinite Time Turing Machines and their Applications
por: Weerawarana, Rukmal, et al.
Publicado: (2025)

Bifocal Attention: Harmonizing Geometric and Spectral Positional Embeddings for Algorithmic Generalization
por: Awadhiya, Kanishk
Publicado: (2026)

Lemur: Integrating Large Language Models in Automated Program Verification
por: Wu, Haoze, et al.
Publicado: (2023)