Rewriting Techniques for Non-Deterministic Computation

项重写是函数式编程和定理证明的计算模型。在本研究项目中，我们根据相对终止重新审视了其基本理论。作为一个结果，我们建立了一个新的合流准则，统一了两个主要的合流准则（罗森的正交性和Knuth和Benzen的完全性）的左线性系统。此外，我们引入了一种新的自动演绎技术，称为最大完成。基于这些新技术，我们开发了功能强大的汇流分析器Saigawa和全自动完成工具Maxcomp。

Term rewriting is a computational model which underlies functional programming and theorem proving. In this research project we revisited its fundamental theory in the light of relative termination. As an outcome, we established a new confluence criterion that unifies two major confluence criteria (Rosen’s orthogonality and Knuth and Bendix’ completeness) for left-linear systems. Moreover, we introduced a new technique for automated deduction, dubbed maximal completion. Based on those new technologies, we developed the powerful confluence analyzer Saigawa and the fully automatic completion tool Maxcomp.