我们在此开启了一种资源感知的极限语言生成理论，重点关注空间效率这一最小约束条件。在我们的框架中，学习者观察来自目标语言 $K$ 的对抗性正向流，并最终必须输出一个无幻觉的假设语言 $L \neq K$，同时最多省略 $\triangle$ 个 $K$ 的字符串。我们专注于 $\text{C}_{s,k}$，即被状态数最多为 $s$ 的确定性有限自动机（DFA）识别的语言集合，作为内存受限学习者的自然假设类。
在指数空间范围内，我们证明学习者可以准确识别目标语言 $K$。在更严格的内存预算下，我们对最强的生成保证进行了描述。特别地，我们提出了一种使用 $\text{poly}(s,k)$ 空间的流式算法，该算法收敛到生成差距为 $\triangle = O(k^{2s-2})$ 的假设。此外，学习到的假设捕获了每个长度至少为 $2s-1$ 的 $K$ 中的字符串。我们通过从标准通信复杂性问题的归约补充了这一结果，具体而言，实现生成差距 $\triangle \leq k^{(1-\text{ε})s}$ 需要 $k^{\text{Ω(εs)}}$ 的内存。这些结果共同揭示了多项式空间生成与指数空间精确识别之间的明显转变。
博主点评：该研究为语言生成提供了新的视角，尤其在内存受限的情况下，展现了学习者如何在资源紧张的环境下有效识别目标语言。它不仅为理论计算机科学提供了新的理论依据，也为实际应用中的算法设计提供了启示。