
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Inductive Inferability for Formal Languages from Positive Data
Masako SATO Kazutaka UMAYAHARA
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E75D
No.4
pp.415419 Publication Date: 1992/07/25
Online ISSN:
DOI:
Print ISSN: 09168532 Type of Manuscript: Special Section PAPER (Special Issue on Algorithmic Learning Theory) Category: Keyword: inductive inference, positive data, formal language,
Full Text: PDF(416KB)>>
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 telltales 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 telltale introduced by Angluin. The main theorem in this paper is that if any language of a class has a pair of finite telltales, 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 telltales. Hence a class with finite cross property is inferable from positive data. Furthermore, it is proved that a language has a finite telltale if and only if there does not exist any infinite cross sequence of languages contained in the language.

