
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.

Properties of Language Classes with Finite Elasticity
Takashi MORIYAMA Masako SATO
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E78D
No.5
pp.532538 Publication Date: 1995/05/25
Online ISSN:
DOI:
Print ISSN: 09168532 Type of Manuscript: Special Section PAPER (Special Issue on Algorithmic Learning Theory) Category: Computational Learning Theory Keyword: inductive inference, positive data, finite elasticity, elementary formal system,
Full Text: PDF(590.3KB)>>
Summary:
This paper considers properties of language classes with finite elasticity in the viewpoint of set theoretic operations. Finite elasticity was introduced by Wright as a sufficient condition for language classes to be inferable from positive data, and as a property preserved by (not usual) union operation to generate a class of unions of languages. We show that the family of language classes with finite elasticity is closed under not only union but also various operations for language classes such as intersection, concatenation and so on, except complement operation. As a framework defining languages, we introduce restricted elementary formal systems (EFS's for short), called max lengthbounded by which any contextsensitive language is definable. We define various operations for EFS's corresponding to usual language operations and also for EFS classes, and investigate closure properties of the family G_{e} of max lengthbounded EFS classes that define classes of languages with finite elasticity. Furthermore, we present theorems characterizing a max lengthbounded EFS class in the family G_{e}, and that for the language class to be inferable from positive data, provided the class is closed under subset operation. From the former, it follows that for any n, a language class definable by max lengthbounded EFS's with at most n axioms has finite elasticity. This means that G_{e} is sufficiently large.

