归纳法推理中的项重写策略*

本文介绍归纳法推理系统中的项重写策略．该策略根据不同的待重写项term，分别运用公理、重写引理、函数定义、项重写规则等重写项term，以期得到一个更接近推理目标的巳重写项．这一策略已在微机上用编译LlsP语言实现．     

动态项重写计算

1.引言项重写系统是一种受到广泛研究和应用的形式计算模型。一个项重写系统由一组称为重写规则的定向等式组成。它的计算基于代入、匹配和替换,除具有方向性外,与等式推导一致。虽然项重写系统形式简单、计算单纯,但它同时又具有与λ计算及图灵机相同的计算能力。正是它的简洁性及计算能力使它受到广泛的研究和应用:项重写系统为抽象数据类型提供类型、为函数型语言提供操作语义、为定理自动证明提供推理工具。对于项重写系统本身也有大量的研究:如合流性、终止性、等价性等。     

项重写的图实现

图重写能够有效地实现项重写。文章从项重写的图实现的角度出发，研究了图重写模拟项重写的正确性和完备性：在无环出现的情况下，图重写对一切项重写下正确；在无环出现的条件下，图重写对左线性合流的项重写是完备的。     

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

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

归纳法推理中的项重写策略

本文介绍归纳法推理系统中的项重写策略，该策略根据不同的待重写项ｔｅｒｍ，分别运用公理、重写引理、函数定义、项重写规则等重写项ｔｅｒｍ，以期得到一个更接近推理目标的已重写项，这一策略已在微机上用编译ＬＩＳＰ语言实现。     

重叠规则与歧义性*

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

重写系统的模块分解

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

用sendmail仿真一个图灵机

简单地介绍了sendmail的重写规则,提出了在sendmail的配置文件中,利用重写规则编写仿真图灵机操作的方法,最后给出了两个图灵机程序(规则集)的实现.     

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

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

重写技术及其在计算机科学中的应用

项重写系统是一种描述不确定计算的计算模型。近十年来,重写技术在计算机科学的许多重要领域得到广泛应用,表现出作为知识信息处理系统的良好性质,引起了人们对重写技术的重视,本文介绍重写技术的主要内容,着重强调了完全过程的思想。同时说明了目前重写技术几个活跃的研究课题。本文还介绍了重写技术在自动定理证明、逻辑程序设计和软件开发中的应用。     

Hierarchical Nominal Terms and Their Theory of Rewriting

Nominal rewriting introduced a novel method of specifying rewriting on syntax-with-binding. We extend this treatment of rewriting with hierarchy of variables representing increasingly 'meta-level' variables, e.g. in hierarchical nominal term rewriting the meta-level unknowns (representing unknown terms) in a rewrite rule can be 'folded into' the syntax itself (and rewritten). To the extent that rewriting is a mathematical meta-framework for logic and computation, and nominal rewriting is a framework with native support for binders, hierarchical nominal term rewriting is a meta-to-the-omega level framework for logic and computation with binders.     

Conditional Term Graph Rewriting with Indirect Sharing

For reasons of efficiency, term rewriting is usually implemented by term graph rewriting. In term rewriting, expressions are represented as terms, whereas in term graph rewriting these are represented as directed graphs. Unlike terms, graphs allow a sharing of common subexpressions. In previous work, we have shown that conditional term graph rewriting is a sound and complete implementation for a certain class of CTRSs with strict equality, provided that a minimal structure sharing scheme is used. In this paper, we will show that this is also true for two different extensions of normal CTRSs. In contrast to the previous work, however, a non-minimal structure sharing scheme can be used. That is, the amount of sharing is increased.     

External Rewriting for Skeptical Proof Assistants

This paper presents the design, the implementation, and experiments of the integration of syntactic, conditional possibly associative-commutative term rewriting into proof assistants based on constructive type theory. Our approach is called external because it consists in performing term rewriting in a specific and efficient environment and checking the computations later in a proof assistant. Two typical systems are considered in this work: ELAN, based on the rewriting calculus, as the term rewriting-based environment, and Coq, based on the calculus of inductive constructions as the proof assistant. We first formalize the proof terms for deduction by rewriting and strategies in ELAN using the rewriting calculus with explicit substitutions. We then show how these proof terms can soundly be translated into Coq syntax where they can be directly type checked. For the method to be applicable for rewriting modulo associativity and commutativity, we provide an effective method to prove equalities modulo these axioms in Coq using ELAN. These results have been integrated into an ELAN-based rewriting tactic in Coq.     

