کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
423639 685267 2008 17 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Towards a Sharing Strategy for the Graph Rewriting Calculus
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Towards a Sharing Strategy for the Graph Rewriting Calculus
چکیده انگلیسی

The graph rewriting calculus is an extension of the ρ-calculus, handling graph like structures rather than simple terms. The calculus over terms is naturally generalized by using unification constraints in addition to the standard ρ-calculus matching constraints. The transformations are performed by explicit application of rewrite rules as first class entities. The possibility of expressing sharing and cycles allows one to represent and compute over regular infinite entities.We propose in this paper a reduction strategy for the graph rewriting calculus which aims at maintaining the sharing information as long as possible in the terms. The corresponding reduction relation is shown to be confluent and complete w.r.t. the small-step semantics of the graph rewriting calculus.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Theoretical Computer Science - Volume 204, 4 April 2008, Pages 111-127