Context-exploiting shapes for diagram transformation

• Autorzy: Drewes F. , Hoffmann B. , Minas M.
• Języki publikacji: EN

Abstrakty

EN

DIA PLAN is a language for programming with graphs representing diagram that is currently being developed. The computational model of the language - nested graph transformation - suports nested structuring of graphs and graph variables, but is still intuitive. This paper discusses structural typing of nested graphs and nested graph transformation systems by shape rules. We extend the context-free shape rules proposed in earlier work to contexy-exploiting shape rules with which many relevant graph structures can be specifed. The conformance of a nested graph to the shape rules is decidable. If a trabsformation system conforms to shape rules as well. it can be shown to preserve shape conformance of the graphs it is applied to. This sets up a static type discipline for nested graph transformation.

Słowa kluczowe

EN

graph transformation; diagram language; visual programming; data type

• Wydawca: Institute of Information Technology of the Warsaw University of Life Sciences – SGGW
• Czasopismo: Machine Graphics and Vision
• Rocznik: 2003
• Tom: Vol. 12, No. 1
• Strony: 117--132
• Opis fizyczny: Bibliogr. 19 poz., rys.

Twórcy

autor

Drewes F.

• Institutionen för Datavetenskap, Umeå Universitet, S-90187 Umeå

autor

Hoffmann B.

• Technologiezentrum Informatik, Universität Bremen, D-28334 Bremen

autor

Minas M.

• Fachbereich Informatik, Universität der Bundeswehr, D-85577 Neubiberg

Bibliografia

• [1] Ehrig H.: lntroduction to the algebraic theory of graph grammars. Claus V., Ehrig H., Rozenberg G. (Ecls.): Proc. Graph Grammars and Their Application to Computer Science and Biology, LNCS, 73, 1-69. Springer. 1979.
• [2] Habel A.: Hypereclge Replacement : Grammars and Languages. LNCS, 643. Springer. 1992.
• [3] Klop J. W.: Term rewriting systems. Abramsky S., Gabbay D. M., Maibaum T. (Eds.): Handbook of Logic in Computer Science, vol. 2, 1-116. Oxford University Press. 1992.
• [4] Corradini A., Ehrig H., Lowe M., Montanari U., Padberg J.: The category of typed graph grammars and its adjunction with categories of derivations. Proc. Graph Grammars and Their Application to Computer Science, LNCS, 1073, 56-74. Springer. 1996.
• [5] Drewes F., Habel A.,Kreowski H.-J.: Hyperedge replacement graph grammars. Rozenberg G. (Ed.): Handbook of Graph Grammars and Computing by Graph Transformation. I: Foundations, chap. 2, 95-162. World Scientific, Singapore. 1997.
• [6] Minas M.: Diagram editing with hypergraph parser support. Proc. VL'97, Capri, Italy, 230-237.
• [7] Fradet P., Le Métayer D.: Structured Gamma. Science of Computer Programming, 31(2/3), 263-289. 1998.
• [8] Sagiv M., Reps T., Wilhelm R.: Solving shape-analysis problems in languages with destructive updating. ACM Trans. on Programming Languages and Systems, 20(1), 1-50. 1998.
• [9] Bardohl R., Minas M., Schürr A., Taentzer G.: Application of graph transformation to visual languages. In Engels et al. [10], chap. 3, 105-180. 1999.
• [10] Engels G., Ehrig H. , Kreowski H.-J., Rozenberg G., (Eds.): Handbook of Graph Grammars and Computing by Graph Transformation, II: Specification and Programming. World Scientific, Singapore. 1999.
• [11] Schürr A., Winter A., Zündorf A.: The PROGRES approach: Language and environment. Engels et al. [10], chap. 13, 487-550. 1999.
• [12] Engels G., Heckel R.: Graph transformation as a conceptual and formal framework for system modelling and evolution. Proc. ICALP 2000, LNCS 1853, 127-150. Springer. 2000.
• [13] Hoffmann B.: Shapely hierarchical graph transformation. Proc. IEEE Symp. on Human-Centric Computing Languages and Environments, IEEE Computer Press, 30-37. 2001.
• [14] Minas M., Hoffmann B.: Specifying and implementing visual process modeling languages with DIAGEN. Electronic Notes in Theoretical Computer Science, 44(4). 2001.
• [15] Bakewell A., Plump D., Runciman C.: Specifying pointer structures by graph reduction. TR, Department of Computer Science, University of York. 2002.
• [16] Drewes F., Hoffmann B., Minas M.: Constructing shapely nested graph transformations. Proc. AGT'02, 107-118. 2002.
• [17] Drewes F., Hoffmann B., Plump D.: Hierarchical graph transformation. J. of Computer and System Sciences, 64, 249-283. 2002.
• [18] Hoffmann B.: Abstraction and control for shapely nested graph transformation. Proc. ICGT '02, LNCS, 2505, 177-191. Springer. 2002.
• [19] Minas M.: Concepts and realization of a diagram editor generator based on hypergraph transformation. Science of Computer Programming, 44, 157-180. 2002.