A poly(s,k)-space streaming algorithm achieves generation gap O(k^{2s-2}) for DFA languages with s states over k symbols and captures all strings of length at least 2s-1, with a near-matching lower bound via communication complexity.
Pareto-optimal non-uniform language generation
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
years
2026 3verdicts
UNVERDICTED 3representative citing papers
Memoryless generation succeeds for any countable collection of infinite languages under an enumeration restriction, with optimal minimax densities for finite collections via Sperner's theorem; sliding windows add no worst-case benefit while adaptive storage does, and approximate identification works
Defines mistake-bounded generation and gives an algorithm for finite classes achieving optimal last-mistake time Cdim(L) with floor(log2 |L|) mistakes, plus a trade-off for infinite classes and noisy extensions.
citing papers explorer
-
Space-Efficient Language Generation in the Limit
A poly(s,k)-space streaming algorithm achieves generation gap O(k^{2s-2}) for DFA languages with s states over k symbols and captures all strings of length at least 2s-1, with a near-matching lower bound via communication complexity.
-
On Language Generation in the Limit with Bounded Memory
Memoryless generation succeeds for any countable collection of infinite languages under an enumeration restriction, with optimal minimax densities for finite collections via Sperner's theorem; sliding windows add no worst-case benefit while adaptive storage does, and approximate identification works
-
Mistake-Bounded Language Generation
Defines mistake-bounded generation and gives an algorithm for finite classes achieving optimal last-mistake time Cdim(L) with floor(log2 |L|) mistakes, plus a trade-off for infinite classes and noisy extensions.