Knuth—Bendix过程的发散现象的研究

Ｋｎｕｔｈ－Ｂｅｎｄｉｘ完备过程不终止的起因研究得很少，本文研究引起不终止的重写规则的结构性质，提出了相容交叉规则对的概念，推广了文献６的结论，并提出了为构造系统检验该过程是否不终止的方法。     

重写系统中解决发散现象的扩充技术

本文介绍和提出用于解决发散问题的各种基于保守扩充技术的方法.我们特别地用实例证明了这几种新方法可以对带AC算子的重写系统进行归纳完备化.     

高效率重写型程序的设计

本文考虑如何设计高效率(即重写步数较少的)重写型程序。文中以计算Fibonacci数列的程序为例．比较具有相同功能的重写型程序,展示编写高效率重写型程序的可能性。介绍利用动态项重写计算编写高效率重写型程序的直观、简洁的方法。其中．动态项重写计算是项重写系统的元计算模型,其计算同样基于项重写。     

项重写系统的并行实现方案

项重写系统的并行归约可以提高归约的效率，在无共享内存的Ｔｒａｎｓｐｕｔｅｒ网络上实现时要考虑任务的分配，项的拼装，归约任务的控制等问题，其中怎么样减少机间的机内进程的通信慢提高系统效果的关键。本文从控制方式角度讨论在不同拓扑结构的Ｔｒａｎｓｐｕｔｅｒ网络上实现项重写系统的方案，重点介绍基于树形结构下的控制方法，进程安排和通讯形式。     

重写系统的模块分解

Ｍｉｄｄｅｌｄｏｒｐ和Ｔｏｙａｍａ证明，强加构造原则到项重写系统可获得完备概念的模块性，并且系统分解成的各部分间可共亨函数符号和重量写规则。本文推广他们的结论，当构造性的项重写系统引用定义在其它系统中的函数符号时，完备概念的模块性仍保持。该结论对代数规范和基于项重写的编程语言等方面是很有意义的。     

依赖项重写系统及其在程序设计语言中的应用

面重写系统是一种简洁通用的计算模型，在许多领域中有着重要的应用。     

项重写系统等价性的归纳证明

尽管学者们在计算机软件理论及相关数学理论方面做出了不懈的努力,但伴随着计算机硬件的高速发展而来的软件危机却日益严峻,其原因复杂多样。其中,主要原因之一是缺乏程序验证的方法和工具。程序设计的主要步骤有:描述问题、设计程序、实现程序及测试程序。需要注意的是,这里是测试程序的正确性而非证明程序的正确性,这样程序的正确性就不能从根     

项重写系统弱基终止性的归纳证明

1.引言项重写系统是一种受到广泛研究和应用的形式计算模型。一个项重写系统由一组称为重写规则的定向等式组成。例如,下面的R是一个由五个重写规则组成的、定义用({0,s})表示的自然数集N上的两倍函数d(x)=2×n:N→N的项重写系统:     

基于项重写系统的联锁系统模型检测方法研究

模型检测方法对安全苛求系统建模的完整性需要一套严谨的方法论与技术,对于验证系统的正确性,具有传统方法无法比拟的优势。提出利用项重写系统建立安全苛求系统模型与验证方法,采用基于项重写系统原理的Maude工具语言,对铁路联锁系统的站场进行形式化建模,通过其语法和语义定义各类约束和离散事件,构架联锁系统属性和行为。在模型建立的基础上,对联锁站场的静态属性和安全属性进行形式化模型验证。结果表明,基于项重写系统的模型检测方法可以较好地应用于实际联锁系统软件的开发,对开发安全苛求系统和模型检测方法的实际应用提供借鉴。     

TA4SP的认证性扩展

认证性是安全协议检测的重要特性之一,但TA4SP自动协议证明器无法对安全协议的认证性进行检测。针对该问题,提出一种TA4SP的认证性检测方法。该方法基于对TA4SP设计原理的分析,采用分层认证思想,实现对其认证性的理论扩展,其结构清晰、易于形式化。实例表明,通过该方法改进后的TA4SP能有效检测安全协议的认证性。     

