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

本研究的目的是构建基本形式系统的归纳可学习性的基本理论，允许从正例中删除替换。我们得到了以下结果：1.由基子句和归纳子句组成的所谓原始形式系统(PFS)所定义的语言被表示为无限多个正则模式语言的并。2.我们得到了PFS可约的一个充要条件。3.由约简PFS定义的语言的包含问题可以归结为原始PFS中出现的规则模式的句法包含问题。4.我们证明了由PFS定义的每种语言都存在一个有限的说明集。此外，我们还证明了由…定义的语言类具有所谓的M-有限稠密性质。5.由所谓的SIMP PSS定义的语言类更多的LE形式系统(简称SFSS)和正则形式系统(简称RFSS)被证明是在不允许擦除替换的情况下可学习的(Shinohara95)，它们比PFS更一般，具有至多k个公理。在本研究中，我们证明了在允许擦除替换的情况下，上述类是不可学习的。6.虽然PFS是只有两个公理的RFSS，但我们在PFS上引入了其他句法条件，并证明了它们可以从正例中学习。7.我们将文6中的结果应用于SH系统生成的语言的学习问题。SH系统是表达DNA序列的重组行为或剪接操作的简化模型。SH系统生成的语言是一种具有一些特殊性质的正则语言。在这项研究中，我们用带空代换的RSS来表示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