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.

@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
)