Graph Transformation with Time

• Autorzy: Gyapay S. , Varró D. , Heckel R.
• Języki publikacji: EN

Abstrakty

EN

Following TER nets, an approach to the modeling of time in high-level Petri nets, we propose a model of time within (attributed) graph transformation systems where logical clocks are represented as distinguished node attributes. Corresponding axioms for the time model in TER nets are generalized to graph transformation systems and semantic variations are discussed. They are summarized by a general theorem ensuring the consistency of temporal order and casual dependencies. The resulting notions of typed graph transformation with time specialize the algebraic double-pushout (DPO) approach to typed graph transformation. In particular, the concurrency theory of the DPO approach can be used in the transfer of the basic theory of TER nets.

Słowa kluczowe

EN

graph transformation; time; concurrency

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

Twórcy

autor

Gyapay S.

• Dept. of Measurement and Information Systems, Budapest University of Technology and Economics, H-1521 Budapest, Hungary

autor

Varró D.

• Dept. of Measurement and Information Systems, Budapest University of Technology and Economics, H-1521 Budapest, Hungary

autor

Heckel R.

• Faculty of Computer Science, Electrical Engineering, and Mathematics, University of Paderborn, D-33095 Paderborn, Germany

Bibliografia

• [1] Baldan, P.: Modelling Concurrent Computations: from Contextual Petri Nets to Graph Grammars, Ph.D. Thesis, Dipartimento di Informatica, Università di Pisa, 2000.
• [2] Baldan, P., Corradini, A., Ehrig, H., Löwe, M., Montanari, U., Rossi, F.: Concurrent Semantics of Algebraic Graph Transformation, in: Handbook of Graph Grammars and Computing by Graph Transformation, Volume 3: Concurrency and Distribution (H. Ehrig, H.-J. Kreowski, U. Montanari, G. Rozenberg, Eds.), World Scientific, 1999, 107-188.
• [3] Baresi, L., Pezzé, M., Taentzer, G., Eds.: Proc. ICALP 2001 Workshop on Graph Transformation and Visual Modeling Techniques, Heraklion, Greece, Electronic Notes in TCS, Elsevier Science, July 2001.
• [4] Corradini, A., Heckel, R., Eds.: Proc. ICALP 2000 Workshop on Graph Transformation and Visual Modeling Techniques, Carleton Scientific, Geneva, Switzerland, July 2000.
• [5] Corradini, A., Montanari, U.: Specification of Concurrent Systems: from Petri Nets to Graph Grammars, Quality of Communication-Based Systems, Kluwer Academic Publishers, 1995.
• [6] Corradini, A., Montanari, U., Rossi, F.: Graph processes, Fundamenta Informaticae, 26(3,4), 1996, 241-266.
• [7] Ehrig, H., Padberg, J., Ribeiro, L.: Algebraic high-level nets: Petri nets revisited, Recent Trends in Data Type Specification, Springer-Verlag, Caldes de Malavella, Spain, 1994, Lecture Notes in Computer Science 785.
• [8] Ehrig, H., Pfender, M., Schneider, H.: Graph grammars: an algebraic approach, 14th Annual IEEE Symposium on Switching and Automata Theory, IEEE, 1973.
• [9] Engels, G., Hausmann, J., Heckel, R., Sauer, S.: Dynamic Meta Modeling: A Graphical Approach to the Operational Semantics of Behavioral Diagrams in UML, Proc. UML 2000, York, UK (A. Evans, S. Kent, B. Selic, Eds.), 1939, Springer-Verlag, 2000.
• [10] Ghezzi, C., Mandrioli, D., Morasca, S., Pezzè: A Unified High-Level Petri Net Formalism for Time-Critical Systems, IEEE Transactions on Software Engineering, 17(2), 1991, 160-172.
• [11] Gyapay, S., Heckel, R.: Towards Graph Transformation with Time, Proc. ETAPS 2002 Workshop on Application of Graph Transformation, Grenoble, France (H.-J. Kreowski, Ed.), April 2002.
• [12] Gyapay, S., Heckel, R., Varro, D.: Graph Transformation with Time: Causality and Logical Clocks, Proc. 1st Int. Conference on Graph Transformation (ICGT 02), Barcelona, Spain (A. Corradini, H. Ehrig, H.-J. Kreowski, G. Rozenberg, Eds.), 2505, Springer-Verlag, October 2002.
• [13] Hausmann, J., Heckel, R., Sauer, S.: Towards Dynamic Meta Modeling of UML Extensions: An Extensible Semantics for UML Sequence Diagrams, Symposium on Visual Languages and Formal Methods, IEEE Symposia on Human Computer Interaction (HCI 2001), Stresa, Italy (M. Minas, A. Schürr, Eds.), IEEE Computer Society Press, Los Alamitos, CA, September 2001.
• [14] Kreowski, H.-J.: Manipulation von Graphmanipulationen, Ph.D. Thesis, Technical University of Berlin, Dep. of Comp. Sci., 1977.
• [15] Kuske, S.: A Formal Semantics of UML State Machines Based on Structured Graph Transformation, Proc. UML 2001, Toronto, Kanada (M. Gogolla, C. Kobryn, Eds.), 2185, Springer-Verlag, 2001.
• [16] Lamport, L.: Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, 21(7), July 1978.
• [17] Löwe, M., Korff, M., Wagner, A.: An Algebraic Framework for the Transformation of Attributed Graphs, in: Term Graph Rewriting: Theory and Practice (M. R. Sleep, M. J. Plasmeijer, M. van Eekelen, Eds.), chapter 14, John Wiley & Sons Ltd, 1993, 185-199.
• [18] Ribeiro, L.: Parallel Composition and Unfolding Semantics of Graph Grammars, Ph.D. Thesis, TU Berlin, 1996.