Chain properties of rule closures

This article introduces a generalisation of the crossed rule approach to the detection of Knuth-Bendix completion procedure divergence. It introduces closure chains, which are special rule closures constructed by means of particular substitution operations and operators, as a suitable formalism for progress in this direction. Supporting substitution algebra is developed first, followed by considerations concerning rule closures in general, concluding with an investigation of closure chain properties. Issues concerning the narrowing process are not discussed here.     

About the rewriting systems produced by the Knuth-Bendix completion algorithm

We show that in a free F-algebra endowed with a strict order we can associate with a complete rewriting system in the sense of Knuth-Bendix an equivalent proper (minimal) complete system. Furthermore, if the complete system is compatible with a strict order, then the equivalent proper complete system is unique.     

Structures for Abstract Rewriting

When rewriting is used to generate convergent and complete rewrite systems in order to answer the validity problem for some theories, all the rewriting theories rely on a same set of notions, properties, and methods. Rewriting techniques have been used mainly to answer the validity problem of equational theories, that is, to compute congruences. Recently, however, they have been extended in order to be applied to other algebraic structures such as preorders and orders. In this paper, we investigate an abstract form of rewriting, by following the paradigm of logical-system independency. To achieve this purpose, we provide a few simple conditions (or axioms) under which rewriting (and then the set of classical properties and methods) can be modeled, understood, studied, proven, and generalized. This enables us to extend rewriting techniques to other algebraic structures than congruences and preorders such as congruences closed under monotonicity and modus ponens. We introduce convergent rewrite systems that enable one to describe deduction procedures for their corresponding theory, and we propose a Knuth-Bendix–style completion procedure in this abstract framework.     

通用远程过程调用的设计与实现

在分布式计算系统中，远程过程调用ＲＰＣ是种流行的进程间通信机制。ＲＰＣ简单灵活，且功能较强。上前大多数ＲＰＣ机制是同步的，严重地影响了分布式应用的并行性。我们设计和实现了一个通用的ＲＰＣ。本文讨论了设计的要点和方法，并对通用ＲＰＣ的实现作了介绍。     

Paramodulation with Well-founded Orderings

For many years, all existing completeness results for Knuth–Bendixcompletion and ordered paramodulation required the term ordering to be well-founded, monotonic and total(izable) on ground terms.Then, it was shown that well-foundedness and the subterm propertywere enough for ensuring completeness of ordered paramodulation.Here we show that the subterm property is not necessary either.By using a new restricted form of rewriting, we obtain a completenessproof of ordered paramodulation for Horn clauses with equality,where well-foundedness of the ordering suffices. Apart fromthe theoretical significance of this result, some potentialapplications motivating the interest of dropping the subtermproperty are given. The proof of the results included in thisarticle, being still technical in some parts, is pretty muchshorter and easier to read than the one we have in the preliminaryversion of this work presented at the CADE, 2002 conference(Bofill, and Rubio, 2002, CADE, Vol. 2392 of LNAI, pp. 456–470).     

The undecidability of self-embedding for term rewriting systems

The self-embedding property of term rewriting systems is closely related to the uniform termination property, since a nonself-embedding term rewriting system is uniform terminating. The self-embedding property is shown to be undecidable and partially decidable. It follows that the nonself-embedding property is not partially decidable. This is true even for globally finite term rewriting systems. The same construction gives an easy alternate proof that uniform termination is undecidable in general and also for globally finite term rewriting systems. Also, the looping property is shown to be undecidable in the same way.     

Head Boundedness of Nonterminating Rewritings

Further research about nonterminating rewritings is introduced.First,the previous definition of head boundedness is modified to exclude non-fair reduction sequences.A sufficient condition is then given to determine head boundedness of term rewriting systems.The condition is then developed to a method to determine head boundedness of constructor systems.     

有关远程过程调用的几个重要问题的讨论

远程过程调用作为构造分布式系统的一个重要工具已经得到了广泛的应用,本文详细讨论了有关ＲＰＣ的七个重要问题：网络传输协议、类型一致性、错误处理、孤儿问题、效率问题、性能问题、互操作性。