up: Publications

Reasoning about transformations of Graph Structures

Jon-Hael Brenas, Mohamed Chaabani, Rachid Echahed, Martin Strecker


This is the formalization of a method of graph transformations. Transformations are expressed by an imperative programming language which is non-standard in the sense that it features conditions (in loops and selection statements) that are description logic (DL) formulas, and a non-deterministic assignment statement (a choice operator given by a DL formula). We sketch an operational semantics of the proposed programming language and then develop a matching Hoare calculus whose pre- and post-conditions are again DL formulas. A major difficulty resides in showing that the formulas generated when calculating weakest preconditions remain within the chosen DL fragment. In particular, this concerns substitutions whose result is not directly representable. We therefore explicitly add substitution as a constructor of the logic and show how it can be eliminated by an interleaving with the rules of a traditional tableau calculus.

Online Copy

Last modified: Sat Apr 20 04:47:24 CEST 2013