Inductive Inferability for Formal Languages from Positive Data

Masako SATO  Kazutaka UMAYAHARA  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E75-D   No.4   pp.415-419
Publication Date: 1992/07/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Issue on Algorithmic Learning Theory)
Category: 
Keyword: 
inductive inference,  positive data,  formal language,  

Full Text: PDF(416KB)
>>Buy this Article


Summary: 
In this paper, we deal with inductive inference of an indexed family of recursive languages. We give two sufficient conditions for inductive inferability of an indexed family from positive data, each of which does not depend on the indexing of the family. We introduce two notions of finite cross property for a class of languages and a pair of finite tell-tales for a language. The former is a generalization of finite elasticity due to Wright and the latter consists of two finite sets of strings one of which is a finite tell-tale introduced by Angluin. The main theorem in this paper is that if any language of a class has a pair of finite tell-tales, then the class is inferable from positive data. Also, it is shown that any language of a class with finite cross property has a pair of finite tell-tales. Hence a class with finite cross property is inferable from positive data. Further-more, it is proved that a language has a finite tell-tale if and only if there does not exist any infinite cross sequence of languages contained in the language.