项重写的图实现

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

Term Rewriting Implemented by Graph Rewriting

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.