Computing by Graph Transformation - COM00005H

« Back to module search

  • Department: Computer Science
  • Module co-ordinator: Dr. Detlef Plump
  • Credit value: 20 credits
  • Credit level: H
  • Academic year of delivery: 2016-17

Related modules

Co-requisite modules

  • None

Prohibited combinations

  • None

Module occurrences

Occurrence Teaching cycle
A Autumn Term 2016-17 to Spring Term 2016-17

Module aims

The aims of this module are:

  • To introduce the foundations of computing by graph transformation
  • To introduce the principles of rule-based programming in domains of graph-like structures

Background:
Graphs are ubiquitous in computer science, they represent and visualise relationships between objects of all kinds. Examples include circuit diagrams, flow diagrams, syntax trees, pointer structures, entity-relationship diagrams, UML diagrams, various forms of networks, etc. Graph transformation is about the dynamic manipulation of graphs by rules, combining the strengths of graphs and rules into a single computational model. Transformation rules which change graphs locally allow a declarative way of computing, with simple syntax and semantics. This course introduces the foundations of computing by graph transformation, and the principles of rule-based programming in domains of graph-like structures.

Contents:
Why graph transformation? Application areas. Graphs, rules and derivations. Mathematical foundations: category theory. Graph transformation systems, graph grammars and graph languages. The power of graph transformation. Properties of derivations: reversing, restricting and extending derivations. Sequential and parallel independence of direct derivations. Confluence and termination. Testing for local confluence: critical pairs. Undecidability of confluence. Graph programs: conditional rule schemata and example programs. A case study in graph programming: automata minimization. Semantics of graph programs. The GP programming system. Graph conditions and verification of graph programs.

Module learning outcomes

As a result of studying this module students should: (1) be familiar with the main concepts and results of graph transformation; (2) be able to recognise problems in various areas of computer science as suitable for applying graph transformation; (3) be able to write graph programs for solving problems in graph-like domains and reason about program correctness and complexity.

Assessment

Task Length % of module mark
University - closed examination
Computing by Graph Transformation (GRAT) - Exam 1
1.5 hours 50
University - closed examination
Computing by Graph Transformation (GRAT) - Exam 2
1.5 hours 50

Special assessment rules

None

Reassessment

Task Length % of module mark
University - closed examination
Computing by Graph Transformation (GRAT) - Exam 1
1.5 hours 50
University - closed examination
Computing by Graph Transformation (GRAT) - Exam 2
1.5 hours 50

Module feedback

Problem classes and practicals are devised to give continuous feedback.
The exams will result in generic class feedback, which can be used by failing students to better understand how to answer the resit paper.
Students will have supervised access to exam scripts.

Key texts

*** H. Ehrig, K.Ehrig, U. Prange and G. Taentzer, Fundamentals of Algebraic Graph Transformation, Springer, 2006

* H. Ehrig, C. Ermel, U. Golas and F. Hermann, Graph and Model Transformation, Springer, 2015

++ G. Rozenberg (ed.), Handbook of Graph Grammars and Computing by Graph Transformation. Volume 1: Foundations, World Scientific, 1997

++ H. Ehrig, G. Engels, H.-J. Kreowski and G. Rozenberg (eds.), Handbook of Graph Grammars and Computing by Graph Transformation. Volume 2: Applications, Languages and Tools, World Scientific, 1999

+ H. Ehrig, H.-J. Kreowski, U. Montanari and G. Rozenberg (eds.), Handbook of Graph Grammars and Computing by Graph Transformation. Volume 3: Concurrency, Parallelism and Distribution, World Scientific, 1999



The information on this page is indicative of the module that is currently on offer. The University is constantly exploring ways to enhance and improve its degree programmes and therefore reserves the right to make variations to the content and method of delivery of modules, and to discontinue modules, if such action is reasonably considered to be necessary by the University. Where appropriate, the University will notify and consult with affected students in advance about any changes that are required in line with the University's policy on Approval of Modifications to Existing Taught Programmes of Study.