GP (for Graph Programs) is a rulebased, nondeterministic programming language for solving graph problems at a high level of abstraction, freeing programmers from handling lowlevel data structures. The core of GP consists of four constructs: singlestep application of a set of conditional graphtransformation rules, sequential composition, branching and iteration. The language has a structural operational semantics, as well as a prototype implementation.
Sandra Steinert, Greg Manning, and Detlef Plump worked on the design and implementation of GP1; Chris Bak and Detlef Plump are currently working on the design and implementation of GP2. Chris Poskitt and Detlef Plump are currently investigating the verification of Graph Programs.
GP Literature
Overviews
 Detlef Plump. The Design of GP 2 (.pdf). In Proc. International Workshop on Reduction Strategies in Rewriting and Programming (WRS 2011), volume 82 of Electronic Proceedings in Theoretical Computer Science, pages 116, 2012.
 Description of GP2, the newest version of GP. The publications below describe the previous version of GP, now known as GP1.
 Detlef Plump. The Graph Programming Language GP (.pdf). In Proc. Algebraic Informatics, Third International Conference (CAI 2009), volume 5725 of Lecture Notes in Computer Science, pages 99122. SpringerVerlag, 2009.
Semantics
 Detlef Plump and Sandra Steinert. The Semantics of Graph Programs (.pdf). In Proc. RuleBased Programming (RULE 2009), Electronic Proceedings in Theoretical Computer Science, 2009.
Verification
 Christopher M. Poskitt and Detlef Plump. A Hoare Calculus for Graph Programs (.pdf). In Proc. International Conference on Graph Transformation (ICGT 2010), volume 6372 of Lecture Notes in Computer Science, pages 139154. SpringerVerlag, 2010.
Case Studies
Prototype Implementation
 Greg Manning and Detlef Plump. The GP Programming System (.pdf). In Proc. Graph Transformation and Visual Modelling Techniques (GTVMT 2008), volume 10 of Electronic Communications of the EASST, 2008.
 Greg Manning and Detlef Plump. The York Abstract Machine (.pdf). In Proc. Graph Transformation and Visual Modelling Techniques (GTVMT 2006), volume 211 of Electronic Notes in Theoretical Computer Science, pages 231240. Elsevier, 2008.
Possible GP Research Projects
Please contact Detlef Plump for more information about the following possible Ph.D. projects.
 Speeding up GP. This project will attempt to speed up GP's current implementation, which is based on a compiler and the York abstract machine, to rival with the fastest graph transformation tools currently available. Activities to make GP faster include the introduction of a powerful type system for graphs to support the analysis of graphs at run time, the implementation of dynamic search plans for graph pattern matching, and the use of socalled rooted graph transformation rules which can be matched in constant time.
 Static analysis of graph programs. This project will develop an automatic program analysis for detecting confluence and termination in graph programs. A nondeterministic program is confluent (or 'don't care' nondeterministic) if all its executions on a given input will produce the same result. Confluence is essential for run time efficiency because GP's backtracking mechanism can be turned off for confluent subprograms without compromising the semantics. Sufficient conditions for confluence will be developed by generalizing socalled critical pair techniques from sets of graph transformation rules to programs. A simple static analysis of termination will complement the analysis of confluence.
More information about these possible projects (and others) are available on our prospective research students page.

Simple_Dijkstra: a graph program implementation of Dijkstra's singlesource shortestpath algorithm.
CheckForest: a graph program for testing whether a provided input graph is a forest or not.
