Note on a central lemma for learning theory
type: Item
instance of: scholarly article
title: Note on a central lemma for learning theory
zbMATH Open document ID: 0541.68062
DOI: 10.1016/0022-2496(83)90027-5
author: Daniel N. Osherson
author: Michael Stob
author: Scott Weinstein
published in: Journal of Mathematical Psychology
publication date: 1983-01-01T00:00:00Z
review text: The paper is a contribution to text identification in learning theory. It begins with the enunciation and proof of a classical result - the Blum and Blum Lemma about the existence of finite locking sequences for any learning function f and any language L which f identifies [\textit{L. Blum} and \textit{M. Blum}, Inf. Control 28, 125-155 (1975; Zbl 0375.02028)]. The importance of this Lemma and some of its applications are also presented. Then, the metric \(d(t,s)=\sum_{t_ n\neq s_ n}2^{-n}\) is introduced on \({}^ NN\) (the set of infinite sequences with elements from N), and \((^ NN,d)\) becomes a complete metric space. The Blum and Blum Lemma is reformulated and proved in this context. This result appears now as a consequence of rather general, topological considerations. The usefulness of this approach is then emphasized, by proving other interesting results about other learning paradigms.
Mathematics Subject Classification ID: 68T05
Mathematics Subject Classification ID: 03D60
Mathematics Subject Classification ID: 54E35
zbMATH DE Number: 3860429
zbMATH Keywords: text identification
zbMATH Keywords: learning theory
zbMATH Keywords: finite locking sequences
zbMATH Keywords: learning function
zbMATH Keywords: metric space
zbMATH Keywords: topological considerations
reviewed by: Cristian Masalagiu
MaRDI profile type: Publication
full work available at URL: 0022-2496(83)90027-5
OpenAlex ID: W2025659114
Wikidata QID: Q124879123
cites work: Toward a mathematical theory of inductive inference
cites work: Some decidability results on grammatical inference and complexity
cites work: Language identification in the limit
cites work: Q4189277
cites work: Q5573961
description: scientific article; zbMATH DE number 3860429