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

On Correctness and completeness of an n Queens program

THEORY AND PRACTICE OF LOGIC programMING 2022年第1期22卷 37-50页

作者： Drabent, Wlodzimierz Polish Acad Sci Inst Comp Sci Ul Jana Kazimierza 5 PL-01248 Warsaw Poland Linkoping Univ Dept Comp & Informat Sci S-58183 Linkoping Sweden

Thom Fruhwirth presented a short, elegant, and efficient Prolog program for the n queens problem. However, the program may be seen as rather tricky and one may not be convinced about its correctness. This paper explains the program in a declarative way and provides proofs of its correctness and completeness. The specification and the proofs are declarative, that is they abstract from any operational semantics. The specification is approximate, it is unnecessary to describe the program's semantics exactly. Despite the program works on non-ground terms, this work employs the standard semantics, based on logical consequence and Herbrand interpretations. Another purpose of the paper is to present an example of precise declarative reasoning about the semantics of a logic program.

关键词： logic programming declarative programming program completeness program correctness specification nonground answers

来源：评论

学校读者我要写书评

暂无评论

Proving completeness of logic programs with the cut

引用

FORMAL ASPECTS OF COMPUTING 2017年第1期29卷 155-172页

作者： Drabent, Wodzimierz Polish Acad Sci Inst Comp Sci Warsaw Poland Linkoping Univ Linkoping Sweden

completeness of a logic program means that the program produces all the answers required by its specification. The cut is an important construct of programming language Prolog. It prunes part of the search space, this may result in a loss of completeness. This paper proposes a way of proving completeness of programs with the cut. The semantics of the cut is formalized by describing how SLD-trees are pruned. A sufficient condition for completeness is presented, proved sound, and illustrated by examples.

关键词： Logic programming The cut Operational semantics program completeness program correctness

来源：评论

学校读者我要写书评

暂无评论

The Prolog Debugger and Declarative programming 29th

The Prolog Debugger and Declarative Programming

引用

29th International Conference on Logic-Based program Synthesis and Transformation (LOPSTR)

作者： Drabent, Wlodzimierz Polish Acad Sci Inst Comp Sci Warsaw Poland Linkoping Univ IDA Linkoping Sweden

ISBN: (纸本)9783030452599;9783030452605

Logic programming is a declarative programming paradigm. programming language Prolog makes logic programming possible, at least to a substantial extent. However the Prolog debugger works solely in terms of the operational semantics. So it is incompatible with declarative programming. This report discusses this issue and tries to find how the debugger may be used from the declarative point of view. The results are rather not encouraging. Also, the box model of Byrd, used by the debugger, is explained in terms of SLD-resolution.

关键词： Declarative diagnosis/Algorithmic debugging Prolog Declarative programming program correctness program completeness

来源：评论

学校读者我要写书评

暂无评论

On completeness of Logic programs 24th

On Completeness of Logic Programs

引用

24th International Symposium on Logic-Based program Synthesis and Transformation (LOPSTR)

作者： Drabent, Wlodzimierz Polish Acad Sci Inst Comp Sci PL-00901 Warsaw Poland Linkoping Univ IDA Linkoping Sweden

ISBN: (纸本)9783319178226;9783319178219

program correctness (in imperative and functional programming) splits in logic programming into correctness and completeness. completeness means that a program produces all the answers required by its specification. Little work has been devoted to reasoning about completeness. This paper presents a few sufficient conditions for completeness of definite programs. We also study preserving completeness under some cases of pruning of SLD-trees (e.g. due to using the cut). We treat logic programming as a declarative paradigm, abstracting from any operational semantics as far as possible. We argue that the proposed methods are simple enough to be applied, possibly at an informal level, in practical Prolog programming. We point out importance of approximate specifications.

关键词： Logic programming program completeness Declarative programming Approximate specification

来源：评论

学校读者我要写书评

暂无评论

On Feasibility of Declarative Diagnosis 39

On Feasibility of Declarative Diagnosis

引用

39th International Conference on Logic programming (ICLP)

作者： Drabent, Wlodzimierz Polish Acad Sci Inst Comp Sci Warsaw Poland

The programming language Prolog makes declarative programming possible, at least to a substantial extent. programs may be written and reasoned about in terms of their declarative semantics. All the advantages of declarative programming are however lost when it comes to program debugging. This is because the Prolog debugger is based solely on the operational semantics. Declarative methods of diagnosis (i.e. locating errors in programs) exist, but are neglected. This paper discusses their possibly main weaknesses and shows how to overcome them. We argue that useful ways of declarative diagnosis of logic programs exist, and should be usable in actual programming.

关键词： declarative diagnosis / algorithmic debugging Prolog coroutining program correctness program completeness

来源：评论

学校读者我要写书评

暂无评论

S-Semantics-an Example 1

引用

31st International Symposium on Logic-Based program Synthesis and Transformation (LOPSTR)

作者： Drabent, Wlodzimierz Polish Acad Sci Inst Comp Sci Ul Jana Kazimierza 5 PL-01248 Warsaw Poland Linkoping Univ Dept Comp & Informat Sci S-58183 Linkoping Sweden

ISBN: (数字)9783030988692

ISBN: (纸本)9783030988692;9783030988685

The s-semantics makes it possible to explicitly deal with variables in program answers. So it seems suitable for programs using nonground data structures, like open lists. However it is difficult to find published examples of using the s-semantics to reason about particular programs. Here we apply s-semantics to prove correctness and completeness of Fruhwirth's n queens program. This is compared with a proof, published elsewhere, based on the standard semantics and Herbrand interpretations.

关键词： Logic programming s-semantics program correctness program completeness Declarative programming Specification

来源：评论

学校读者我要写书评

暂无评论

Correctness and completeness of Logic programs

引用

ACM TRANSACTIONS ON COMPUTATIONAL LOGIC 2016年第3期17卷 18-18页

作者： Drabent, Wlodzimierz Polish Acad Sci Inst Comp Sci Ul Jana Kazimierza 5 PL-01248 Warsaw Poland Linkoping Univ S-58183 Linkoping Sweden

We discuss proving correctness and completeness of definite clause logic programs. We propose a method for proving completeness, while for proving correctness we employ a method that should be well known but is often neglected. Also, we show how to prove completeness and correctness in the presence of SLD-tree pruning, and point out that approximate specifications simplify specifications and proofs. We compare the proof methods to declarative diagnosis (algorithmic debugging), showing that approximate specifications eliminate a major drawback of the latter. We argue that our proof methods reflect natural declarative thinking about programs, and that they can be used, formally or informally, in everyday programming.

关键词： Logic programming declarative programming program completeness program correctness specifications declarative diagnosis/algorithmic debugging

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：