home >
publications >
non-standard computation >
*Probabilistic Graph Programming*

### Timothy Atkinson, Detlef Plump, Susan Stepney.

Probabilistic Graph Programming.

*Electronic pre-proceedings, GCM 2017, Marburg, Germany, July*, 2017

#### Abstract:

We introduce a notion of probability to the graph programming
language GP 2 which resolves nondeterministic choices of graph
transformation rules and their matches. With our programming model
Probabilistic GP 2 (P-GP 2), rule and match decisions are assigned uniform
distributions over their domains. In this paper, we present an implementation
of P-GP 2 as an extension of an existing GP 2 compiler.
As an example application, we analyse a (polynomial-time) nondeterministic
vertex colouring program which may produce one of many possible
colourings. The uniform implementation of P-GP 2 is shown, by
sampling, to produce different colourings with different probabilities, allowing
quantities such as expected colouring and likelihood of optimal
colouring to be considered.

full paper : pdf

@inproceedings(Atkinson2017:GCM:pgp,
author = "Timothy Atkinson and Detlef Plump and Susan Stepney",
title = "Probabilistic Graph Programming",
crossref = "GCM-2017"
)
@proceedings(GCM-2017,
title = "Electronic pre-proceedings, GCM 2017, Marburg, Germany, July 2017",
booktitle = "Electronic pre-proceedings, GCM 2017, Marburg, Germany, July 2017",
year = 2017
)