符合CHR的逻辑算法：一个约束的元复杂性结果 用规则优先级处理规则

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

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

立即领取

感谢您参与论坛问题回答

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

+2 论坛币

摘要翻译：
本文研究了Ganzinger和McAllester的逻辑算法语言(LA)与约束处理规则(CHR)之间的关系。给出了一个具有规则优先级的LA到CHR-rp：CHR的翻译模式，并证明了LA的元复杂性定理可以通过逆翻译应用于CHR-rp的子集。受Ganzinger和McAllester的逻辑算法高级实现方案的启发，在一种新的调度算法的基础上，我们提出了一种CHR-rp的替代实现方案，该方案给出了很强的复杂性保证，并给出了一个新的精确的CHR-rp元复杂性定理。进一步证明了逻辑算法到CHR-rp的转换与新的CHR-rp实现相结合，满足了逻辑算法元复杂度结果所需的复杂度。
---
英文标题：
《Logical Algorithms meets CHR: A meta-complexity result for Constraint
  Handling Rules with rule priorities》
---
作者：
Leslie De Koninck
---
最新提交年份：
2009
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Programming Languages        程序设计语言
分类描述：Covers programming language semantics, language features, programming approaches (such as object-oriented programming, functional programming, logic programming). Also includes material on compilers oriented towards programming languages; other material on compilers may be more appropriate in Architecture (AR). Roughly includes material in ACM Subject Classes D.1 and D.3.
涵盖程序设计语言语义，语言特性，程序设计方法（如面向对象程序设计，函数式程序设计，逻辑程序设计）。还包括面向编程语言的编译器的材料；关于编译器的其他材料可能在体系结构(AR)中更合适。大致包括ACM主题课程D.1和D.3中的材料。
--
一级分类：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中的材料。
--
一级分类：Computer Science        计算机科学
二级分类：Computational Complexity        计算复杂度
分类描述：Covers models of computation, complexity classes, structural complexity, complexity tradeoffs, upper and lower bounds. Roughly includes material in ACM Subject Classes F.1 (computation by abstract devices), F.2.3 (tradeoffs among complexity measures), and F.4.3 (formal languages), although some material in formal languages may be more appropriate for Logic in Computer Science. Some material in F.2.1 and F.2.2, may also be appropriate here, but is more likely to have Data Structures and Algorithms as the primary subject area.
涵盖计算模型，复杂度类别，结构复杂度，复杂度折衷，上限和下限。大致包括ACM学科类F.1（抽象设备的计算）、F.2.3（复杂性度量之间的权衡）和F.4.3（形式语言）中的材料，尽管形式语言中的一些材料可能更适合于计算机科学中的逻辑。在F.2.1和F.2.2中的一些材料可能也适用于这里，但更有可能以数据结构和算法作为主要主题领域。
--

---
英文摘要：
  This paper investigates the relationship between the Logical Algorithms language (LA) of Ganzinger and McAllester and Constraint Handling Rules (CHR). We present a translation schema from LA to CHR-rp: CHR with rule priorities, and show that the meta-complexity theorem for LA can be applied to a subset of CHR-rp via inverse translation. Inspired by the high-level implementation proposal for Logical Algorithm by Ganzinger and McAllester and based on a new scheduling algorithm, we propose an alternative implementation for CHR-rp that gives strong complexity guarantees and results in a new and accurate meta-complexity theorem for CHR-rp. It is furthermore shown that the translation from Logical Algorithms to CHR-rp combined with the new CHR-rp implementation, satisfies the required complexity for the Logical Algorithms meta-complexity result to hold.
---
PDF链接：
https://arxiv.org/pdf/0901.1230

扫码加我 拉你入群

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

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

分享0 收藏0 回帖

关键词：复杂性 优先级 CHR Intelligence relationship implementation 给出 translation 规则