Christopher Bak

I am a fourth year PhD Research Student in the Department of Computer Science at the University of York, where I am a member of the Programming Languages and Systems Research Group. I have been at The University of York since 2007, graduating in 2011 with an MMath in Mathematics and Computer Science.

Email: chrisbak [at] cs.york.ac.uk.
Office: CSE/214.

Research

A graph is an abstract mathematical structure that represents relationships between a set of objects. They are used to model network-based structures. They have a variety of applications, most notably in software engineering, functional programming evaluation and distributed systems. It is therefore desirable to analyse and manipulate graph-based models. Many tools have been created to support such work.

My research is based on the development of GP, a graph programming language created at York. Users of GP write graph programs, which consist of a set of graph rewriting rules and some control flow constructs to organise the rules. Each graph rewriting rule takes an instance of a pattern graph in the input graph, and replaces that instance with another graph. The objective of GP is to facilitate the manipulation of graph-based structures by exploiting the visual and expressive nature of graphs, enabling graph programs to be written at a high level of abstraction. Graph programs in GP are constructed diagramatically, as opposed to the more common approach of specifying graphs textually in a conventional programming language. GP was designed with simplicity in mind: it has a small syntax and semantics, and it is based on a sound theoretical framework for graph transformation. These features of GP make it a very accessible language; a minimal knowledge of programming is required to write graph programs in GP.

I am implementing a new version of the GP language called GP 2. The primary goal of the project is the generation of code that executes graph programs efficiently. This is challenging from a theoretical point of view because the application of a single graph rewriting rule involves solving an instance of the subgraph isomorphism problem, an algorithm known to be computationally expensive. A new feature of the language, the rooted graph, may be used by GP programmers to drastically reduce the search space for finding an instance of a rule graph in the input graph. In addition, I am using some techniques from the literature to optimise the execution engine of graph programs.

My supervisor is Dr. Detlef Plump. Funding for my project is provided by a studentship from the EPSRC.

Publications

Conference/Workshop Papers

Rooted Graph Programs, Christopher Bak and Detlef Plump. In: Proceedings of the Seventh International Workshop on Graph-Based Tools (GraBaTs 2012). Electronic Communications of the EASST, 2012.

Internal Reports

The Implementation of Graph Programming Systems, Christopher Bak. Qualifying Dissertation, 2012.

Attacking the Grid Colouring Problem with Constraint Programming, Christopher Bak. Masters Dissertation, 2011.

Teaching

I assist in teaching undergraduate Computer Science modules by demonstrating in problem classes and marking formative tests.

Other

I was the seminar organiser for the PLASMA research group in the academic years 2012/13 and 2013/14. I was a member of the program committee for The York Doctoral Symposium in 2012, 2013 and 2014.