What Is the Search Space of the Regular Inference?
What Is the Search Space of the Regular Inference?
复制标题
正则推理的搜索空间是多少？
DOI：
--
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
E. Vidal
中科院分区：
文献类型：
--
作者：
P. Dupont;L. Miclet;E. Vidal
本文重新审视了常规推论的理论，特别是通过扩展了阳性样本的结构完整性的定义，并通过证明了两个基本定理。该框架使人们能够通过正面样本构建的布尔晶格搜索规则推理问题。研究了搜索空间的几个属性，并讨论了概括标准。在此框架中，引入了边界集合的概念，即不包括负样本的最通用解决方案的集合。最后，讨论了常规语言识别的复杂性。
This paper revisits the theory of regular inference, in particular by extending the definition of structural completeness of a positive sample and by demonstrating two basic theorems. This framework enables to state the regular inference problem as a search through a boolean lattice built from the positive sample. Several properties of the search space are studied and generalization criteria are discussed. In this framework, the concept of border set is introduced, that is the set of the most general solutions excluding a negative sample. Finally, the complexity of regular language identification from both a theoritical and a practical point of view is discussed.