Computational complexity and constraint logic programming languages
Computational complexity and constraint logic programming languages
复制标题
计算复杂性和约束逻辑编程语言
DOI：
--
复制
发表时间：
1990
影响因子：
1.2
通讯作者：
C. Tretkoff
中科院分区：
文献类型：
--
作者：
J. Cox;K. McAloon;C. Tretkoff
我们给出了一个复杂性分析的各种语言的频谱的CLP计划。通过改变逻辑和存储器管理，可以测量约束的作用和逻辑的作用。分析阐明了线性/整数规划与约束逻辑规划之间的关系。我们还确定了如何权力的约束可以很容易地导致不可判定查询的Datasheet语言的约束。这项工作的动机在很大程度上是由CLP语言的有效实施和随之而来的需要低级别的约束语言的问题。
We give a complexity analysis of a variety of languages across the spectrum of the CLP scheme. By varying the logic and memory management, the role of the constraints and the role of the logic can be measured. The analysis clarifies the relation between linear/integer programming and constraint logic programming. We also determine how the power of constraints can easily lead to undecidable queries in Datalog languages with constraints. This work is motivated in large part by the problems of efficient implementation of CLP languages and the concomitant need for low level constraint languages.