Abstraction and Control for Shapely Nested Graph Transformation

• Autorzy: Hoffmann B.
• Języki publikacji: EN

Abstrakty

EN

Shapely nested graph transformation is the computational model for DIAPLAN, a language for programming with graphs representing diagrams that is currently being developed. The model supports nested structuring of graphs, structural graph types (shapes), and rules with graph variables. We extend this model by two concepts that are essential for programming: abstraction allows compound transformations to be named and parameterized; control allows the order of rule application to be specified. These concepts refine the computational model with respect to structuring and efficiency needs of a programming language while preserving its rule-based and graph-ical nature.

Słowa kluczowe

EN

graph transformation; nested graph; diagram; graph typing; abstraction; control

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2003
• Tom: Vol. 58, nr 1
• Strony: 39--65
• Opis fizyczny: Bibliogr. 54 poz., rys., tab., wykr.

Twórcy

autor

Hoffmann B.

• Technologiezentrum Informatik, Universität Bremen, Postfach 330 440, D-28334 Bremen, Germany,

Bibliografia

• [1] Arnold, K., Gosling, J.: The Java Programming Language, Java Series, Addison-Wesley, Reading, Massachusetts, 1998, 2nd edition.
• [2] Bakewell, A., Plump, D., Runciman, C.: Specifying Pointer Structures by Graph Reduction, Technical report, Department of Computer Science, University of York, Nov. 2002.
• [3] Banâtre, J.-P., Le Métayer, D.: Gamma and the Chemical Reaction Model: Ten Years after, in: Coordination Programming: Mechanisms, Models, and Semantics, World Scientific, 1996, 3-41.
• [4] Bardohl, R., Minas, M., Schürr, A., Taentzer, G.: Application of Graph Transformation to Visual Languages, in: Engels et al. [20], chapter 3, 105-180.
• [5] Barendregt, H. P.: The Lambda Calculus—Its Syntax and Semantics, North-Holland, Amsterdam, 1981.
• [6] Berge, C.: Graphs and Hypergraphs, North Holland, Amsterdam, 1973.
• [7] Burnett, M. M., Goldberg, A., Lewis, T. G., Eds.: Visual Object-Oriented Programming, Manning, 1995.
• [8] Busatto, G.: An Abstract Model of Hierarchical Graphs and Hierarchical Graph Transformation, Dissertation, Universität Paderborn, June 2002.
• [9] Corradini, A., Ehrig, H., Heckel, R., Löwe, M., Montanari, U., Rossi, F.: Algebraic Approaches to Graph Transformation Part I: Basic Concepts and Double Pushout Approach, in: Rozenberg [48], chapter 3, 163-245.
• [10] Corradini, A., Ehrig, H., Montanari, U., Padberg, J.: The Category of Typed Graph Grammars and its Adjunction with Categories of Derivations, in: Cuny et al. [12], 56-74.
• [11] Corradini, A., Rossi, F.: Hyperedge Replacement Jungle Rewriting for Term Rewriting Systems and Logic Programming, Theoretical Computer Science, 109, 1993, 7-48.
• [12] Cuny, J. E., Ehrig, H., Engels, G., Rozenberg, G., Eds.: Proc. Graph Grammars and Their Application to Computer Science, number 1073 in Lecture Notes in Computer Science, Springer, 1996.
• [13] Drewes, F., Habel, A., Kreowski, H.-J.: Hyperedge Replacement Graph Grammars, in: Rozenberg [48], chapter 2, 95-162.
• [14] Drewes, F., Hoffmann, B., Minas, M.: Constructing Shapely Nested Graph Transformations, Proc. Int’lWorkshop on Applied Graph Transformation (AGT’02) (H.-J. Kreowski, P. Knirsch, Eds.), 2002, 107-118.
• [15] Drewes, F., Hoffmann, B., Minas, M.: Context-Exploiting Shapes for Diagram Transformation, Machine Graphics and Vision, 12(1), 2003, 117-132.
• [16] Drewes, F., Hoffmann, B., Plump, D.: Hierarchical Graph Transformation, Journal of Computer and System Sciences, 64(2), 2002, 249-283.
• [17] Ehrig, H.: Introduction to the Algebraic Theory of Graph Grammars, Proc. Graph Grammars and Their Application to Computer Science and Biology (V. Claus, H. Ehrig, G. Rozenberg, Eds.), number 73 in Lecture Notes in Computer Science, Springer, 1979.
• [18] Ehrig, H., Heckel, R., Löwe, M., Ribeiro, L., Wagner, A., Corradini, A.: Algebraic Approaches to Graph Transformation Part II: Single Pushout Approach and Comparison to Double Pushout Approach, in: Rozenberg [48], chapter 4, 247-312.
• [19] Ehrig, H., Löwe, M.: Categorical Principles, Techniques and Results for High-Level Replacement Systems in Computer Science, Applied Categorical Structures, 1(1), 1993, 21-50.
• [20] Engels, G., Ehrig, H., Kreowski, H.-J., Rozenberg, G., Eds.: Handbook of Graph Grammars and Computing by Graph Transformation, Vol. II: Applications, Languages, and Tools, World Scientific, Singapore, 1999.
• [21] Engels, G., Heckel, R.: Graph Transformation as a Conceptual and Formal Framework for System Modelling and Evolution, Automata, Languages, and Programming (ICALP 2000 Proc.) (U. Montanari, J. Rolim, E. Welz, Eds.), number 1853 in Lecture Notes in Computer Science, Springer, 2000.
• [22] Ermel, C., Rudolf, M., Taentzer, G.: The AGG Approach: Language and Environment, in: Engels et al. [20], chapter 14, 551-603.
• [23] Fradet, P., Le Métayer, D.: Structured Gamma, Science of Computer Programming, 31(2/3), 1998, 263-289.
• [24] Guttag, J. V., Horning, J. J.: The Algebraic Specification of Abstract Data Types, Acta Informatica, 10, 1978, 27-51.
• [25] Habel, A.: Hyperedge Replacement: Grammars and Languages, Number 643 in Lecture Notes in Computer Science, Springer, 1992.
• [26] Habel, A., Müller, J., Plump, D.: Double-Pushout Graph Transformation Revisited, Mathematical Structures in Computer Science, 11(5), 2001, 637-688.
• [27] Harary, F.: Graph Theory, Addison-Wesley, Reading, MA, 1969.
• [28] Heckel, R., Engels, G., Ehrig, H., Taentzer, G.: Classification and Comparison of Module Concepts for Graph Transformation Systems, in: Engels et al. [20], chapter 17, 669-689.
• [29] Hoffmann, B.: From Graph Transformation to Rule-Based Programming with Diagrams, Int’l Workshop on Applications of Graph Transformations with Industrial Relevance (AGTIVE’99), Selected Papers (M. Nagl, A. Schürr, M. Münch, Eds.), number 1779 in Lecture Notes in Computer Science, Springer, 2000.
• [30] Hoffmann, B.: Shapely Hierarchical Graph Transformation, Proc. IEEE Symposia on Human-Centric Computing Languages and Environments, IEEE Computer Press, 2001.
• [31] Hoffmann, B.: Abstraction and Control for Shapely Nested Graph Transformation, 1st Int’l Conference on Graph Transformation (ICGT’02) (A. Corradini, H. Ehrig, H.-J. Kreowski, G. Rozenberg, Eds.), number 2505 in Lecture Notes in Computer Science, Springer, 2002.
• [32] Hoffmann, B., Minas, M.: A Generic Model for Diagram Syntax and Semantics, ICALP Workshops 2000 (J. D. P. Rolim, et al., Eds.), number 8 in Proceedings in Informatics, Carleton Scientific, Waterloo, Ontario, Canada, 2000.
• [33] Hoffmann, B., Minas,M.: Towards Rule-Based Visual Programming of Generic Visual Systems, Proc. Workshop on Rule-Based Languages (N. Dershowitz, C. Kirchner, Eds.), Montréal, Quebeq, Canada, September 2000.
• [34] Huet, G.: Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems, Journal of the ACM, 27(4), 1980, 797-821.
• [35] Klarlund, N., Schwartzbach, M. I.: Graph Types, Proc. Principles of Programming Languages, ACM Press, New York, 1993.
• [36] Klop, J. W.: Term Rewriting Systems, in: Handbook of Logic in Computer Science (S. Abramsky, D. M. Gabbay, T. Maibaum, Eds.), vol. 2, Oxford University Press, 1992, 1-116.
• [37] Koster, C. H. A.: Using the CDL Compiler Compiler, Compiler Construction—An Advanced Course (F. Bauer, J. Eickel, Eds.), number 21 in Lecture Notes in Computer Science, Springer, 1976.
• [38] Kreowski, H.-J., Kuske, S.: Graph Transformation Units and Modules, in: Ehrig et al. [20], chapter 15, 607-638.
• [39] Kuske, S.: More about control conditions for transformation units, Theory and Application of Graph Transformation (TAGT’98), Selected Papers (H. Ehrig, G. Engels, H.-J. Kreowski, G. Rozenberg, Eds.), number 1764 in Lecture Notes in Computer Science, Springer, 2000.
• [40] Kuske, S.: Transformation Units - A Structuring Principle for Graph Transformation Systems, Dissertation, Universität Bremen, Fachbereich Mathematik u. Informatik, 2000.
• [41] Minas, M.: Concepts and Realization of a Diagram Editor Generator Based on Hypergraph Transformation, Science of Computer Programming, 44(2), 2002, 157-180.
• [42] Peyton Jones, S., et al.: Haskell 98 Language and Library: The Revised Report, December 2002, Available via http://haskell.org_.
• [43] Plump, D.: Hypergraph Rewriting: Critical Pairs and Undecidability of Confluence, in: Term Graph Rewriting, Theory and Practice (M. R. Sleep, R. Plasmeijer, M. v. Eekelen, Eds.), Wiley & Sons, Chichester, 1993, 201-213.
• [44] Plump, D.: Computing by Graph Rewriting, Habilitationsschrift, Universität Bremen, 1999.
• [45] Plump, D.: Term Graph Rewriting, in: Engels et al. [20], chapter 1, 3-102.
• [46] Plump, D., Habel, A.: Graph Unification and Matching, in: Cuny et al. [12], 75-89.
• [47] Robinson, J. A.: Logic: Form and Function, Elsevier North Holland, 1979.
• [48] Rozenberg, G., Ed.: Handbook of Graph Grammars and Computing by Graph Transformation, Vol. I: Foundations, World Scientific, Singapore, 1997.
• [49] Rumbaugh, J., Jacobson, I., Booch, G.: The Unified Modeling Language Reference Manual, Object Technology Series, AddisonWesley, 1999.
• [50] Sagiv, M., Reps, T., Wilhelm, R.: Solving Shape-Analysis Problems in Languages with Destructive Updating, ACM Transactions on Programming Languages and Systems, 20(1), 1998, 1-50.
• [51] Schürr, A., Winter, A., Zündorf, A.: The PROGRES Approach: Language and Environment, in: Engels et al. [20], chapter 13, 487-550.
• [52] Smolka, G., Henz, M., Würtz, J.: Object-Oriented Concurrent Constraint Programming in Oz, in: Principles and Practice of Constraint Programming (P. van Hentenryck, V. Saraswat, Eds.), chapter 2, The MIT Press, 1995, 29-48.
• [53] Uesu, T.: A System of Graph Grammars which Generates all Recursively Enumerable Sets of Labelled Graphs, Tsukuba J. Math., 2, 1978, 11-26.
• [54] Wagner, A., Gogolla, M.: Semantics of Object-Oriented Languages, in: Engels et al. [20], chapter 4, 181-211.