GP (Graph Programs)

GP (for Graph Programs) is a rule-based, nondeterministic programming language for solving graph problems at a high level of abstraction, freeing programmers from handling low-level data structures. The core of GP consists of four constructs: single-step application of a set of conditional graph-transformation 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 1-16, 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 99-122. Springer-Verlag, 2009. Sandra Steinert. The Graph Programming Language GP (.pdf). PhD thesis, The University of York, 2007. Semantics Detlef Plump and Sandra Steinert. The Semantics of Graph Programs (.pdf). In Proc. Rule-Based Programming (RULE 2009), Electronic Proceedings in Theoretical Computer Science, 2009. Translations Detlef Plump. From Imperative to Rule-based Graph Programs (Extended Abstract) (.pdf). In Proc. Nordic Workshop on Programming Theory (NWPT 2014), to appear. Verification and Static Analyses Ivaylo Hristakiev and Detlef Plump. A Unification Algorithm for GP (.pdf). In Proc. Graph Computation Models (GCM 2014). 2014. Christopher M. Poskitt and Detlef Plump. Verifying Monadic Second-Order Properties of Graph Programs (.pdf). In Proc. International Conference on Graph Transformation (ICGT 2014), volume 8571 of LNCS, pages 33-48. Springer, 2014. Christopher M. Poskitt. Verification of Graph Programs. PhD thesis, University of York, 2013. Christopher M. Poskitt and Detlef Plump. Verifying Total Correctness of Graph Programs (.pdf). In Revised Selected Papers, Graph Computation Models (GCM 2012). Electronic Communications of the ECEASST 61, 2013. Christopher M. Poskitt and Detlef Plump. Hoare-Style Verification of Graph Programs (.pdf). Fundamenta Informaticae 118 (1-2), pages 135-175. IOS Press, 2012. 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 139-154. Springer-Verlag, 2010. Case Studies Detlef Plump, Robin Suri, and Ambuj Singh. Minimizing Finite Automata with Graph Programs (.pdf). In Graph Computation Models (GCM 2010), Revised Selected Papers, volume 39 of Electronic Communications of the EASST, 2011. Implementation Christopher Bak and Detlef Plump. Rooted graph programs. In Proc. International Workshop on Graph Based Tools (GraBaTs 2012), volume 54 of Electronic Communications of the EASST, 2012. Greg Manning and Detlef Plump. The GP Programming System (.pdf). In Proc. Graph Transformation and Visual Modelling Techniques (GT-VMT 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 (GT-VMT 2006), volume 211 of Electronic Notes in Theoretical Computer Science, pages 231-240. 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 so-called 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 so-called 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 single-source shortest-path algorithm. CheckForest: a graph program for testing whether a provided input graph is a forest or not.