优先化缺省逻辑的复杂性

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

摘要翻译：
在缺省推理中，通常并不是所有解决缺省规则之间冲突的可能方法都是可以接受的。表示解决冲突的可接受方式的准则可以硬连线在推理机制中，例如继承推理中的特定性可以这样处理，或者它们可以抽象地作为默认规则的排序给出。在本文中，我们研究了Reiter的缺省逻辑中后一种方法的形式化。我们的目标是从计算复杂度的角度来分析和比较这三种形式化的计算特性：Baader和Hollunder以及Brewka的优先化缺省逻辑，以及基于词典比较的优先化缺省逻辑。该分析将这些逻辑的命题变体定位在多项式层次的第二和第三层次上，并为受限制的优先化缺省理论类别确定了可处理和难处理推理之间的界限。
---
英文标题：
《Complexity of Prioritized Default Logics》
---
作者：
J. Rintanen
---
最新提交年份：
2011
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Artificial Intelligence        人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--

---
英文摘要：
  In default reasoning, usually not all possible ways of resolving conflicts between default rules are acceptable. Criteria expressing acceptable ways of resolving the conflicts may be hardwired in the inference mechanism, for example specificity in inheritance reasoning can be handled this way, or they may be given abstractly as an ordering on the default rules. In this article we investigate formalizations of the latter approach in Reiter's default logic. Our goal is to analyze and compare the computational properties of three such formalizations in terms of their computational complexity: the prioritized default logics of Baader and Hollunder, and Brewka, and a prioritized default logic that is based on lexicographic comparison. The analysis locates the propositional variants of these logics on the second and third levels of the polynomial hierarchy, and identifies the boundary between tractable and intractable inference for restricted classes of prioritized default theories.
---
PDF链接：
https://arxiv.org/pdf/1105.5453

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：复杂性 Presentation Intelligence Computation Presentatio may 复杂度 reasoning 冲突 ways