Lazy Graph Transformation

• Autorzy: Orejas F. , Lambers L.
• Języki publikacji: EN

Abstrakty

EN

Applying an attributed graph transformation rule to a given object graph always implies some kind of constraint solving. In many cases, the given constraints are almost trivial to solve. For instance, this is the case when a rule describes a transformation G ⇒ H, where the attributes of H are obtained by some simple computation from the attributes of G. However there are many other cases where the constraints to solve may be not so trivial and, moreover, may have several answers. This is the case, for instance, when the transformation process includes some kind of searching. In the current approaches to attributed graph transformation these constraints must be completely solved when defining the matching of the given transformation rule. This kind of early binding is well-known from other areas of Computer Science to be inadequate. For instance, the solution chosen for the constraints associated to a given transformation step may be not fully adequate, meaning that later, in the search for a better solution, we may need to backtrack this transformation step. In this paper, based on our previous work on the use of symbolic graphs to deal with different aspects related with attributed graphs, including attributed graph transformation, we present a new approach that, based on the new notion of narrowing graph transformation rule, allows us to delay constraint solving when doing attributed graph transformation, in a way that resembles lazy computation. For this reason, we have called lazy this new kind of transformation. Moreover, we show that the approach is sound and complete with respect to standard attributed graph transformation. A running example, where a graph transformation system describes some basic operations of a travel agency, shows the practical interest of the approach.

Słowa kluczowe

EN

attributed graph transformation; symbolic graph transformation; lazy transformation

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 118, nr 1-2
• Strony: 65--96
• Opis fizyczny: Bibliogr. 16 poz., rys., tab.

Twórcy

autor

Orejas F.

autor

Lambers L.

• Departament de Llenguatges i Sistemes Informatics, Universitat Politecnica de Catalunya, 08034 Barcelona, Spain,

Bibliografia

• [1] Berthold, M., Fischer, I. and Koch M. (2000) Attributed Graph Transformation with Partial Attribution. Technical Report 2000-2.
• [2] Ehrig, H. (2004) Attributed Graphs and Typing: Relationship between Different Representations. Bulletin of the EATCS, 82: 175-190.
• [3] Ehrig, H., Ehrig, K., Prange, U. and Taentzer, G. (2006) Fundamentals of Algebraic Graph Transformation, Springer.
• [4] Ehrig, H., Padberg, J., Prange, U. and Habel A. (2006) Adhesive High-Level Replacement Systems: A New Categorical Framework for Graph Transformation. Fundamenta Informaticae, 74(1): 1-29.
• [5] Ehrig, H., Ehrig, K., Prange, U. and Taentzer, G. (2006) Fundamental Theory for Typed Attributed Graphs and Graph Transformation based on Adhesive HLR Categories. Fundamenta Informaticae, 74(1): 31-61.
• [6] Ehrig, H., Mahr, B. (1985) Fundamentals of Algebraic Specifications 1: Equations and Initial Semantics. Vol. 6 of EATCS Monographs on Theoretical Computer Science. Springer.
• [7] Heckel, R., Küster, J. and Taentzer, G. (2002) Towards Automatic Translation of UML Models into Semantic Domains. In Proc. APPLIGRAPH Workshop on Applied Graph Transformation, pp. 11-22.
• [8] Knuth D.E (1968) Semantics of context-free languages, Mathematical Systems Theory, 2: 127-145.
• [9] Jaffar, J., Maher, M., Marriot, P., and Stukey P. (1998) The semantics of constraint logic programs. The Journal of Logic Programming, 37:1-46.
• [10] Löwe, M., Korff, M. and Wagner A. (1993) An Algebraic Framework for the Transformation of Attributed Graphs. In Term Graph Rewriting: Theory and Practice, 185-199. John Wiley and Sons Ltd.
• [11] Lack, S. and Sobocinski P. (2005) Adhesive and quasi adhesive categories. Theoretical Informatics and Applications, 39(3): 511-545.
• [12] Orejas F. (2008) Attributed Graph Constraints. In Graph Transformations, 4th International Conference, ICGT 2008, Springer LNCS 5214, 274-288.
• [13] Orejas F. (2011) Attributed Graph Constraints for Attributed Graph Transformation. Journal of Symbolic Computation, 46 (3): 294-315.
• [14] Orejas F. and Lambers, L. (2010) Symbolic Attributed Graphs for Attributed Graph Transformation. Int. Coll. on Graph and Model Transformation On the occasion of the 65th birthday of Hartmut Ehrig. Comm. of the EASST, 30.
• [15] Orejas F. and Lambers, L. (2010) Delaying Constraint Solving in Attributed Graph Transformation. In Graph Transformations, 5th International Conference, ICGT 2010, Springer LNCS 6372, 43-58.
• [16] Plump, D. and Steinert S. (2004) Towards Graph Programs for Graph Algorithms. In Graph Transformations, Second International Conference, ICGT 2004,Springer LNCS 3256, 128-143.