首页> 中文学位 >逻辑程序的相容性与环公式研究
【6h】

逻辑程序的相容性与环公式研究

代理获取

目录

文摘

英文文摘

论文说明:List of Tables, List of Figures

声明

序言

Chapter 1Introduction

1.1 Motivations

1.2 Problems

1.3 Results

Chapter 2 Normal Logic Programming

2.1 Syntax

2.2 Semantics

2.2.1 Least model

2.2.2 Stable model

2.2.3 Well-founded model

2.3 Computation

2.3.1 Complexity

2.3.2 Smodels

2.3.3 ASSAT

2.4 Syntactic extensions

2.4.1 Constraints and classical negation

2.4.2 Disjunctions

2.4.3 Nested expressions

2.5 Applications

2.5.1 Planning

2.5.2 CSP

2.5.3 Combinational graph problems

2.5.4 Timetabling

Chapter 3 Weakly Auto-compatible Logic Programs

3.1 Motivations

3.2 Weakly auto-compatibility

3.2.1 Properties

3.2.2 Algorithms

3.2.3 Reasoning complexities

3.3 Comparison

3.3.1 FC-normality

3.3.2 Call-consistency and order-consistency

3.3.3 WF-irreducible

3.4 Concluding remarks

Chapter 4 First-order Loop Formulas

4.1 Motivations

4.2 Preliminaries

4.3 First-order loops and loop formulas

4.4 Some properties

4.5 Concluding remarks

Chapter 5 Conclusion and Future Work

5.1 Conclusion

5.2 Further work

Acknowledgements

Bibliography

Appendix

在学期间在省级以上刊物发表的论文目录及参加的科研项目及获奖情况

展开▼

摘要

一个逻辑程序可能有一个回答集、多个回答集或者根本就没有回答集。我们提出了一类逻辑程序一弱自相容逻辑程序。它们保证具有回答集而且有多项式时间算法可以计算其中一个回答集。另外,我们还获得了如下结果: (1)利用弱自相容逻辑程序中的相容性概念和A算子,获得了逻辑程序协调性质的一个充要条件。 (2)两个有趣的弱自相容逻辑程序的本质特征,即强半单调性和任意良序下的前向链构造均生成一个回答集。 (3)弱自相容逻辑程序的轻信推理(credulous reasoning)和怀疑推理(skepticalreasoning)的复杂性分别是NP-完全和co-NP-完全的。前向链正规逻辑程序的轻信推理和怀疑推理的复杂性也分别是NP-完全的和co-NP-完全的。判定一个逻辑程序是否是弱自相容的是co-NP-完全的。 (4)弱自相容逻辑程序不同于命名协调的逻辑程序,他们互不包含。即使在限制逻辑程序必须是良基不可归约(WF-irreducible)的情形也是如此。前向链正规逻辑程序与命名协调逻辑程序也是不可比的。 (5)另外,我们还发现,(a)对任何前向链正规的逻辑程序P,总存在一个最小的P上的一致性性质使得P是关于它前向链正规。(b)命名协调逻辑程序和Lifschitz的序协调(order-consistent)逻辑程序是等价的:而且它们有多项式时间算法来检查一个逻辑程序是否是命名协调(序协调)的。 逻辑程序的环和环公式思想开辟了求解其回答集的新方法。我们将这一思想从命题情形推广到一阶的环和环公式,并得到了如下结果: (1)一个逻辑程序的一阶环公式和其Clark完备化(也是一阶的)一起精确地刻画了原来逻辑程序的回答集。 (2)如果固定逻辑程序中出现的谓词符号的最大元(arity)数,则判定一个逻辑程序是否有有穷的完备环集是多项式时间可判定的。

著录项

相似文献

  • 中文文献
  • 外文文献
  • 专利
代理获取

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号