Space-Efficient Language Generation in the Limit

This paper investigates the computational limits of language acquisition when a learner is restricted to a finite memory budget. Specifically, it asks: what is the strongest possible generation guarantee a learner can achieve when observing only positive examples of a target regular language while operating within polynomial space?

The authors formalize a framework for "space-efficient generation in the limit." In this model, a learner receives a stream of positive examples from a target language $K$ (recognizable by a DFA with at most $s$ states) and must output a hypothesis language $L$ that is a subset of $K$. The goal is to minimize the "generation gap"—the number of strings in $K$ that the hypothesis $L$ fails to generate. The authors develop a streaming algorithm that uses a rank-iteration strategy to traverse the space of possible DFAs, employing a recursion technique inspired by Savitch’s theorem to maintain space efficiency. They also provide a lower bound for the generation gap by reducing the problem to the Index problem in communication complexity.

The study establishes a sharp phase transition in language generation. With exponential memory, a learner can exactly identify the target language. However, under a polynomial memory budget, the learner must incur an exponential generation gap. Specifically, the authors present an algorithm that achieves a generation gap of $O(k^{2s-2})$ using $\text{poly}(s, k)$ space. They further prove that any algorithm attempting to achieve a significantly smaller generation gap ($k^{(1-\varepsilon)s}$) requires $k^{\Omega(\varepsilon s)}$ memory, demonstrating that the gap is essentially optimal.