Generación de lenguaje eficiente en espacio en el límite
Este estudio inicia una teoría consciente de los recursos de la generación de lenguaje en el límite bajo restricciones de eficiencia espacial. Un aprendiz observa un flujo adversario positivo de un lenguaje objetivo K y debe producir una hipótesis libre de alucinaciones L mientras omite como máximo Δ cadenas. La investigación se centra en DFAs con s estados sobre un alfabeto de tamaño k como la clase de hipótesis para aprendices con memoria limitada. En el régimen de espacio exponencial, los autores demuestran que un aprendiz puede identificar exactamente el lenguaje objetivo K. Bajo presupuestos de memoria más estrictos, presentan un algoritmo en streaming que usa espacio poly(s,k) y converge a una hipótesis con una brecha de generación de Δ= O(k^{2s-2}). Esta hipótesis aprendida captura cada cadena en K de longitud al menos 2s-1. Los resultados se complementan con un límite inferior casi coincidente derivado de la complejidad de comunicación, mostrando que lograr Δ≤ k^{(1-ε)s} requiere memoria k^{Ω(εs)}. Estos hallazgos revelan una transición aguda entre la generación en espacio polinomial y la identificación exacta en espacio exponencial.