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

本研究的目的是建立基本形式系统的归纳可学习性的基础理论，允许从正例中删除替换。我们得到了以下结果：1.由基子句和归纳子句组成的原始形式系统（简称PFS）所定义的语言可以表示为无穷多个正则模式语言的并集; 2.我们得到了PFS可约化的一个充要条件. 3.由约化PFS定义的语言的包含问题可以归结为原PFS中出现的正则模式的句法包含问题。4.我们证明了由PFS定义的每种语言都存在一个有限的tell-tale集。此外，我们还证明了由PFS定义的语言类具有所谓的M-有限厚的性质。 ...更多信息 le形式系统（SFSs，简称）和规则形式系统（RFSs，简称），这是更一般的EFSs比PFSs，最多有k个公理被证明是可学习的情况下擦除替代是不允许的（Shinohara 95）。在这项研究中，我们证明了上述类是不可学习的情况下，擦除替换是允许的。6.虽然PFSs是RFSs只有两个公理，我们介绍了其他的句法条件PFSs，并表明他们是可学习的，从积极的例子。7.我们应用的结果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