检索结果-内蒙古大学图书馆

Implementing Constructive Intensional Negation

NEW GENERATION COMPUTING 2008年第1期27卷 25-56页

作者： Marino, Julio Jose Moreno-Navarro, Juan Munoz-Hernandez, Susana Univ Politecn Madrid Babel Grp Boadilla Del Monte 28660 Spain

Although negation is an active area of research in logic programming, sound and complete implementations are still absent from actual Prolog systems. One of the most promising techniques in the literature is intensional negation (IN), which follows a transformational approach: for each predicate p in a program its negative counterpart intneg(p) is generated. However, implementations of IN have not been included in Prolog environments due, in part, to the lack of details and explicit techniques, such as the treatment of universally quantified goals. In this paper, we describe a variant of IN, which we have called constructive intensional negation (CIN). Unlike earlier proposals, CIN does not resort to a dedicated resolution strategy when dealing with universally quantified formulae, which has been instrumental in having an effective implementation. Therefore, pure SLD resolution is used, what enables the reuse of existing Prolog implementation technology. Among the contributions of this work we can mention not only a full implementation being tested for its integration in the Ciao Prolog system but also some formal results ensuring soundness and completeness with their associated proofs.

关键词： Negation Intensional Negation constraint logic programming Program Transformation logic programming Implementation Constructive Negation

来源：评论

学校读者我要写书评

暂无评论

A Decision Procedure for a Theory of Finite Sets with Finite Integer Intervals

引用

ACM TRANSACTIONS ON COMPUTATIONAL logic 2024年第1期25卷 1-34页

作者： Cristia, Maximiliano Rossi, Gianfranco Univ Nacl Rosario Fac Ciencias Exactas Ingn & Agrimensura Pellegrini 250 RA-2000 Rosario Santa Fe Argentina CIFASIS Fac Ciencias Exactas Ingn & Agrimensura Pellegrini 250 RA-2000 Rosario Santa Fe Argentina Univ Parma Dipartimento Sci Matemat Fis & Informat Parco Area Sci53-A I-43124 Parma Italy

In this paper we extend a decision procedure for the Boolean algebra of finite sets with cardinality constraints (L-vertical bar center dot vertical bar) to a decision procedure for L-vertical bar center dot vertical bar extended with set terms denoting finite integer intervals (L-[]). In L-[] interval limits can be integer linear terms including unbounded variables. These intervals are a useful extension because they allow to express non-trivial set operators such as the minimum and maximum of a set, still in a quantifier-free logic. Hence, by providing a decision procedure for L-[] it is possible to automatically reason about a new class of quantifier-free formulas. The decision procedure is implemented as part of the {log} ('setlog') tool. The paper includes a case study based on the elevator algorithm showing that {log} can automatically discharge all its invariance lemmas, some of which involve intervals.

关键词： {log} set theory integer intervals decision procedure constraint logic programming

来源：评论

学校读者我要写书评

暂无评论

Design and implementation of a tracer driver: Easy and efficient dynamic analyses of constraint logic programs

引用

THEORY AND PRACTICE OF logic programming 2008年第5-6期8卷 581-609页

作者： Langevine, Ludovic Ducasse, Mireille Mission Crit IT B-1420 Braine Lalleud Belgium INSA Rennes IRISA F-35042 Rennes France

Tracers provide users with useful information about program executions. In this article, we propose a "tracer driver". From a single tracer, it provides a powerful front-end enabling multiple dynamic analysis tools to be easily implemented, while limiting the overhead of the trace generation. The relevant execution events are specified by flexible event patterns and a large variety of trace data can be given either systematically or "on demand". The proposed tracer driver has been designed in the context of constraint logic programming (CLP);experiments have been made within GNU-Prolog. Execution views provided by existing tools have been easily emulated with a negligible overhead. Experimental measures show that the flexibility and power of the described architecture lead to good performance. The tracer driver overhead is inversely proportional to the average time between two traced events. Whereas the principles of the tracer driver are independent of the traced programming language, it is best suited for high-level languages, such as CLP, where each traced execution event encompasses numerous low-level execution steps. Furthermore, CLP is especially hard to debug. The current environments do not provide all the useful dynamic analysis tools. They can significantly benefit froth our tracer driver which enables dynamic analyses to be integrated at a very low cost.

关键词： Software engineering Debugging Execution trace analysis Execution monitoring Execution tracing Execution visualization programming environment constraint logic programming

来源：评论

学校读者我要写书评

暂无评论

