Properties of Language Classes with Finite Elasticity

Takashi MORIYAMA  Masako SATO  

IEICE TRANSACTIONS on Information and Systems   Vol.E78-D   No.5   pp.532-538
Publication Date: 1995/05/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Issue on Algorithmic Learning Theory)
Category: Computational Learning Theory
inductive inference,  positive data,  finite elasticity,  elementary formal system,  

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

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 length-bounded by which any context-sensitive 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 Ge of max length-bounded EFS classes that define classes of languages with finite elasticity. Furthermore, we present theorems characterizing a max length-bounded EFS class in the family Ge, 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 length-bounded EFS's with at most n axioms has finite elasticity. This means that Ge is sufficiently large.