From The Programming Languages and Systems Research Group


Line 32: 
Line 32: 
 More information about these possible projects (and others) are available on [[Prospective Research Students#Subject_Area:_Programming_by_Graph_Transformation_.28Detlef_Plump_.5B3.5D.29our prospective research students page]].   More information about these possible projects (and others) are available on [[Prospective Research Students#Subject_Area:_Programming_by_Graph_Transformation_.28Detlef_Plump_.5B3.5D.29our prospective research students page]]. 
   
−  valign=top[[Image:ExampleGraphProgramCheckForest.pngthumbborder500px'''CheckForest:''' example graph program for testing whether a graph is a forest.]]  +  valign=top width=500[[Image:ExampleGraphProgramSimple_Dijkstra.pngthumbborder400px'''Simple_Dijkstra:''' graph program implementation of Dijkstra's singlesource shortestpath algorithm.]] 
 +  
 +  [[Image:ExampleGraphProgramCheckForest.pngthumbborder400px'''CheckForest:''' example graph program for testing whether a graph is a forest.]] 
 }   } 
   
 [[Category:Graph Transformation]]   [[Category:Graph Transformation]] 
Revision as of 19:48, 2 March 2010
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 GP; Chris Poskitt and Detlef Plump are currently investigating the formal verification of Graph Programs.
GP Literature
Overviews
 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. To appear.
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 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: graph program implementation of Dijkstra's singlesource shortestpath algorithm.
CheckForest: example graph program for testing whether a graph is a forest.
