World Library  
Flag as Inappropriate
Email this Article

Double pushout graph rewriting

Article Id: WHEBN0035717039
Reproduction Date:

Title: Double pushout graph rewriting  
Author: World Heritage Encyclopedia
Language: English
Subject: Graph Theory
Publisher: World Heritage Encyclopedia

Double pushout graph rewriting

In computer science, double pushout graph rewriting or (DPO graph rewriting) refers to a mathematical framework for graph rewriting. It was introduced in as one of the first algebraic approaches to graph rewriting in the article "Graph-grammars: An algebraic approach" (1973).[1] It has since been generalized to allow rewriting structures which are not graphs, and to handle negative application conditions,[2] among other extensions.


A DPO graph transformation system (or graph grammar) consists of a finite graph, which is the starting state, and an a finite or countable set of labeled spans in the category of finite graphs and graph homomorphisms, which serve as derivation rules. The rule spans are generally taken to be composed of monomorphisms, but the details can vary.[3]

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 construction in the category of graphs, and the deletion is the same as finding a pushout complement, hence the name.


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,[4] 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 for DPO graph rewriting is undecidable because the Post correspondence problem can be reduced to it.[5]

DPO graph rewriting can be viewed as a generalization of Petri nets.[4]


Axioms have been sought to describe categories in which DPO rewriting will work. One possibility is the notion of an adhesive category, which also enjoys many closure properties. Related notions are HLR systems, quasi-adhesive categories and \mathcal{M}-adhesive categories, adhesive HLR categories.[6]

The concepts of adhesive category and HLR system are related (an adhesive category with coproducts is a HLR system[7]).

Hypergraph, typed graph and attributed graph rewriting,[8] for example, can be handled because they can be cast as adhesive HLR systems.


  1. ^ "Graph-grammars: An algebraic approach", Ehrig, Hartmut and Pfender, Michael and Schneider, Hans-Jürgen, Switching and Automata Theory, 1973. SWAT'08. IEEE Conference Record of 14th Annual Symposium on, pp. 167-180, 1973, IEEE
  2. ^ "Constraints and application conditions: From graphs to high-level structures", Ehrig, Ehrig, Habel and Pennemann, Graph transformations, pp. 287--303, Springer
  3. ^ "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
  4. ^ a b "Concurrent computing: from Petri nets to graph grammars", Corradini, Andrea, ENTCS, vol. 2, pp. 56--70, 1995, Elsevier
  5. ^ , "Termination of graph rewriting is undecidable", Detlef Plump, Fundamenta Informaticae, vol. 33, no. 2, pp. 201--209, 1998, IOS Press
  6. ^ Hartmut Ehrig and Annegret Habel and Julia Padberg and Ulrike Prange, "Adhesive high-level replacement categories and systems", 2004, Springer
  7. ^ "Adhesive categories", Stephen Lack and Paweł Sobociński, in Foundations of software science and computation structures, pp. 273--288, Springer 2004
  8. ^ "Fundamentals of Algebraic Graph Transformation", Hartmut Ehrig, Karsten Ehrig, Ulrike Prange and Gabriele Taentzer
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.