한계 내에서의 공간 효율적인 언어 생성

우리는 공간 효율성(space efficiency)이라는 최소한의 제약 조건 하에서, extit{한계 내에서의 언어 생성 (language generation in the limit)}에 관한 자원 인식 이론을 개시합니다. 우리의 프레임워크에서 학습자는 대상 언어 $K$로부터 적대적인 양의 스트림(positive stream)을 관찰하며, $K$의 문자열을 최대 $\Delta$개까지만 누락하면서 최종적으로 환각이 없는(hallucination-free) 가설 언어 $L \subseteq K$를 출력해야 합니다. 우리는 메모리 제한이 있는 학습자를 위한 자연스러운 가설 클래스로서, 크기가 $k$인 알파벳에 대해 최대 $s$개의 상태를 가진 DFA(Deterministic Finite Automata)에 의해 인식되는 언어들의 집합인 $\mathcal{C}_{s,k}$에 초점을 맞춥니다. 지수 공간 영역(exponential-space regime)에서, 우리는 학습자가 대상 $K$를 정확하게 식별할 수 있음을 증명합니다. 더 엄격한 메모리 예산 하에서는, 가능한 가장 강력한 생성 보장(generation guarantees)을 규명합니다. 특히, 우리는 $\mathrm{poly}(s,k)$ 공간을 사용하여 생성 간극(generation gap) $\Delta = O(k^{2s-2})$를 갖는 가설로 수렴하는 스트리밍 알고리즘을 제시합니다. 또한, 학습된 가설은 길이가 $2s-1$ 이상인 $K$의 모든 문자열을 포착합니다. 우리는 표준 통신 복잡도(communication complexity) 문제로부터의 환원을 통해 이 결과에 근접한 하한(lower bound)을 제시하여 이를 보완합니다. 구체적으로, 생성 간극 $\Delta \le k^{(1-\varepsilon)s}$를 달성하려면 $k^{\Omega(\varepsilon s)}$의 메모리가 필요합니다. 이러한 결과들을 종합하면, 다항 공간 생성(polynomial-space generation)과 지수 공간 정확 식별(exponential-space exact identification) 사이의 급격한 전이(sharp transition)가 드러납니다.