This special issue of Mathematical Structures in Computer Science is devoted to the theory and applications of graph transformations. This research area dates back to the early seventies and is based on mathematical techniques from graph theory, algebra, logic and category theory. The theory of graph transformations has become attractive as a modelling and programming paradigm for complex graphical structures in a large variety of areas in computer science and for applications to other fields. During the Joint APPLIGRAPH/GETGRATS Workshop on Graph Transformation Systems (GRATRA 2000) – a satellite of ETAPS 2000 in Berlin – 35 lectures were presented by participants from all over the world. The authors of presentations that stressed the theoretical point of view were invited to submit a full version of their presentation to Mathematical Structures in Computer Science. After a careful refereeing process nine papers have been accepted, seven of which are included in this special issue.

The paper by Ehrenfeucht, Petre, Prescott and Rozenberg connects the important new area of DNA computing in vivo to our area of graph transformation. An application of hypergraph constructions to the static analysis of concurrent systems is presented by König, and normal forms for context-free node rewriting hypergraph grammars by Klempien-Hinrichs. The construction of pushout complements for ‘partly total algebras’ generalising attributed graphs is presented by Burmeister, Llabrés and Roselló. Finally, Courcelle and Makowsky present operations on relational structures (generalising different kinds of graphs and hypergraphs) that are compatible with monadic second order logic. Four other accepted papers could not be included in this special issue because of space limitations.

They will appear in regular issues of MSCS:

— R. Heckel, M. Llabrés, H. Ehrig and F. Orejas: Concurrency and loose semantics of open graph transformation systems.

— L. Helouet, C. Jard and B. Caillaud: An event structure based semantics for high-level message sequence charts.

— J. Larossa and G. Valiente: Constraint satisfaction algorithms for graph pattern matching.

— N. Verlinden and D. Janssens: Algebraic properties for Local Action Systems.

We are most grateful to all the referees of these papers, to Olga Runge and Claudia Ermel for technical support, and to Giuseppe Longo and Cambridge University Press for fruitful cooperation in editing this special issue.

Ciliates have developed a unique nuclear dualism, having two nuclei of different functionality: the germline micronucleus and the somatic macronucleus. The way that ciliates assemble the macronuclear genes after cell mating constitutes one of the most intricate DNA processings in living organisms. This processing is also very interesting from the computational point of view. In this paper, we investigate the operations of loop excision and hairpin excision/reinsertion used in the assembly process. In particular, we consider three levels of formalization of this process, culminating in graph reduction systems.

Confluent node-rewriting hypergraph grammars represent the most comprehensive known method for defining sets of hypergraphs in a recursive way. For a large natural subclass of these grammars, we show that the maximal rank of hyperedges indispensable for generating some set of hypergraphs equals the maximal rank of the hyperedges occurring in the hypergraphs of that set. Moreover, if such a grammar generates a set of graphs, one can construct from that grammar a C-edNCE graph grammar generating the same set of graphs.

We define a construction operation on hypergraphs based on a colimit and show that its expressiveness is equal to the graph expressions of Bauderon and Courcelle. We also demonstrate that by closing a set of rewrite rules under graph construction we obtain a notion of rewriting equivalent to the double-pushout approach of Ehrig. The usefulness of our approach for the compositional modelling of concurrent systems is then demonstrated by giving a semantics of process graphs (corresponding to a process calculus with mobility) and of Petri nets. We introduce on the basis if a hypergraph construction, a method for the static analysis of process graphs, related to type systems.

Let Σ be an arbitrary signature and ϒ be a non-empty set of operation symbols within it. A (partial) Σ-algebra is ϒ-total when all its operations in ϒ are total: these are the partly total algebras in the title, and they include total algebras and attributed graphs. In this paper we establish a necessary and sufficient condition on a pair of homomorphisms of ϒ-total Σ-algebras for the existence of a pushout complement of them. This solves the application problem for the double-pushout transformation of these kinds of structure.

Relational structures offer a common framework for handling graphs and hypergraphs of various kinds. Operations like disjoint union, the creation of new relations by means of quantifier-free formulas, and relabellings of relations make it possible to denote them using algebraic expressions. It is known that every monadic second-order property of a structure is verifiable in time proportional to the size of such an algebraic expression defining it. We prove here that this result remains true if we also use in these algebraic expressions a fusion operation that fuses all elements of the domain satisfying some unary predicate. The value mapping from these algebraic expressions to the structures they denote is a monadic second-order definable transduction, which means that the structure is definable inside the tree representing the algebraic expression by monadic second-order formulas. It follows (by using results of other articles) that, with this fusion operation, we cannot generate more graph families, but we can generate them with less unary auxiliary predicates. We also obtain clear-cut characterizations of Vertex Replacement and Hyperedge Replacement context-free graph grammars in terms of four types of operations, amongst which is the fusion of vertices satisfying a specified predicate.