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

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

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

This paper proposes a novel method for proving weakly ground termination in a restricted domain of a term rewriting system based on structural and cover set induction. For this prupose,we introduce the concepts of base set and set of ground terms defined recursively over base sets,which plays a crucial role in the inductive method. The method can be used for non-terminating,non-confluent and/or non-linear term rewriting systems,and have application in inductive equivalence testing and program verification.

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

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

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

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

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

项重写系统是一种简洁通用的计算模型，在许多领域中有着重要的应用．但是，在一些应用中，它不能很好地解决问题，为此，文中提出了一种新的项重写计算模型——依赖项重写系统，并给出了它在程序设计语言中的应用．直观上说，依赖项重写系统是重写规则之间存在着关于函数符号的依赖关系的项重写系统．这一模型具有较好的性质（例如，合流性、终止性等）和很强的表达能力．应用它，能够解决某些计算不终止问题，并有利于并行性的开发．

基于项重写的动态可重构系统建模与仿真框架

可重构系统建模与仿真是一项复杂的任务.本文从可重构计算模式的基本特征出发,建立计算与通讯并重的生产者-消费者系统架构,并提取其数据、计算、通讯基本元素,解决运行时的调度和加载问题,形成基于项重写理论的动态可重构计算系统建模框架.最后指出基于本框架进行系统规范描述、系统设计和仿真验证的方法与步骤.并以实例说明了不同的调度策略产生满足不同规范的应用系统,显示了本框架的通用性.

重写系统的模块分解

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

基于DTRC的形式自动证明平台及其应用

动态项重写计算(DTRC)是项重写系统(TRS)的元计算模型,具有层次化结构和动态重写等特征,可应用于归纳定理的形式自动证明以及项重写系统弱终止性的形式自动证明等方面.文中介绍了一个基于DTRC的形式自动证明平台及其在TRS弱终止性自动证明上的应用.

TA4SP的认证性扩展

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

基于Lakatos证伪方法论的机器发现逻辑

介绍了基于二阶项重写技术的机器发现逻辑理论及两个实验系统DI和ALP.同时举例说明了ALP系统的工作原理,展示了机器发现逻辑在数学发现(?)逻辑程序自动设计领域的应用前景。

有序类代数的操作语义

本文简要介绍有序类代数的基本概念，研究有序类等式演绎，并且给出了有序类代数上进行基于规则的项重写的操作语义．

重叠规则与歧义性

重写系统是一种一般的计算模型，重写系统的归约策略的范式化性质对于实际应用重写系统进行计算具有决定意义，而重叠规则导致的歧义性是使归约过程复杂化重要原因，本文对重写系统的歧义性进行了初步研究，并对一类常见的歧义问题作了具体分析，同时提出了解决办法。