Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-11-23T21:26:08.413Z Has data issue: false hasContentIssue false
  • English
  • Français

Algebraic high-level net transformation systems

Published online by Cambridge University Press:  04 March 2009

Julia Padberg ,
Hartmut Ehrig  and
Leila Ribeiro
Julia Padberg
Affiliation:
Computer Science Department, Technical University Berlin
Hartmut Ehrig
Affiliation:
Computer Science Department, Technical University Berlin
Leila Ribeiro
Affiliation:
Computer Science Department, Technical University Berlin
Get access Rights & Permissions [Opens in a new window]

Abstract

The concept of algebraic high-level net transformation systems combines two important lines of research recently introduced in the literature: algebraic high-level nets (AHL-nets for short) and high-level replacement systems (HLR-systems for short). In both cases a categorical formulation of the corresponding theory has turned out to be highly important and is also a good basis for the integration of these concepts in this paper.

AHL-nets combine Petri nets with algebraic specifications and provide a powerful specification technique for distributed systems including data types and processes.

HLR-systems are transformation systems for high-level structures such as graphs, hypergraphs, algebraic specifications and different kinds of Petri nets. The theory of HLRsystems - formulated already in a categorical framework - is applied in this paper to AHLnets. Thus we obtain AHL-net transformation systems as an instantiation of HLR-systems to AHL-nets. This allows us to build up AHL-nets from basic components and to transform the net structure using rules or productions in the sense of graph grammars. This concept is illustrated by extending the well-known example of ‘dining philosophers’. We are able to show that AHL-net-transformation systems satisfy several important compatibility properties. On the one hand we obtain a local Church-Rosser and Parallelism Theorem, which is well-known for graph grammars and has recently been generalized to HLR-systems. This allows us to analyse concurrency in AHL-nets not only on the token level but also on the level of transformations of the net structure. On the other hand, we consider the ‘fusion’ and ‘union’ constructions for high-level structures, motivated by corresponding concepts for high-level Petri nets in the literature, and we show compatibility of these constructions with derivations of HLR-systems in general and AHL-nettransformations in particular. This means compatibility of vertical and horizontal structuring in terms of software development.

