Properties of Language Classes with Finite Elasticity

スポンサーリンク

概要

• 論文の詳細を見る

• 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 pairs 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 G_e 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 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 length-bounded EFS's with at most TL axioms has finite elasticity. This means that G_e is sufficiently large.

• 社団法人電子情報通信学会の論文
• 1995-05-25

著者

• Sato M

  Real World Computing Partnership Tsukuba‐shi Jpn

• Moriyama Takashi

  3rd Systems Development Division Open Systems Engineering Department Nec Corporation

• Sato Masako

  College of Arts and Integrated Sciences, University of Osaka Prefecture

関連論文

• Properties of Language Classes with Finite Elasticity

スポンサーリンク