Solving Horn Clauses on Inductive Data Types Without Induction

引用

THEORY AND PRACTICE OF logic programming 2018年第3-4期18卷 452-469页

作者： De Angelis, Emanuele Fioravanti, Fabio Pettorossi, Alberto Proietti, Maurizio G dAnnunzio Univ Chieti Pescara DEC Pescara Italy Univ Roma Tor Vergata DICII Rome Italy CNR IASI Rome Italy

We address the problem of verifying the satisfiability of Constrained Horn Clauses (CHCs) based on theories of inductively defined data structures, such as lists and trees. We propose a transformation technique whose objective is the removal of these data structures from CHCs, hence reducing their satisfiability to a satisfiability problem for CHCs on integers and booleans. We propose a transformation algorithm and identify a class of clauses where it always succeeds. We also consider an extension of that algorithm, which combines clause transformation with reasoning on integer constraints. Via an experimental evaluation we show that our technique greatly improves the effectiveness of applying the Z3 solver to CHCs. We also show that our verification technique based on CHC transformation followed by CHC solving, is competitive with respect to CHC solvers extended with induction.

关键词： Program verification constrained Horn clauses constraint logic programming inductively defined data types program transformation

来源：评论

学校读者我要写书评

暂无评论

Temporal phylogenetic networks and logic programming

引用

THEORY AND PRACTICE OF logic programming 2006年第0期6卷 539-558页

作者： Erdem, Esra Lifschitz, Vladimir Ringe, Don Vienna Univ Technol Inst Informat Syst 184 3 A-1040 Vienna Austria Univ Texas Dept Comp Sci Austin TX 78712 USA Univ Penn Dept Linguist Philadelphia PA 19104 USA

The concept of a temporal phylogenetic network is a mathematical model of evolution of a family of natural languages. It takes into account the fact that languages can trade their characteristics with each other when linguistic communities are in contact, and also that a contact is only possible when the languages are spoken at the same time. We show how computational methods of answer set programming and constraint logic programming can be used to generate plausible conjectures about contacts between prehistoric linguistic communities, and illustrate our approach by applying it to the evolutionary history of Indo-European languages.

关键词： phylogenetics historical linguistics Indo-European languages answer set programming constraint logic programming

来源：评论

学校读者我要写书评

暂无评论

A Practical Decision Procedure for Quantifier-Free, Decidable Languages Extended with Restricted Quantifiers

引用

JOURNAL OF AUTOMATED REASONING 2024年第4期68卷 23页

作者： Cristia, Maximiliano Rossi, Gianfranco Univ Nacl Rosario Rosario Argentina UNR CIFASIS CONICET Rosario Argentina Univ Parma Parma Italy

Let L(X )be the language of a first-order, decidable, quantifier-free theory X. Consider the language, L-RQ(X), that extends L-X with formulas of the form for all x is an element of A : phi (restricted universal quantifier, RUQ) and there exists x is an element of A : phi(restricted existential quantifier, REQ), where A is a finite set and phi is a formula made of X-formulas, RUQ and REQ. That is,L-RQ(X)admits nested restricted quantifiers. In this paper we present a decision procedure for some expressive fragments of L-RQ(X) and its implementation as part of the{log}('setlog') tool. The usefulness of the approach is shown by reporting on three real-world case studies.

关键词： Restricted quantifiers Set theory constraint logic programming {log}

来源：评论

学校读者我要写书评

暂无评论

Nicolog: A simple yet powerful cc(FD) language

引用

JOURNAL OF AUTOMATED REASONING 1996年第3期17卷 371-403页

作者： Sidebottom, G Havens, WS SIMON FRASER UNIV INTELLIGENT SYST LABCTR SYST SCIBURNABYBC V5A 1S6CANADA SIMON FRASER UNIV SCH COMP SCIBURNABYBC V5A 1S6CANADA

In this paper, we describe Nicolog, a language with capabilities similar to recently developed constraint logic programming (CLP) languages such as CLP(BNR), clp(FD), and cc(FD). Central to Nicolog are projection constraints (PCs), a sublanguage for compiling and optimizing constraint propagation in numeric and Boolean domains. PCs are an interesting generalization of the indexical constraints introduced in cc(FD) and also found in clp(FD). Nicolog compiles a very general class of built-in constraints into equivalent sets of PCs, allowing an arbitrary mixture of integer (easily extensible to real) and Boolean operations. Nicolog also lets the user program PCs directly, making it possible to implement new sophisticated propagation procedures. We show that PCs are a simple, efficient, and flexible way to implement most of the propagation procedures possible in other FD CLP systems. These include procedures for cardinality, constructive disjunction, implication, and mixed Boolean/numeric constraints. Empirical results with a simple prototype Nicolog implementation based on the WAM architecture show it can solve hard problems with speed comparable to the fastest existing CLP systems.

