In a node-replacement graph grammar, a node of a given graph is replaced by a new subgraph, which is connected to the remainder of the graph by new edges, depending on how the node was connected to it. These node replacements are controlled by the productions (or replacement rules) of the grammar. Here mainly the "context-free" (or "confluent") node-replacement graph grammars are considered, in which the result of the replacements does not depend on the order in which they are applied. Although many types of such grammars can be found in the literature, the emphasis will be one of them: the C-edNCE grammar. Basic notions are discussed that faciliate the construction and analysis of these grammars. Properties of the class of generated graph languages, such as closure properties, structural properties, and decidability Properties, are considered. A number of quite different characterizations of the class are presented, thus showing its robustness. This robustness of the class of C-edNCE graph languages, together with the fact that it is one of the largest classes of "context-free" graph languages, motivates the choice of the C-edNCE grammar to be central in this chapter.

Here the concept of hyperedge replacement is presented as an elementary approach to graph and hypergraph generation. In particular, hyperedge replacement graph grammars are discussed as a (hyper)graph-grammatical counterpart to context-free string grammars. To cover a large part of the theory of hyperedge replacement, structural properties and decision problems, including the membership problem, are addressed.

The algebraic approaches to graph transformation are based on the concept of gluing of graphs, modelled by pushouts in suitable categories of graphs and graph morphisms. This allows one not only to give an explicit algebraic or set theoretical description of the constructions, but also to use concepts and results from category theory in order to build up a rich theory and to give elegant proofs even in complex situations. We start with an overview of the basic notions common to the two algebraic approaches, the double-pushout (DPO) approach and the single-pushout (SPO) approach; next we present the classical theory and some recent development of the double-pushout approach.

Various forms of programmed graph replacement systems as extensions of context-sensitive graph replacement systems have been proposed until today. They differ considerably with respect to their underlying graph models, the supported forms of graph replacement rules, and offered rule regulation mechanisms. Some of them have additional constructs for the definition of graph schemata, derived graph properties, and so forth. It is rather difficult to develop precise and compact descriptions of programmed graph replacement systems, a necessary prerequisite for any attempt to compare their properties in detail. Programmed Logic-based Structure Replacement (PLSR) systems are a kind of intermediate defintion language for this purpose. They treat specific graph classes as sets of predicate logic formulas with certain properties, so-called structures. Their rules preserve the consistency of manipulated structures and use nonmonotonic reasoning for checking needed pre-and postconditions. So-called Basic Control Flow (BCF) expressions together with an underlying fixpoint theory provide needed means for programming with rules. We introduce first the basic framework of PLSR systems and study afterwards the essential properties of context-sensitive graph replacement approaches themselves as well as popular rule regulation mechanisms.

We introduce the notions of transformation units and transformation modules as means of constructing large graph transformation systems from small ones in a structured and systematic way. A transformation unit comprises a set of rules, descriptions of initial and terminal graphs, and a control condition. Moreover, it may use other transformation units for structuring purposes. Its semantics is a binary relation between intial and terminal graphs which is given by interleaving ordinary direct derivation steps with calls of imported transformation units. Putting transformation units together yields transformation modules. A module may have an import interface consisting of formal parameter units and an export interface consisting of the units that are made available to the environment. The formal parameter units can be instantiated by exported units of other modules. The introduced framework is independent of a particular graph transformation approach and, therefore, it may enhance the usefulness of graph transformations in many contexts.

The idea of a combined reference model- and view-based specification approach has been proposed recently in the software engineering community. We present a specification technique based on open graph transformation systems which supports such a development approach.
Open graph transformation systems extend graph transformation systems (in the double-pushout approach) by a new loose semantics for rule-based systems, which allows to model the interaction between different views, and by explicit frame conditions which restrict these interactions to an interface of open types. On this background, formal notions of view and view relation are developed and the behaviour of views is described by the loose semantics. Based on the assumption that dependencies between different views are faithfully described by a common reference model, a construction is developed for the automatic integration of views. The views and the refernece model are kept consistent manually, which is the task of a model manager. All concepts and results are illustrated at the well-known exmaple of a banking system.

Graph relabelling systems have been introduced as a suitable model for expressing and studying distributed algorithms on a network of communicating processors. We recall the basic ideas underlying that model and we present the main questions that have been considered and the main results that have been obtained in that framework.

Distributed systems demand a number of requirements on specification techniques which do not have to be taken into account for the development of non-distributed software. Allocation of objects and tasks, object replication and migration, remote interactions, multiple threads of control as well as dynamic network topologies are important issues in distributed systems. Some of these distribution issues are already handled by common modeling techniques mostly based on graphical notations, but altogether distributed systems cannot be designed sufficiently with these techniques satisfying all the requirements. We present new concepts for visual design of distributed systems which are based on distributed graph transformation as underlying formal specification technique. The kernel of this technique focuses on a structured graph with two abstraction levels, the network and the local level, and its transformation. On the network level, the (possibly) dynamic topological structure of a distributed system is specified. The local level contains the graphical description of local object and data structures where parts of them may be replicated in remote network nodes. Those structures may evolve independently or synchronized with remote structures using a interaction mechanism based on subactions. Network activities as well as local actions are described rule-based. The advantage of using rules in this context is to avoid purely sequential or serie-parallel control flow, since rules naturally support the design of multiple threads of control on the level of events without prescribing the order of execution. Distributed graph transformation is based on the double-pushout approach to graph transformation. Local graph transformations may be attributed and may use application conditions for rules. Using graph transformation as underlying formal framework, distributed behaviour is designed in a way that consistency of the network as well as of all object and data structures involved is ensured in a way that the result is again a distributed graph. This result is obtained from the formalization of distributed graph transformation as double-pushout in the category of distributed graphs and graph morphisms. For the illustration of the concepts presented we use a reference application modeling distributed version management for any kind of document. This subject becomes the more important the more remote software development becomes popular. In contrast to server-client solutions where all documents are held centrally, the documents are really distributed over the involved sites in our case.

Graphs and graph transformations are natural means to describe systems of processes. Graphs represent structure of the system, and graph rewriting rules model dynamic behaviour. We illustrate the technique by describing Petri nets, statecharts, parallel logic programming, and systems of processes. Whereas description of Petri nets is based on usual graphs, statecharts lead us to hierarchial graphs, and parallel logic programming needs jungles. Finally, we combine different approaches to describe systems of processes. Topological structure is represented by a hypergraph. Local states and communication channels correspond to nodes that are labelled with parts of a global jungle playing the role of a shared data structure. The formal model takes advantage of comma-category approach allowing to change both the structure of graph and the contents of nodes consistently and to treat different graph structures as well as different labelling mechanisms in a uniform way.