The computational power and complexity of constraint handling rules
The computational power and complexity of constraint handling rules
复制标题
约束处理规则的计算能力和复杂性
DOI：
10.1145/1462166.1462169
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Bart Demoen
中科院分区：
文献类型：
--
作者：
Jon Sneyers;Tom Schrijvers;Bart Demoen
约束处理规则 (CHR) 是一种基于规则的高级编程语言，越来越多地用于通用编程。我们介绍了 CHR 机，这是一种基于 CHR 操作语义的计算模型。其计算能力和时间复杂度属性与众所周知的图灵机和随机存取存储器机器进行了比较。这使我们能够证明一个有趣的结果，即每个算法都可以在 CHR 中以已知的时间和空间复杂度来实现。我们还研究了该结果的实际相关性以及所涉及的恒定因素。最后，我们将讨论范围扩大到其他（声明性）编程语言。
Constraint Handling Rules (CHR) is a high-level rule-based programming language which is increasingly used for general-purpose programming. We introduce the CHR machine, a model of computation based on the operational semantics of CHR. Its computational power and time complexity properties are compared to those of the well-understood Turing machine and Random Access Memory machine. This allows us to prove the interesting result that every algorithm can be implemented in CHR with the best known time and space complexity. We also investigate the practical relevance of this result and the constant factors involved. Finally we expand the scope of the discussion to other (declarative) programming languages.