Inequational Deduction as Term Graph Rewriting

Multi-algebras allow to model nondeterminism in an algebraic framework by interpreting operators as functions from individual arguments to sets of possible results.We propose a simple inequational deduction system, based on term graphs, for inferring inclusions of derived relations in a multi-algebra, and we show that term graph rewriting provides a sound and complete implementation of it.     

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

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

项重写的图实现

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

Reachability Analysis over Term Rewriting Systems

This paper surveys some techniques and tools for achieving reachability analysis over term rewriting systems. The core of those techniques is a generic tree automata completion algorithm used to compute in an exact or approximated way the set of descendants (or reachable terms). This algorithm has been implemented in the tool. Furthermore, we show that many classes with regular sets of descendants of the literature corresponds to specific instances of the tree automata completion algorithm and can thus be efficiently computed by . An extension of the completion algorithm to conditional term rewriting systems and some applications are also presented.     

A Rewriting Logic Approach to Operational Semantics (Extended Abstract)

This paper shows how rewriting logic semantics (RLS) can be used as a computational logic framework for operational semantic definitions of programming languages. Several operational semantics styles are addressed: big-step and small-step structural operational semantics (SOS), modular SOS, reduction semantics with evaluation contexts, and continuation-based semantics. Each of these language definitional styles can be faithfully captured as an RLS theory, in the sense that there is a one-to-one correspondence between computational steps in the original language definition and computational steps in the corresponding RLS theory. A major goal of this paper is to show that RLS does not force or pre-impose any given language definitional style, and that its flexibility and ease of use makes RLS an appealing framework for exploring new definitional styles.     

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.     

Strongly Typed Rewriting For Coupled Software Transformation

Coupled transformations occur in software evolution when multiple artifacts must be modified in such a way that they remain consistent with each other. An important example involves the coupled transformation of a data type, its instances, and the programs that consume or produce it. Previously, we have provided a formal treatment of transformation of the first two: data types and instances. The treatment involved the construction of type-safe, type-changing strategic rewrite systems. In this paper, we extend our treatment to the transformation of corresponding data processing programs.The key insight underlying the extension is that both data migration functions and data processors can be represented type-safely by a generalized abstract data type (GADT). These representations are then subjected to program calculation rules, harnessed in type-safe, type-preserving strategic rewrite systems. For ease of calculation, we use point-free representations and corresponding calculation rules.Thus, coupled transformations are carried out in two steps. First, a type-changing rewrite system is applied to a source type to obtain a target type together with (representations of) migration functions between source and target. Then, a type-preserving rewrite system is applied to the composition of a migration function and a data processor on the source (or target) type to obtain a data processor on the target (or source) type. All rewrites are type-safe.     

一个基于抽象解释的部分演绎过程

本文提出一种新的基于抽象解释的逻辑程序部分演绎方法．在一遍预处理里，针对给定的程序Ｐ和目标Ｇ，同时进行Ｐ∪｛Ｇ｝的部分演绎和抽象解释，以抽象解释控制部分演绎的展开过程．只要抽象论域是有穷的，部分演绎必定终止，而且Ｐ＇带有抽象解释估算出的关于其运行性质的信息，便于对Ｐ作进一步优化．     

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.     

A Rewriting Machine and Optimization of Strategies of Term Rewriting

An algebraic specification of a new rewriting machine for fast rewriting of terms is considered. Theorems on the correctness of this specification are proved. A method for optimization of a strategy of iterative rewriting is proposed.     

抽象数据类型的双代数结构及其计算

程序语言中的许多抽象数据类型包含了可递归定义的语法构造和可共递归定义的动态行为特征,因此单纯利用代数或共代数难以给出完整的描述.双代数是同一载体集上的代数和共代数对,提供了一种从范畴论的角度探讨抽象数据类型上的语法构造和动态行为关系及性质的可行途径.给出抽象数据类型的双代数结构,并利用代数函子对共代数函子的分配律描述了语法构造与动态行为之间的自然转换关系;利用分配律对共代数和代数函子进行函子化提升,给出一种构造初始代数(或终结共代数)上的共代数(或代数)结构,并将其提升为初始(或终结)λ-双代数的方法.在此基础上,进一步将函子化提升应用于各种递归(包括迭代和原始递归)及共递归函数(包括共迭代和原始共递归)的定义及计算中,并给出相应的计算定律.     

