HYPEREDGE REPLACEMENT JUNGLE REWRITING FOR TERM-REWRITING SYSTEMS AND LOGIC PROGRAMMING

被引：15
作者：
CORRADINI, A
ROSSI, F
机构：
[1] Università di Pisa, Dipartimento di Informatica, 56125 Pisa
来源：
THEORETICAL COMPUTER SCIENCE | 1993年 / 109卷 / 1-2期
关键词：
D O I：
10.1016/0304-3975(93)90063-Y
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We introduce hyperedge replacement jungle rewriting, a graph-rewriting formalism suitable for modeling the manipulation of terms and similar structures, and investigate its expressive power by showing that it can model both term-rewriting systems and logic programming in a faithful way. For term-rewriting systems we prove the soundness of their jungle representation, and a result of completeness w.r.t. applicability which is stronger than similar results in the related literature, since it works also for non-left-linear rules. For logic programming both soundness and completeness hold.
引用
收藏
页码：7 / 48
页数：42
相关论文
共 31 条
[1]  
ASPERTI A, 1989, 6TH P INT C LOG PROG, P337
[2]  
BARENDREGT HP, 1987, LECT NOTES COMPUT SC, V259, P141
[3]   GRAPH EXPRESSIONS AND GRAPH REWRITINGS [J].
BAUDERON, M ;
COURCELLE, B .
MATHEMATICAL SYSTEMS THEORY, 1987, 20 (2-3) :83-127
[4]  
Colmerauer A, 1982, PROLOG 2 REFERENCE M
[5]  
CORRADINI A, 1991, LECT NOTES COMPUT SC, V493, P275
[6]  
CORRADINI A, 1991, LECT NOTES COMPUT SC, V532, P221, DOI 10.1007/BFb0017392
[7]  
CORRADINI A, 1992, IN PRESS LECTURE NOT
[8]  
COURCELLE B, 1988, PROGRAMMING FUTURE G, V2, P83
[9]  
COURCELLE B, 1988, THEORET COMPUT SCI, V78, P217
[10]  
EHRIG H, 1991, LECT NOTES COMPUT SC, V532, P269, DOI 10.1007/BFb0017395
1234