INDUCTIVE LEARNING OF DESISION TREES OVER REGULAR PATTERNS AND REGULAR FORMAL SYSTEMS

本研究的目的是建立初等形式系统（efs，简称）的归纳可学习性的基本理论，允许从正例中删除替换。我们得到了以下结果：1。由一个基本子句和一个归纳子句组成的所谓原始形式系统（PFS）所定义的语言被证明是无限多个规则模式语言的联合。得到了减小PFS的一个充分必要条件。此外，我们还证明了它是有效可判定的。简化后的PFSs定义的语言的包含问题可以简化为原始PFSs中出现的规则模式的语法包含问题。我们证明了存在一个由PFS定义的每种语言的有限提示集。此外，我们还证明了由pfs定义的语言类具有所谓的m有限厚度的性质。由所谓的简单形式系统（简称SFSs）和规则形式系统（简称rfs）定义的语言类，它们是比pfs更一般的EFSs，最多有k个公理，在不允许擦除替换的情况下是可学习的（Shinohara 95）。在本研究中，我们证明了在允许擦除替换的情况下，上述类是不可学习的。虽然pfs是只有两个公理的rfs，但我们在pfs上引入了其他语法条件，并表明它们是可以从正例中学习的。我们将6中提到的结果应用于由SH系统生成的语言的学习问题。SH系统是表达重组行为或DNA序列剪接操作的简化模型。SH系统生成的语言是一种具有一些特殊属性的规则语言。在本研究中，我们用rfs用空替换来表示SH语言，并通过6.8得到的结果表明它们是可从正例中学习的。规则模式上的决策树所定义的语言表现为规则模式语言和协规则模式语言的有限多个联合和交集。在本研究中，我们证明了规则模式语言的有限多个联合或交集的语言类具有所谓的有限弹性，并证明了该类是可学习的。共同规则模式语言的问题仍然存在。少

The purpose of this research is to construct fundamental theory of inductive learnability of Elementary Formal Systems(EFSs, for short) allowing erasing substitutions from positive examples. We have obtained the following results :1.The language defined by the so-called Primitive Formal System(PFS, for short), which consists of a base clause and an induction clause, was shown to be expressed as a union of infinitely many regular pattern languages.2.We obtained a necessary and sufficient condition for a PFS to be reduced. Moreover, we showed that it is efficiently decidable.3.The inclusion problem of languages defined by reduced PFSs can he reduced to the syntactical inclusion problem of regular patterns appearing in the original PFSs.4.We showed that there exists a finite tell-tale set of each language defined by a PFS. Moreover, we showed that the language class defined by PFSs have the property of the so-called M-finite thickness.5.The class of languages defined by the so-called simp … More le formal systems(SFSs, for short) and regular formal systems(RFSs, for short), which are more general EFSs than PFSs, with at most k axioms is shown to be learnable in case erasing substitutions are not allowed (Shinohara 95). In this research, we showed that the above class is not learnable in case erasing substitutions are allowed.6.Although PFSs are RFSs with just two axioms, we introduced other syntactical conditions on PFSs and showed that they are learnable from positive examples.7.We applied the results as mentioned at 6 to the learning problem of languages generated by SH systems. An SH system is a simplified model for expressing a recombinant behavior or a splicing operation for a DNA sequence. The language generated by an SH system is a regular language with some special properties. In this research, we expressed SH languages by RFSs with empty substitutions and showed that they are learnable from positive examples by using results obtained at 6.8.The languages defined by decision trees over regular patterns were shown to be expressed as finitely many unions and intersections of regular pattern languages and co-regular pattern languages. In this research, we showed that the language class of finitely many unions or intersections of regular pattern languages has the so-called finite elasticity and showed that the class is learnable. The problem for co-regular pattern languages is still open. Less