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

Formal correctness of a quadratic unification algorithm

JOURNAL OF AUTOMATED REASONING 2006年第1-2期37卷 67-92页

作者： Ruiz-Reina, Jose-Luis Martin-Mateos, Francisco-Jesus Alonso, Jose-Antonio Hidalgo, Maria-Jose Univ Seville ETSI Informat Dept Comp Sci & Artificial Intelligence Computat Log Grp Seville Spain

We present a case study using ACL2 to verify a nontrivial algorithm that uses efficient data structures. The algorithm receives as input two first-order terms, and it returns a most general unifier of these terms if they are unifiable, failure otherwise. The verified implementation stores terms as directed acyclic graphs by means of a pointer structure. Its time complexity is O(n(2)) and its space complexity O(n), and it can be executed in ACL2 at a speed comparable to a similar C implementation. We report the main issues encountered to achieve this formally verified implementation.

关键词： ACL2 unification algorithm verification

来源：评论

学校读者我要写书评

暂无评论

Formal correctness of a quadratic unification algorithm

Formal correctness of a quadratic unification algorithm

引用

20th Workshop on Empirically Successful Classical Automated Reasoning

关键词： ACL2 unification algorithm verification

来源：评论

学校读者我要写书评

暂无评论

unification algorithms for eliminating and introducing quantifiers in natural deduction automated theorem proving

引用

JOURNAL OF AUTOMATED REASONING 1997年第1期18卷 105-134页

作者： Dafa, L TSING HUA UNIV DEPT APPL MATHBEIJING 100084PEOPLES R CHINA

A natural deduction system was adapted from Gentzen system. It enables valid wffs to be deduced in a very 'natural' way. One need not transform a formula into other normal forms. Robinson's unification algorithm is used to handle clausal formulas. algorithms for eliminating and introducing quantifiers without Skolemization are presented, and unification theorems for them are proved. A natural deduction automated theorem prover based on the algorithms was implemented. The rules for quantifiers are controlled by the algorithms. The Andrews challenge and the halting problem were proved by the system.

关键词： automated theorem proving Gentzen system natural deduction unification algorithm

来源：评论

学校读者我要写书评

暂无评论

Substad: for fast substitution in LISP, with an application on unification

引用

Information Processing Letters 1978年第1期7卷 58-62页

作者： de Champeaux, Dennis Bedrijfsinformatica University of Amsterdam Mirror Co Netherlands

来源：评论

学校读者我要写书评

暂无评论

Unifying nominal unification

Unifying nominal unification

引用

24th International Conference on Rewriting Techniques and Applications, RTA 2013

作者： Calvès, Christophe Université de Lorraine LORIA UMR 7503 Vandœuvre-lès-NancyF-54500 France CNRS LORIA UMR 7503 Vandœuvre-lès-NancyF-54500 France Inria Villers-lès-NancyF-54600 France

ISBN: (纸本)9783939897538

Nominal unification is proven to be quadratic in time and space. It was so by two different approaches, both inspired by the Paterson-Wegman linear unification algorithm, but dramatically different in the way nominal and first-order constraints are dealt with. To handle nominal constraints, Levy and Villaret introduced the notion of replacing while Calvès and Fernández use permutations and sets of atoms. To deal with structural constraints, the former use multi-equations in a way similar to the Martelli-Montanari algorithm while the later mimic Paterson-Wegman. In this paper we abstract over these two approaches and genralize them into the notion of modality, highlighting the general ideas behind nominal unification. We show that replacings and environments are in fact isomorphic. This isomorphism is of prime importance to prove intricate properties on both sides and a step further to the real complexity of nominal unification. © Christophe Calvès.

关键词： unification nominal a-equivalence term-graph rewriting Nominal unification algorithm Modality second approximation

来源：评论

学校读者我要写书评

暂无评论

ON THE OCCUR-CHECK-FREE PROLOG PROGRAMS

引用

ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS 1994年第3期16卷 687-726页

作者： APT, KR PELLEGRINI, A UNIV AMSTERDAM FAC MATH & COMP SCI1018 TV AMSTERDAMNETHERLANDS UNIV PADUA DIPARTIMENTO MATEMAT PURA APPLI-35131 PADUAITALY

In most PROLOG implementations, for efficiency occur-check is omitted from the unification algorithm. This paper provides natural syntactic conditions that allow the occur-check to be safely omitted. The established results apply to most well-known PROLOG programs, including those that use difference lists, and seem to explain why this omission does not lead in practice to any complications. When applying these results to general programs, we show their usefulness for proving absence of floundering. Finally, we propose a program transformation that transforms every program into a program for which only the calls to the built-in unification predicate need to be resolved by a unification algorithm with the occur-check.

关键词： LANGUAGES MODED PROGRAMS OCCUR-CHECK PROBLEM PROLOG PROGRAMS unification algorithm

来源：评论

学校读者我要写书评

暂无评论

Mit :: Lcs :: Tr :: Mit-Lcs-Tr-344

引用

2016年

Mit :: Lcs :: Tr :: Mit-Lcs-Tr-344 by published by

关键词： algorithm complete set confined regular equational equational theories equational unification function symbols induction hypothesis lemma mit-lcs-tr-344 set substitution symbols term rewriting theories unification unification algorithm unification algorithms unification problem variable variables

来源：评论

学校读者我要写书评

暂无评论

Automatic synthesis of recursive programs: the proof-planning paradigm 97

Automatic synthesis of recursive programs: the proof-plannin...

引用

Proceedings of the 12th international conference on Automated software engineering (formerly: KBSE)

作者： A. Armando A. Smaill I. Green

ISBN: (纸本)9780818679612

We describe a proof plan that characterises a family of proofs corresponding to the synthesis of recursive functional programs. This plan provides a significant degree of automation in the construction of recursive programs from specifications, together with correctness proofs. This plan makes use of meta-variables to allow successive refinement of the identity of unknowns, and so allows the program and the proof to be developed hand in hand. We illustrate the plan with parts of a substantial example-the synthesis of a unification algorithm.

关键词： functional programming automatic synthesis unification algorithm recursive programs recursive functional programs proof-planning paradigm correctness proofs

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：