Strategic Rewriting

This is a position paper preparing the round table organized during the 4th International Workshop on Reduction Strategies in Rewriting and Programming. I sketch what I believe to be important challenges of strategic rewriting.     

Some group theoretic examples with completion theorem provers

In this paper we investigate the performance of completion theorem provers on a number of group theoretic problems. These are of a rather different character to the usual test problems and exercise different features of the programs. Very large rewriting systems and very deeply nested terms arise, but, where the programs allow, additional mathematical information can often by used to dramatically speed the computations. We compare two general-purpose theorem provers with some more specialised tools and conclude by drawing some lessons for the design of future general-purpose provers.     

Lifting Infinite Normal Form Definitions From Term Rewriting to Term Graph Rewriting

nfinite normal forms are a way of giving semantics to non-terminating rewrite systems. The notion is a generalization of the Böhm tree in the lambda calculus. It was first introduced in [Ariola, Z. M. and S. Blom, Cyclic lambda calculi, in: Abadi and Ito [Abadi, M. and T. Ito, editors, “Theoretical Aspects of Computer Software,” Lecture Notes in Computer Science 1281, Springer Verlag, 1997], pp. 77–106] to provide semantics for a lambda calculus on terms with letrec. In that paper infinite normal forms were defined directly on the graph rewrite system. In [Blom, S., “Term Graph Rewriting - syntax and semantics,” Ph.D. thesis, Vrije Universiteit Amsterdam (2001)] the framework was improved by defining the infinite normal form of a term graph using the infinite normal form on terms. This approach of lifting the definition makes the non-confluence problems introduced into term graph rewriting by substitution rules much easier to deal with. In this paper, we give a simplified presentation of the latter approach.     

Matrix Interpretations for Proving Termination of Term Rewriting

We present a new method for automatically proving termination of term rewriting. It is based on the well-known idea of interpretation of terms where every rewrite step causes a decrease, but instead of the usual natural numbers we use vectors of natural numbers, ordered by a particular nontotal well-founded ordering. Function symbols are interpreted by linear mappings represented by matrices. This method allows us to prove termination and relative termination. A modification of the latter, in which strict steps are only allowed at the top, turns out to be helpful in combination with the dependency pair transformation. By bounding the dimension and the matrix coefficients, the search problem becomes finite. Our implementation transforms it to a Boolean satisfiability problem (SAT), to be solved by a state-of-the-art SAT solver.     

几种软件抽象机制及其开发技术的分析比较

软件抽象机制是软件技术的基础,其发展具有继承性,对象是过程抽象的发展,agent是对象的进化和发展。文中分析了过程、对象、agent等三种重要的软件抽象机制的特点及相应开发技术,讨论了它们之间的区别和联系,揭示了软件抽象机制发展的趋势。     

Formalizing and Analyzing the Needham-Schroeder Symmetric-Key Protocol by Rewriting

This paper reports on work in progress on using rewriting techniques for the specification and the verification of communication protocols. As in Genet and Klay's approach to formalizing protocols, a rewrite system describes the steps of the protocol and an intruder's ability of decomposing and decrypting messages, and a tree automaton encodes the initial set of communication requests and an intruder's initial knowledge. In a previous work we have defined a rewriting strategy that, given a term t that represents a property of the protocol to be proved, suitably expands and reduces t using the rules in and the transitions in to derive whether or not t is recognized by an intruder. In this paper we present a formalization of the Needham-Schroeder symmetric-key protocol and use the rewriting strategy for deriving two well-known authentication attacks.     

The Rewriting Logic Semantics Project

Rewriting logic is a flexible and expressive logical framework that unifies denotational semantics and SOS in a novel way, avoiding their respective limitations and allowing very succinct semantic definitions. The fact that a rewrite theory's axioms include both equations and rewrite rules provides a very useful “abstraction knob” to find the right balance between abstraction and observability in semantic definitions. Such semantic definitions are directly executable as interpreters in a rewriting logic language such as Maude, whose generic formal tools can be used to endow those interpreters with powerful program analysis capabilities.