Learning Elementary Formal Systems
Learning Elementary Formal Systems
复制标题
学习基本形式系统
DOI：
10.1016/0304-3975(92)90068-q
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
Akihiro Yamamoto
中科院分区：
文献类型：
--
作者：
S. Arikawa;T. Shinohara;Akihiro Yamamoto
Smullyan为发展其递归函数理论而发明的初等形式系统（Elementary Formal Systems，简称EFS）被证明适合于生成语言。本文首先指出EFS也可以作为一种逻辑程序设计语言，并且EFS的归结过程可以用来接受语言。本文从逻辑程序语义的角度为EFS提供了理论基础。因此，Shapiro的模型推理理论可以很自然地应用于我们的EFS语言学习。我们介绍了EFS的一些子类，它们对应于Chomsky层次结构和其他重要的语言类。我们讨论两项之间的统一符的计算。然后我们给出了这些子类的包含加细算子的归纳推理算法，并证明了它们的完备性。
The elementary formal systems (EFS for short) Smullyan invented to develop his recursive function theory, are proved suitable togeneratelanguages. In this paper we first point out that EFS can also work as a logic programming language, and the resolution procedure for EFS can be used toacceptlanguages. We give a theoretical foundation to EFS from the viewpoint of semantics of logic programs. Hence, Shapiro's theory of model inference can naturally be applied to our language learning by EFS. We introduce some subclasses of EFS's with correspond to Chomsky hierarchy and other important classes of languages. We discuss computations of unifiers between two terms. Then we give inductive inference algorithms including refinement operators for these subclasses and show their completeness.