Proving termination of context-sensitive rewriting by transformation

Context-sensitive rewriting (CSR) is a restriction of rewriting that forbids reductions on selected arguments of functions. With CSR, we can achieve a terminating behavior with non-terminating term rewriting systems, by pruning (all) infinite rewrite sequences. Proving termination of CSR has been recently recognized as an interesting problem with several applications in the fields of term rewriting and programming languages. Several methods have been developed for proving termination of CSR. Specifically, a number of transformations that permit treating this problem as a standard termination problem have been described. The main goal of this paper is to contribute to a better comprehension and practical use of transformations for proving termination of CSR. We provide new completeness results regarding the use of the transformations in two restricted (but relevant) settings: (a) proofs of termination of canonical CSR and (b) proofs of termination of CSR by using transformations together with simplification orderings. We have also made an experimental evaluation of the transformations, which complements the theoretical analysis from a practical point of view. This leads to new hierarchies of the transformations which are useful to guide their practical use when implementing tools for proving termination of CSR.     

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.     

Rewriting-Based Navigation of Web Sites: Looking for Models and Logics

In this paper we outline the use of term rewriting techniques for modeling the dynamic behavior of Web sites. We associate rewrite rules to each Web page expressing the Web pages which are immediately reachable from this page. The obtained system permits the application of well-known results from the rewriting theory to analyse interesting properties of the Web site. In particular, we briefly discuss the use of some logics with strong connections with term rewriting as a basis for specifying and verifying dynamic properties of Web sites. We use Maude as a suitable specification language for such rewriting models which also permits to directly explore interesting dynamic properties of Web sites.     

An Algebraic Baseline for Automatic Transformations in MDA

Software evolution can be supported at two levels: models and programs. The model-based software development approach allows the application of a more abstract process of software evolution, in accordance with the OMG's MDA initiative. We describe a framework for model management, called MOMENT, that supports automatic formal model transformations in MDA. Our model transformation approach is based on the algebraic specification of models and benefits from mature term rewriting system technology to perform model transformation using rewriting logic. In this paper, we present how we apply this formal transformation mechanism between platformindependent models, such as UML models and relational schemas. Our approach enhances the integration between formal environments and industrial technologies such as .NET technology, and exploits the best features of both.     

From Chemical Rules to Term Rewriting

In this paper, rule-based programming is explored in the field of automated generation of chemical reaction mechanisms. We explore a class of graphs and a graph rewriting relation where vertices are preserved and only edges are changed. We show how to represent cyclic labeled graphs by decorated labeled trees or forests, then how to transform trees into terms. A graph rewriting relation is defined, then simulated by a tree rewriting relation, which can be in turn simulated by a rewriting relation on equivalence classes of terms. As a consequence, this kind of graph rewriting can be implemented using term rewriting. This study is motivated by the design of the GasEl system for the generation of kinetics reactions mechanisms. In GasEl, chemical reactions correspond to graph rewrite rules and are implemented by conditional rewriting rules in ELAN. The control of their application is done through the ELAN strategy language.     

Lazy productivity via termination

We present a procedure for transforming strongly sequential constructor-based term rewriting systems (TRSs) into context-sensitive TRSs in such a way that productivity of the input system is equivalent to termination of the output system. Thereby automated termination provers become available for proving productivity. A TRS is called productive if all its finite ground terms are constructor normalizing, and all ‘inductive constructor paths’ through the resulting (possibly non-wellfounded) constructor normal form are finite. To our knowledge, this is the first complete transformation from productivity to termination.The transformation proceeds in two steps: (i) The strongly sequential TRS is converted into a shallow TRS, where patterns do not have nested constructors. (ii) The shallow TRS is transformed into a context-sensitive TRS, where rewriting below constructors and in arguments not ‘consumed from’ is disallowed.Furthermore, we show how lazy evaluation can be encoded by strong sequentiality, thus extending our transformation to, e.g., Haskell programs.Finally, we present a simple, but fruitful extension of matrix interpretations to make them applicable for proving termination of context-sensitive TRSs.