关键词： constraint logic programming projection constraints

来源：评论

学校读者我要写书评

暂无评论

Optimizing compilation of CLP(R)

引用

ACM TRANSACTIONS ON programming LANGUAGES AND SYSTEMS 1998年第6期20卷 1223-1250页

作者： Kelly, AD Marriott, K Macdonald, A Stuckey, PJ Yap, P Monash Univ Dept Comp Sci & Software Engn Clayton Vic 2168 Australia Univ Melbourne Dept Comp Sci Parkville Vic 3052 Australia Natl Univ Singapore Dept Informat Syst & Comp Sci Singapore 119260 Singapore

constraint logic programming (CLP) languages extend logic programming by allowing the use of constraints from different domains such as real numbers or Boolean functions. They have proved to be ideal for expressing problems that require interactive mathematical modeling and complex combinatorial optimization problems. However, CLP languages have mainly been considered as research systems, useful for rapid prototyping, but not really competitive with more conventional programming languages where efficiency is a more important consideration. One promising approach to improving the performance of CLP systems is the use of powerful program optimizations to reduce the cost of constraint solving. We extend work in this area by;describing a new optimizing compiler for the CLP language CLP(R). The compiler implements six powerful optimizations: reordering of constraints, bypass of the constraint solver, splitting and dead-code elimination, removal of redundant constraints, removal of redundant variables, and specialization of constraints which cannot fail. Each program optimization is designed to remove the overhead of constraint solving when possible and keep the number of constraints in the store as small as possible. We systematically evaluate the effectiveness of each optimization in isolation and in combination. Our empirical evaluation of the compiler verifies that optimizing compilation can be made efficient enough to allow compilation of real-world programs and that it is worth performing such compilation because it gives significant time and space performance improvements.

关键词： compilation constraint logic programming program analysis program optimization source-to-source program transformation

来源：评论

学校读者我要写书评

暂无评论

On the system of two all_different predicates

引用

INFORMATION PROCESSING LETTERS 2005年第3期94卷 99-105页

作者： Appa, G Magos, D Mourtos, I London Sch Econ London WC2A 2AE England Technol Educ Inst Athens Egaleo 12210 Greece Athens Univ Econ & Business Athens 10434 Greece

Numerous real-life problems require certain variables to be assigneddifferent values. This requirement is encapsulated in constraints of difference. If x_1, x_2 denotetwo problem variables, the (nonlinear) constraint of difference is x_1 ≠ x_2. Given that variablesx_1,..., x_n must all be pairwise different, a constraint of the type all_different(x_1,..., x_n)can be used to formulate in a compact manner the n(n - 1)/2 binary constraints of difference. Suchan n-ary constraint is also called a predicate because it imposes a logical condition on itsvariable set. constraint programming (CP) makes use of such elaborate predicates in order to providea natural modeling framework. Such models are solved by CP techniques designed to produce feasiblesolutions. Alternatively, Integer programming (IP) methods can be employed in cases where a logicpredicate can be represented by linear inequalities involving integer variables. Apparently, suchrepresentations are important not only because they enrich the arsenal of resolution techniques butalso because they motivate the integration of CP and IP in a unified modeling and algorithmicframework.

关键词： combinatorial problems all_different predicate constraint logic programming facet

来源：评论

学校读者我要写书评

暂无评论

A non-termination criterion for binary constraint logic programs

引用

THEORY AND PRACTICE OF logic programming 2009年第2期9卷 145-164页

作者： Payet, Etienne Mesnard, Fred Univ Reunion IREMIA LIM St Denis France

On the one hand, termination analysis of logic programs is now a fairly established research topic within the logic programming community. On the other hand, non-termination analysis seems to remain a much less attractive Subject. If we divide this line of research into two kinds of approaches, dynamic versus static analysis, this paper belongs to the latter. It proposes a criterion for detecting non-terminating atomic queries with respect to binary constraint logic programming (CLP) rules, which strictly generalizes our previous works on this subject. We give a generic operational definition and an implemented logical form of this criterion. Then we show that the logical form is correct and complete with respect to the operational definition.

关键词： constraints constraint logic programming non-termination

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：