项重写的图实现  

Term Rewriting Implemented by Graph Rewriting

作　　者：杨继锋[1] 孙永强[1] 

机构地区：[1]上海交通大学计算机科学与工程系,上海200030

出　　处：《计算机工程》1998年第4期3-6,15,共5页Computer Engineering

基　　金：国家九五科技攻关项目

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

关 键 词：项重写 图重写 图实现 函数式语言 

分 类 号：TP312[自动化与计算机技术—计算机软件与理论]