Rich Classes Inferable from Positive Data: Length-Bounded Elementary Formal Systems
Rich Classes Inferable from Positive Data: Length-Bounded Elementary Formal Systems
复制标题
从正数据推断出丰富的类：长度有限的基本形式系统
DOI：
10.1006/inco.1994.1006
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
T. Shinohara
中科院分区：
文献类型：
--
作者：
T. Shinohara
摘要利用初等形式系统的框架，从正数据中进行归纳推理是非常有效的。基本形式系统（Elementary Formal System，简称EFS）是一种基于BASIC+的逻辑程序，由许多公理组成。任何上下文敏感的语言都可以由一个受限的EFS定义，称为长度有界的EFS。长度有界EFSs与最多n公理被认为是，它表明，归纳推理的积极数据成功地为他们的模型，以及他们的语言。由此可以得出结论，任何一类逻辑程序，如Prolog程序，对应于长度有界的EFS可以推断出积极的事实。
Abstract Inductive inference from positive data is shown to be remarkably powerful using the framework of elementary formal systems. An elementary formal system, EFS for short, is a kind of logic program on Σ+ consisting of finitely many axioms. Any context-sensitive language is definable by a restricted EFS, called a length-bounded EFS. Length-bounded EFSs with at most n axioms are considered, and it is shown that inductive inference from positive data works successfully for their models as well as for their languages. From this it follows that any class of logic programs, such as Prolog programs, corresponding to length-bounded EFSs can be inferred from positive facts.