Open AccessTermination Criteria for DPO Transformations with Injective Matches
Author(s) -
Tihamér Levendovszky,
Ulrike Prange,
Hartmut Ehrig
Publication year - 2007
Publication title -
electronic notes in theoretical computer science
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.242
H-Index - 60
ISSN - 1571-0661
DOI - 10.1016/j.entcs.2007.04.019
Subject(s) - graph rewriting , injective function , transitive closure , transformation (genetics) , model transformation , computer science , graph , theoretical computer science , transitive relation , model checking , closure (psychology) , algorithm , mathematics , discrete mathematics , artificial intelligence , combinatorics , biochemistry , chemistry , consistency (knowledge bases) , economics , market economy , gene
Reasoning about graph and model transformation systems is an important means to underpin model-driven software engineering, such as Model-Driven Architecture (MDA) and Model Integrated Computing (MIC). Termination criteria for graph and model transformation systems have become a focused area recently. This paper provides termination criteria for graph and model transformation systems with injective matches and finite input structure. It proposes a treatment for infinite sequences of rule applications, and takes attribute conditions, negative application conditions, and type constraints into account. The results are illustrated on case studies excerpted from real-world transformations, which show the termination properties of the frequently used "transitive closure" and "leaf collector" transformation idioms. An intuitive comparison with other approaches is also given
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom