Skip to content

Characterizing Language Generation in the Limit: Finite Witnesses and a Separation-Width Hierarchy

Sep 2026 · 1 citation · ⚡ 1 influential · 18 references
Computer Science

TL;DR

This work describes language generation in the limit for arbitrary families over a countable universe and describes the characterization and full width hierarchy, including the simplified normalization and a direct diagonal capture lemma.

Abstract

Language generation in the limit asks for valid unseen elements from every exhaustive positive presentation of an unknown infinite language. We characterize this task for arbitrary families over a countable universe. Generation is possible exactly when each target can be assigned a finite positive witness so that the targets activated by any finite sample have an infinite common intersection. The necessary direction follows from a universal normalization: a search through unconfirmed histories converts any successful generator into one depending only on the observed set. We then ask how large compatible witnesses must be. Positive separation width records the smallest uniform size bound, with two further levels for unbounded finite witnesses and the absence of any compatible finite-witness assignment. Every level occurs. Countable families admit singleton witnesses, explicit families realize every finite width, and a union of two families with infinite common cores requires unbounded finite witnesses. Finally, countable-support and finite-profile obstructions explain why local combinatorial data cannot determine generation in the limit. The characterization and full width hierarchy are checked in Lean, including the simplified normalization and a direct diagonal capture lemma. The accompanying Lean development is maintained at https://github.com/xiaoyulics/language-generation-characterization

View source

Similar papers

Preprint Oct 2026

Two-Variable Logic with Arbitrarily Many Successor Relations

We study two-variable first-order logic with a finite, input-dependent number of distinguished successor relations and arbitrary additional unary and binary predicates. Each distinguished relation must be the exact immediate-successor relation of some linear order on the common domain; the orders themselves are not ava...

Jakub Michaliszyn, P. Witkowski · 1 citation
Preprint Oct 2026

Proving at Scale for Universal Algebra

We introduce SemiBase, a project that computes and formally certifies finite identity bases for small semigroups. Deciding finite basability is undecidable for finite algebras and remains open for finite semigroups. The task requires a proof that a candidate basis is complete, or a proof that none exists, rather than a...

João Araújo, Jan Hůla, Mikoláš Janota et al. · 0 citations
#edge computing Preprint Sep 2026

Automatic constraints with few subpowers and graphoid recognition

For graphoid automata, these results give polynomial-time recognition without a graph-width restriction, effective boundary composition, and comparison of finite graph relations, and the quadratic boundary bounds are optimal in the worst case.

Antonios Kalampakas · 0 citations
Preprint Oct 2026

Step Recursion: Exact Membership Spectra, Mixed Strides, and Collapse

For a strictly increasing $G:\mathbb{N}\to\mathbb{N}$ with $G(0)\geq 1$, we study minimal-basis function algebras generated by recursion along generalized inverses of its iterates. Bounded recursion requires an earlier pointwise majorant; unbounded recursion has no such requirement. If the orbit $G^{[t]}(0)$ has no pol...

K. Osipov · 0 citations
Preprint Oct 2026

A direct proof of Infinity in NF-0

We give a direct proof of Infinity in the no-empty version of New Foundations, denoted NF-0, by establishing that every model of the specified theory contains an object that is not finite in a precise, internally defined sense. The version considered has extensionality, at least two distinct objects, no empty objects,...

Zuhair Al-Johar · 0 citations
Preprint Sep 2026

Exact Local Optimality Does Not Compose: The Complexity of Chronological Realization

We study a controlled, normalized multi-menu positive-realization problem. A normalized realization reproduces declared root--word responses using common row-stochastic transition matrices and a single terminal effect. We compare three realization complexities: independent local realizations, a static shared carrier wi...

Yi-Xin Zhao · 1 citation

Related blog posts

MIT News · Artificial Intelligence Nov 17, 2026

Learning the language of machine learning

By studying the computational foundations of language learning, Associate Professor Jacob Andreas builds intelligent systems that can communicate effectively with humans.

Microsoft Research Blog Nov 16, 2026

TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient

AI coding agents are increasingly help developers fix bugs and build features largely on their own, but every interaction with their models consumes tokens. In each session, an agent sends instructions, tool descriptions, and session history to its model. Most efforts to reduce this cost focus on individual tasks. Yet developers return to the same […] The post TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient appeared first on Microsoft Research.

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.