computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...

, double pushout graph rewriting (or DPO graph rewriting) refers to a mathematical framework for

graph rewriting In computer science, graph transformation, or graph rewriting, concerns the technique of creating a new graph out of an original graph algorithmically. It has numerous applications, ranging from software engineering (software construction and also ...

. It was introduced as one of the first algebraic approaches to graph rewriting in the article "Graph-grammars: An algebraic approach" (1973). It has since been generalized to allow rewriting structures which are not graphs, and to handle negative application conditions, among other extensions.

Definition

A DPO graph transformation system (or

graph grammar In computer science, graph transformation, or graph rewriting, concerns the technique of creating a new graph out of an original graph algorithmically. It has numerous applications, ranging from software engineering (software construction and also ...

) consists of a finite

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...

, which is the starting state, and a finite or countable set of labeled spans in the

category Category, plural categories, may refer to: Philosophy and general uses * Categorization, categories in cognitive science, information science and generally *Category of being * ''Categories'' (Aristotle) *Category (Kant) *Categories (Peirce) * ...

of finite graphs and graph homomorphisms, which serve as derivation rules. The rule spans are generally taken to be composed of

monomorphism In the context of abstract algebra or universal algebra, a monomorphism is an injective homomorphism. A monomorphism from to is often denoted with the notation X\hookrightarrow Y. In the more general setting of category theory, a monomorphism ...

s, but the details can vary."Double-pushout graph transformation revisited", Habel, Annegret and Müller, Jürgen and Plump, Detlef, Mathematical Structures in Computer Science, vol. 11, no. 05., pp. 637--688, 2001, Cambridge University Press Rewriting is performed in two steps: deletion and addition. After a match from the left hand side to

G

is fixed, nodes and edges that are not in the right hand side are deleted. The right hand side is then glued in. Gluing graphs is in fact a

pushout A ''pushout'' is a student who leaves their school before graduation, through the encouragement of the school. A student who leaves of their own accord (e.g., to work or care for a child), rather than through the action of the school, is consider ...

construction in the

of graphs, and the deletion is the same as finding a pushout complement, hence the name.

Uses

Double pushout graph rewriting allows the specification of graph transformations by specifying a pattern of fixed size and composition to be found and replaced, where part of the pattern can be preserved. The application of a rule is potentially non-deterministic: several distinct matches can be possible. These can be non-overlapping, or share only preserved items, thus showing a kind of concurrency known as parallel independence,"Concurrent computing: from Petri nets to graph grammars", Corradini, Andrea, ENTCS, vol. 2, pp. 56--70, 1995, Elsevier or they may be incompatible, in which case either the applications can sometimes be executed sequentially, or one can even preclude the other. It can be used as a language for software design and programming (usually a variant working on richer structures than graphs is chosen).

Termination Termination may refer to: Science *Termination (geomorphology), the period of time of relatively rapid change from cold, glacial conditions to warm interglacial condition *Termination factor, in genetics, part of the process of transcribing RNA ...

for DPO graph rewriting is undecidable because the

Post correspondence problem The Post correspondence problem is an undecidable decision problem that was introduced by Emil Post in 1946. Because it is simpler than the halting problem and the ''Entscheidungsproblem'' it is often used in proofs of undecidability. Definiti ...

can be reduced to it., "Termination of graph rewriting is undecidable", Detlef Plump, Fundamenta Informaticae, vol. 33, no. 2, pp. 201--209, 1998, IOS Press DPO graph rewriting can be viewed as a generalization of

Petri nets A Petri net, also known as a place/transition (PT) net, is one of several mathematical modeling languages for the description of distributed systems. It is a class of discrete event dynamic system. A Petri net is a directed bipartite graph that ...

Generalization

Axioms have been sought to describe categories in which DPO rewriting will work. One possibility is the notion of an

adhesive category In mathematics, an adhesive category is a category where pushouts of monomorphisms exist and work more or less as they do in the category of sets. An example of an adhesive category is the category of directed multigraphs, or quivers, and the the ...

, which also enjoys many closure properties. Related notions are HLR systems, quasi-adhesive categories and

\mathcal{M}

-adhesive categories, adhesive HLR categories.Hartmut Ehrig and Annegret Habel and Julia Padberg and Ulrike Prange, "Adhesive high-level replacement categories and systems", 2004, Springer The concepts of

and HLR system are related (an adhesive category with

coproduct In category theory, the coproduct, or categorical sum, is a construction which includes as examples the disjoint union of sets and of topological spaces, the free product of groups, and the direct sum of modules and vector spaces. The coprodu ...

s is a HLR system"Adhesive categories", Stephen Lack and Paweł Sobociński, in ''Foundations of software science and computation structures'', pp. 273--288, Springer 2004).

Hypergraph In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices. Formally, an undirected hypergraph H is a pair H = (X,E) wh ...

typed graph Typing is the process of writing or inputting text by pressing keys on a typewriter, computer keyboard, mobile phone or calculator. It can be distinguished from other means of text input, such as handwriting and speech recognition. Text can b ...

and

attributed graph In computer science, an attributed graph grammar is a class of graph grammar that associates vertices with a set of attributes and rewrites with functions on attributes. In the algebraic approach to graph grammars, they are usually formulated using ...

rewriting,"Fundamentals of Algebraic Graph Transformation", Hartmut Ehrig, Karsten Ehrig, Ulrike Prange and Gabriele Taentzer for example, can be handled because they can be cast as adhesive HLR systems.

Notes

Graph algorithms Graph rewriting