• Student home
• Things to know this week
• Student news
• Student events
• New students' welcome
• Studying at York
  • Semesters
  • Teaching hours
  • Enrolment
  • Manage your studies
    • Enrol or re-enrol
    • Your student record
    • Your timetable
    • Change your plan
    • Programmes and modules
      • Programme specifications
      • Studying beyond your department
      • Module catalogue
    • University study spaces
  • Student Visa holders
  • Study skills
  • Assessment and examination
  • Academic progress issues
  • Graduation
• Support and advice
• Health and wellbeing
• Work, volunteering and career planning
• Study and work abroad
• Accommodation
• IT and online services
• Finance
• Student life in York
• If things go wrong
• Student Centre

Computing by Graph Transformation - COM00051H

« Back to module search

• Department: Computer Science
• Module co-ordinator: Dr. Detlef Plump
• Credit value: 20 credits
• Credit level: H
• Academic year of delivery: 2024-25
  • See module specification for other years: 2023-24

Module will run

Occurrence	Teaching period
A	Semester 2 2024-25

Module aims

The module will introduce (1) the foundations of computing by graph transformation, (2) the theory and practice of rule-based graph programming, and (3) the formal verification of graph programs.

Module learning outcomes

1. Apply the main concepts and results of graph transformation.

2. Recognise problems in various areas of computer science as suitable for applying graph transformation.

3. Be able to write efficient graph programs for solving problems in graph-like domains.

4. Know how to reason about program properties such as termination and complexity.

5. Be able to formally verify the correctness of graph programs.

Module content

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.

Assessment

Task	Length	% of module mark
Online Exam -less than 24hrs (Centrally scheduled) Online Exam : Computing by Graph Transformation	3 hours	100

Special assessment rules

None

Reassessment

Task	Length	% of module mark
Online Exam -less than 24hrs (Centrally scheduled) Online Exam : Computing by Graph Transformation	3 hours	100

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.

Indicative reading

*** 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