:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Yang, Andy, Cadilhac, Michaël, Chiang, David
Format:	Preprint
Published:	2025
Subjects:	Computation and Language Formal Languages and Automata Theory
Online Access:	https://arxiv.org/abs/2506.16055
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

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

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

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

Simulating Hard Attention Using Soft Attention
by: Yang, Andy, et al.
Published: (2024)

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

Transformers in Uniform TC$^0$
by: Chiang, David
Published: (2024)

Length Generalization Bounds for Transformers
by: Yang, Andy, et al.
Published: (2026)

Population Protocols over Ordered Agents
by: Blondin, Michael, et al.
Published: (2026)

A Hierarchy of Nondeterminism
by: Radi, Bader Abu, et al.
Published: (2022)

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

A Diamond Structure in the Transducer Hierarchy
by: Kaufmann, Noah
Published: (2021)

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

Transformers as Transducers
by: Strobl, Lena, et al.
Published: (2024)

What Formal Languages Can Transformers Express? A Survey
by: Strobl, Lena, et al.
Published: (2023)

Data Structures for Finite Downsets of Natural Vectors: Theory and Practice
by: Cadilhac, Michaël, et al.
Published: (2025)

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

A Forward Simulation-Based Hierarchy of Linearizable Concurrent Objects
by: Wang, Chao, et al.
Published: (2026)

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

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

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

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

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

Autoformalization in the Wild: Assessing LLMs on Real-World Mathematical Definitions
by: Zhang, Lan, 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)

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

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

Cluster automata
by: Kornai, András
Published: (2025)

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

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

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

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

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

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

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

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

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)