摘要： 图重写能够有效地实现项重写．文章从项重写的图实现的角度出发，研究了图重写模拟项重写的正确性和完备性；在无环出现的倩况下，图重写对一切项重写正确；在无环出现的条件下，图重写对左线性合流的项重写是完备的．据此，作者又研究了规则、共享和环生成的关系，从而指导操作，避免环的产生，保证正确性和完备性。以上结果能够用于指导项重写的图实现。

关键词: 项重写, 图重写, 项图重写, 有向无环图, 函数式语言

Abstract: Graph rewriting is an efficient technique for implementing term rewriting system.From the angle of implementation, we study the soundness and completeness of graph rewriting simulating term rewriting. In the no-cycle-appear case, graph rewriting is sound for all term rewriting. Under the no-cyclettippear condition, graph rewriting is complete for left-linear confluent term rewriting. Based on this, we study the relation among rule, sharing and cycle-generation which can direct operation to avoid cycle appear. These results can direct the implementing of term rewriting system by graph rewriting system.

中图分类号: 

• TP311