The Semantics of Graph Programs

Detlef Plump
(The University of York)
Sandra Steinert
(The University of York)

GP (for Graph Programs) is a rule-based, nondeterministic programming language for solving graph problems at a high level of abstraction, freeing programmers from handling low-level data structures. The core of GP consists of four constructs: single-step application of a set of conditional graph-transformation rules, sequential composition, branching and iteration. We present a formal semantics for GP in the style of structural operational semantics. A special feature of our semantics is the use of finitely failing programs to define GP's powerful branching and iteration commands.

In Ian Mackie and Anamaria Martins Moreira: Proceedings Tenth International Workshop on Rule-Based Programming (RULE 2009), Brasília, Brazil , 28th June 2009, Electronic Proceedings in Theoretical Computer Science 21, pp. 27–38.
Published: 30th March 2010.

ArXived at: https://dx.doi.org/10.4204/EPTCS.21.3 bibtex PDF

Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org