| 项重写的图实现 |
| |
| 引用本文： | 杨继锋,孙永强. 项重写的图实现[J]. 计算机工程, 1998, 24(4): 3-6,15 |
| |
| 作者姓名： | 杨继锋 孙永强 |
| |
| 作者单位： | 上海交通大学计算机科学与工程系,上海,200030 |
| |
| 摘 要： | 图重写能够有效地实现项重写。文章从项重写的图实现的角度出发，研究了图重写模拟项重写的正确性和完备性：在无环出现的情况下，图重写对一切项重写下正确；在无环出现的条件下，图重写对左线性合流的项重写是完备的。
|
| 关 键 词： | 项重写 图重写 图实现 函数式语言 |
Term Rewriting Implemented by Graph Rewriting |
| |
| Yang Jifeng,SUN Yongqiang. Term Rewriting Implemented by Graph Rewriting[J]. Computer Engineering, 1998, 24(4): 3-6,15 |
| |
| Authors: | Yang Jifeng SUN Yongqiang |
| |
| 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. |
| |
| Keywords: | Term rewriting Graph rewriting Term graph rewriting DAG Functional programming language |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
