Safe Language Generation in the Limit
read the original abstract
Recent results in learning a language in the limit have shown that, although language identification is impossible, language generation is tractable. As this foundational area expands, we need to consider the implications of language generation in real-world settings. This work offers the first theoretical treatment of safe language generation. Building on the computational paradigm of learning in the limit, we formalize the tasks of safe language identification and generation. We prove that under this model, safe language identification is impossible, and that safe language generation is at least as hard as (vanilla) language identification, which is also impossible. Last, we discuss several intractable and tractable cases.
This paper has not been read by Pith yet.
Forward citations
Cited by 3 Pith papers
-
Contrastive Identification and Generation in the Limit
Contrastive pair presentations yield exact identifiability characterizations via a geometric refinement of Angluin's condition, a new contrastive closure dimension for generation, mutual incomparability with text iden...
-
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 w...
-
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.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.