2021/03/24 by Fernando C. Alves, Alves, Fernando C.
Computer Science · #Algorithms and Data Compression #Computability, Logic, AI Algorithms #Computation and Language (cs.CL) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.2103.13166
openalex publication_date 2021/03/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In his pioneering work in the field of Inductive Inference, Gold (1967)\nproved that a set containing all finite languages and at least one infinite\nlanguage over the same fixed alphabet is not learnable in the exact sense.\nWithin the same framework, Angluin (1980) provided a complete characterization\nfor the learnability of language families. Mathematically, the concept of exact\nlearning in that classical setting can be seen as the use of a particular type\nof metric for learning in the limit. In this short research note we use\nNiyogi's extended version of a theorem by Blum and Blum (1975) on the existence\nof locking data sets to prove a necessary condition for learnability in the\nlimit of any family of languages in any given metric. This recovers Gold's\ntheorem as a special case. Moreover, when the language family is further\nassumed to contain all finite languages, the same condition also becomes\nsufficient for learnability in the limit.\n