Inductive Inferability for Formal Languages from Positive Data

Masako SATO; Kazutaka UMAYAHARA

Inductive Inferability for Formal Languages from Positive Data

Masako SATO, Kazutaka UMAYAHARA

Full Text Views

0

Cite this

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.

Publication: IEICE TRANSACTIONS on Information Vol.E75-D No.4 pp.415-419

Publication Date: 1992/07/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Issue on Algorithmic Learning Theory)

Category

Cite this

Copy

Masako SATO, Kazutaka UMAYAHARA, "Inductive Inferability for Formal Languages from Positive Data" in IEICE TRANSACTIONS on Information, vol. E75-D, no. 4, pp. 415-419, July 1992, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/e75-d_4_415/_p

Copy

@ARTICLE{e75-d_4_415,
author={Masako SATO, Kazutaka UMAYAHARA, },
journal={IEICE TRANSACTIONS on Information},
title={Inductive Inferability for Formal Languages from Positive Data},
year={1992},
volume={E75-D},
number={4},
pages={415-419},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={July},}

Copy

TY - JOUR
TI - Inductive Inferability for Formal Languages from Positive Data
T2 - IEICE TRANSACTIONS on Information
SP - 415
EP - 419
AU - Masako SATO
AU - Kazutaka UMAYAHARA
PY - 1992
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E75-D
IS - 4
JA - IEICE TRANSACTIONS on Information
Y1 - July 1992
AB - 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.
ER -