Theory & Algorithms · Computer Science & AI
Formal Languages & Automata
The newest papers in Formal Languages & Automata that ReadSearch has read, newest first. Each links to its own page, with its authors, date, where it was published and the original.
30 papers, from 5 September 2026 to 4 November 2026: 30 arXiv preprints.
Get the few papers worth your time in Formal Languages & Automata every morning.
Follow Formal Languages & Automata and ReadSearch reads its new papers each day, then brings you the few worth reading, each with its key finding in a sentence.
Newest papers
An Engineering Reading of the Bounded Halting Problem and Observable Properties of a Universal Machine
The halting problem asks whether a program eventually halts, with unrestricted resources.The Scope Grammar of Natural-Language Rules: Counting and Enumerating Readings modulo Logical Equivalence
A rule written for people fixes its atomic conditions and connectives but leaves open how the connectives are bracketed, and each bracketing is a different logical reading that an autoformalizer…Private Uniform Language Generation
We study uniform language generation under approximate differential privacy.Maximal input entropy for binary two-deletion and two-insertion channels
Under uniform transmission, we determine the received binary words that maximize input entropy for two-deletion and two-insertion channels.Learning Erasing Equal-Length Relational Pattern Languages in the Limit from Positive Data over Binary Alphabets
Relational pattern languages generalize Angluin's pattern languages by requiring the strings substituted for repeated occurrences of a variable to stand in a given relation, rather than to be…Relational Composition as Parallel Transport: What Per-Entity Frames Force in Attention
A dot product means something only when both vectors share a coordinate system.SPECOLA: A Tool for Specification Driven Robot Evaluation
Simulation benchmarks are a useful way to measure progress in robotics; typically they provide success rate as the dominant measure of performance.Reward Objectives for Robust (PO)MDPs: A Law-Preserving Equivalence with (Partially Observable) Games
Robust partially observable Markov decision processes model agents that act under partial observability while adversarial environment resolves uncertainty in the transition probabilities.Runtime Semantic Discovery for Evolving Action Alphabets
Runtime Verification typically assumes a fixed alphabet of observable actions.On the Complexity of Level-Synchronized Tree Automata for Quantum Circuit Verification
Reliable quantum computation requires methods for verifying quantum circuits.At the Limits of Computability: Steps Towards Autonomous AI Discovery on the Busy Beaver Frontier
Recent breakthroughs in AI for mathematics---ranging from Olympiad medal performances to resolving long-standing open conjectures---have rapidly expanded what automated systems can achieve.Jumbled Simon's Equivalence and Embeddings
\emph{Jumbled scattered factors} are a generalisation of scattered factors (or subsequences) where a jumbled scattered factor is obtained from another word by deleting and rearranging letters.Limit-sure Winning in Team Games without Shared Randomness
We study concurrent stochastic games in which a team of agents plays against an adversarial environment.Type-Checking for Pattern-Based Tree Transformations
We introduce and study pattern-based tree transformations.Smallest String Attractors and Minimal Coverage Certificates of Thue--Morse Words
String attractors provide a compact way of representing the complete factor structure of a word: a set of positions is an attractor if every distinct factor has at least one occurrence crossing one…From Transformers to Weighted Automata: Towards the Verification of Large Language Models
Large language models (LLMs) are increasingly deployed in safety-critical settings, yet their black-box nature makes it difficult to provide formal guaranties about their behavior.Small universal multiset reaction systems
This paper presents a construction of a small universal machine within the framework of Multi-set Reaction Systems.Provably Tractable NFA-Constrained Language Generation via HMMs
Constrained generation aims to sample from language models (LMs) conditioned on hard constraints.Learning Shuffle Ideals with Membership Queries and Contrastive Examples
This paper studies learning of shuffle ideals with membership queries as well as with contrastive queries---a form of membership query that reveals not only whether a selected word $w$ is in the…Constraints Are Graphs, Not Chains: Exact Decoding for Diffusion Language Models
Diffusion language models (dLLMs) predict masked positions in arbitrary order, but their exact constrained decoders still encode constraints as sequential languages, whose state must track every…