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.
|Autori:||Corradini A; Rossi F|
|Titolo:||Hyperedge Replacement Jungle Rewriting for Term-Rewriting Systems and Programming|
|Anno del prodotto:||1993|
|Digital Object Identifier (DOI):||10.1016/0304-3975(93)90063-Y|
|Appare nelle tipologie:||1.1 Articolo in rivista|