Title: | Horn逻辑程序和形式文法之间的对应关系 |
Author: | 陈文彬
|
Issued Date: | 2003
|
Major: | 基础数学
|
Degree Grantor: | 中国科学院软件研究所
|
Place of Degree Grantor: | 中国科学院软件研究所
|
Degree Level: | 博士
|
Keyword: | 文法
; 逻辑程序
; 最小Herbrand模型
|
Alternative Title: | The Correspondence between the Horn Logic Programs and Grammars
|
Abstract: | 这篇论文从文法的角度研究了Horn逻辑程序.因为Horn逻辑程序的计算能力与图灵机是等价的,而图灵机的计算能力与。型文法是等价的,所以,Horn逻辑程序可以与。型文法相互对应起来,可以根据文法的分类方法将Horn逻辑程序进行分类.本论文的研究目的是探索Horn逻辑程序怎样与。型文法对应起来及与。型文法的子类相对应的Horn逻辑程序有什么特征,以刻划出Horn逻辑程序的层次结构.在本论文中,得到了如下的研究结果:找到了用O型文法产生Horn逻辑程序的最小Herbrand模型的方法,找到了用Horn逻辑程序模拟。型文法的方法,描述了与递归文法,1型文法,2型文法,3型文法等价的Horn逻辑程序的特征. |
English Abstract: | In this paper, Horn logic programs with grammatical view is considered. Because the computability of Horn logic programs is equivalent to that of Turing machines and the latter are equivalent to that of type-0 grammars, Horn logic programs are equivalent to type-0 grammars. This paper is to aim at exploring how Horn logic programs are equivalent to type-0 grammars and what is the characterics of Horn logic programs that are semantically equivalent to subclasses of type-0 grammars. In this paper, the results of research are as follows: The method to find type-0 grammars generating the least Herbrand models of Horn logic program is given. The method to find Horn logic programs generating the languages of type-0 grammars is given. The characterics of Horn logic programs that are semantically equivalent to recursive grammars, type-1 grammars, type-2 grammars, and type-3 grammars are given. |
Language: | 中文
|
Content Type: | 学位论文
|
URI: | http://ir.iscas.ac.cn/handle/311060/6574
|
Appears in Collections: | 中科院软件所
|
File Name/ File Size |
Content Type |
Version |
Access |
License |
|
LW011243.pdf(1661KB) | -- | -- | 限制开放 | -- | 联系获取全文 |
|
Recommended Citation: |
陈文彬. Horn逻辑程序和形式文法之间的对应关系[D]. 中国科学院软件研究所. 中国科学院软件研究所. 2003-01-01.
|
|
|