In: Ehrig, H.; Kreowski, H.-J.; Montanari, U.; G. Rozenberg: Handbook of Graph Grammars and Computing by Graph Transformation, Vol. III: Concurrency, Parallelism, and Distribution, pages 341-400. September 1999.
Abstract: The general idea of high-level replacement systems is to generalize the concept of graph transformation systems and graph grammars from graphs to all kinds of structures which are of interest in Computer Science and Mathematics. Within the algebraic approach of graph transformation this is possible by replacing graphs, graph morphisms, and pushouts (gluing) of graphs by objects, morphisms, and pushouts in a suitable category. Of special interest are categories for all kinds of labelled and typed graphs, hypergraphs, algebraic specifications and Petri nets. In this chapter, we show how some basic results for graph transformation systems in the algebraic double pushout approach can be reformulated in the framework of high-level replacement systems. The specific choice of results concerning local Church-Rosser properties and horizontal structuring is motivated by the results needed in our application areas studied in this contribution. In order to show the great variety of the high-level replacement approach we do not consider specific graphs and graph transformation but algebraic specifications and Petri nets as application domains, where transformation corresponds to rule-based changes of the structure of specifications and nets, respectively. The first application shows how high-level replacement systems can be instantiated by algebraic specifications. An algebraic transformation rule corresponds to the interface part of an algebraic module specification for software systems. This allows applying high-level replacement techniques to software system design. As an application it is shown how to reuse an algebraic module specification of an airport schedule for the design of a book library. The second main application shows how rule-based modification of Petri nets can be considered as a special case of high-level replacement techniques. An important result is the compatibility of horizontal structuring of nets with rule-based modification. This result is essential within a case study of a medical information system where the functional essence is developed by rule-based modification from the actual state of the system represented by algebraic high-level nets.