Type
Research Article
Information
Mathematical Structures in Computer Science , Volume 5 , Issue 2 , June 1995 , pp. 217 - 256
Copyright
Copyright © Cambridge University Press 1995

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Adameck, J., Herrlich, H. and Strecker, G. (1990) Abstract and Concrete Categories, Wiley- Interscience.Google Scholar
Astesiano, E. and Reggio, G. (1982) An outline of the SMolCS approach. In: Venturini, Zilli M. (ed.) Math. Models for the Semantics of Parallelism. Proc. Advanced School on Math. Models of Parallelism, Roma, 1986. Springer-Verlag Lecture Notes in Computer Science 380 81–113Google Scholar
Battiston, E., De Cindio, F. and Mauri, G. (1988) OBJSA nets: a class of high-level nets having objects as domains. In: Rozenberg, G. (ed.) Advances in Petri-Nets. Springer-Verlag Lecture Notes in Computer Science 340 20–43CrossRefGoogle Scholar
Burstall, R. M., AND Goguen, J. A. (1980) Semantics of CLEAR, a specification language. In: Björnes, D. (ed.) Abstract Software Specifications, Proc. 1979 Copenhagen Winter School. Springer- Verlag Lecture Notes in Computer Science 86 292–332CrossRefGoogle Scholar
Bergstra, J. A. and Klop, J. W. (1986) Algebra of Communicating Processes; CWI Monographs I series, Proc. of the CWIU Symp. Math, and Comp. Sci., North-Holland, Amsterdam, 89–138Google Scholar
Broy, M. (1985) Specification and top down design of distributed systems. In: Ehrig, H., Floyd, C., Nivat, M. and Thatcher, J. (eds.) Proc. TAPSOFT ‘85, Vol. 1. Springer-Verlag Lecture Notes in Computer Science 185 4–28CrossRefGoogle Scholar
Broy, M. and Streicher, T. (1992) Modular Functional Modelling of Petri Nets with Individual Tokens, Advances in Petri Nets. Springer-Verlag Lecture Notes in Computer Science 609 70–88CrossRefGoogle Scholar
Dimitrovici, C. and Hummert, U. (1991) Composition of algebraic high-level nets, Proc. of the 7th ADT-Workshop (Wusterhausen/Dosse). Springer-Verlag Lecture Notes in Computer Science 534 52–73CrossRefGoogle Scholar
Dimitrovici, C., Hummert, U. and Petrucci, L. (1991) Semantics, Composition and Net Properties of Algebraic High-Level Nets. Springer-Verlag Lecture Notes in Computer Science 524 93–117CrossRefGoogle Scholar
Dijkstra, E. W. (1971) Hierarchical ordering of sequential processes, Operating systems techniques (Perrot Hoare, ed.) Academic Press London, New York.Google Scholar
Ehrig, H. (1979) Introduction to the algebraic theory of graph grammars (A Survey). In: Graph Grammars and Their Application to Computer Science and Biology. Springer-Verlag Lecture Notes in Computer Science 73 1–69CrossRefGoogle Scholar
Ehrig, H., Baldamus, M. and Orejas, F. (1991) New Concepts for Amalgamation and Extension in the Framework of Specification Logics, Proc. of ADT-Workshop Durdan 1991 (Durdan). Springer-Verlag Lecture Notes in Computer Science 655 199–221CrossRefGoogle Scholar
Ehrig, H., Boehm, P., Hummert, U. and Löwe, M. (1988) Distributed Parallelism of Graph Transformations. Proc. Graph Theoretic Concepts in Comp. Sci. (WG ‘87). Springer-Verlag Lecture Notes in Computer Science 314 1–19CrossRefGoogle Scholar
Ehrig, H., Große-Rhode, M. and Heise, A. (1992) Specification Techniques for Concurrent and Distributed Systems, Invited lecture for 2nd Maghrebian Conference on Software Engineering and Artificial Intelligence, Tunis 1992, Techn. Report No. 92–05, TU Berlin, FB 20.Google Scholar
Ehrig, H. and Große-Rhode, (1994) Functorial Theory of Parameterized Specifications in a General Specification Framework. Theoretical Computer Science 135 221–266CrossRefGoogle Scholar
Ehrig, H., Habel, A., Kreowski, H.-J. and Parisi-Presicce, F.(1991) Parallelism and Concurrency in High-Level-Replacement Systems MSCS 1 361–404Google Scholar
Ehrig, H., Kreowski, H.-J. and Taentzer, G. (1992) Canonical Derivations in High-Level-Replacement Systems, Technical Report 6/92, University of Bremen.Google Scholar
Ehrig, H. and Mahr, B. (1985) Fundamentals of Algebraic Specification 1. Equations and Initial Semantics, EATCS Monographs on Theoretical Computer Science, Vol. 6, Springer-Verlag.CrossRefGoogle Scholar
Ehrig, H., Padberg, J. and Ribeiro, L. (1993) Algebraic High-Level nets: Petri nets revisited, Proc. Of the ADT-COMPASS Workshop ‘92 (Caldes de Malavella, Spain); Techn. Report No. 93–6, TU Berlin, FB 20, 1993. (Short version to appear in Springer-Verlag Lecture Notes in Computer Science.)Google Scholar
Ehrig, H. and Parisi-Presicce, F. (1991a) Algebraic Specification Grammars: A Junction Between Module Specifications and Graph Grammars, Proc. 4th Int. Workshop on Graph Grammars and Application to Computer Science, Springer-Verlag Lecture Notes in Computer Science 532 292–310CrossRefGoogle Scholar
Ehrig, H. and Parisi-Presicce, F. (1991b) Nonequivalence of Categories for Equational Algebraic Specifications in View of High-Level Replacement Systems, Techn. Report 91/16, TU Berlin, Dept. of Comp. Sci. (Short version in Proc. 3rd Conf. on Algebraic and Logic Programming, Pisa, 1992.)CrossRefGoogle Scholar
Ehrig, H., Parisi-Presicce, F., Boehm, P., Rickhoff, C., Dimitrovici, C. and Große-Rhode, M. (1987) Algebraic Data Type and Process Specifications based on Projection Spaces. Springer-Verlag Lecture Notes in Computer Science 332 23–13 (Techn. Report No. 87–08, TU Berlin, FB 20, 1987.)CrossRefGoogle Scholar
Ehrig, H., Pfender, M. and Schneider, H. J. (1993) Graph Grammars: An Algebraic Approach, Proc. IEEE Conf. SWATT ‘73, Iowa City, 167–180Google Scholar
Hennessy, M. (1988) Algebraic theory of processes, The MIT Press, Cambridge, Massachusetts.Google Scholar
Higgins, P. J. (1964) Algebras with a Scheme of Operators. Mathematische Nachrichten 27 115–132CrossRefGoogle Scholar
Huber, P., Jensen, K. and Shapiro, R. M. (1991) Hierarquies in coloured Petri nets. In: Jensen and Rozenberg (1991) 215–243Google Scholar
Hummert, U. (1989) Algebraische High-Level Netze, Ph.D. thesis, TU Berlin, Dept. of Comp. Sci.Google Scholar
Jensen, K. (1981) Coloured Petri nets and the invariant-method. Theoretical Computer Science 14 317–336CrossRefGoogle Scholar
Jensen, K. (1992) Coloured Petri Nets. Basic Concepts, analysis methods and practical use, Springer- Verlag.CrossRefGoogle Scholar
Jensen, K. and Rozenberg, G. (eds.) (1991) High-level Petri nets: theory and application, Springer- Verlag.CrossRefGoogle Scholar
Kramer, B. and Schmidt, H. W. (1991) Types and Modules for Net Specifications. In: Jensen and Rozenberg (1991) 171–188Google Scholar
LOTOS (1987) Information processing systems - Open systems interconnection - LOTOS - A Formal Description Technique Based on the Temporal Ordering of Observational Behaviour, ISO DIS 8807 (ISO/TC 97/SC 21 N).Google Scholar
Meseguer, J. and Montanari, U. (1990) Petri nets are monoids. Theoretical Computer Science (2) 105–155Google Scholar
Padberg, J. (1992) Theory of High-Level-Replacement Systems and its Applications to Petri-Nets, Diploma thesis, TU Berlin, FB 20.Google Scholar
Padberg, J. and Taentzer, G. (1993) Embedding of Derivations in High-Level Replacement Systems, Techn. Report No. 93–09, TU Berlin, FB 20.Google Scholar
Parisi-Presicce, F. (1991) Foundations of Rule-Based Design of Modular Systems. Theoretical Computer Science 83 (1).CrossRefGoogle Scholar
Petri, C. A. (1962) Kommunikation mit Automaten, Ph.D. thesis, Schriften des Instituts für Instrumentelle Mathematik, Bonn.Google Scholar
Reisig, W. (1985) Petri nets, Springer-Verlag.CrossRefGoogle Scholar
Reisig, W. (1991) Petri nets and algebraic specifications. Theoretical Computer Science 80 1–34CrossRefGoogle Scholar
Ribeiro, L., Ehrig, H. and Padberg, J. (1993) Formal Development of Concurrent Systems Using Algebraic High-Level Nets and Transformations, Techn. Report No. 93–12, TU Berlin, FB 20. (Short version in Proc 8 Simpzósio Brasileiro de Engenheria de Software, Rio de Janeiro, 1993, 1–16)CrossRefGoogle Scholar
Starke, P. (1990) Analyse von Petri-Netz-Modellen, Teubner Verlag, Stuttgart.CrossRefGoogle Scholar
Taentzer, G. (1992) Parallel High-Level Replacement Systems, Technical Report No. 92–10, TU Berlin, FB 20.Google Scholar
Tarlecki, A., Burstall, R. M. and Goguen, J. A. (1987) Some fundamental algebraic tools for the semantics of computation. Part III: Indexed categories, Techn. Report, University of Edinburgh.Google Scholar
Vautherin, J. (1986) Parallel systems specifications with coloured Petri nets and algebraic abstract data types. In: 7th European Workshop on Applications and Theory of Petri Nets (Oxford, England), 5–23Google Scholar