From imperative to rule-based graph programs

We discuss the translation of a simple imperative programming language, high-level random access machines, to the rule-based graph programming language GP 2. By proving the correctness of the translation and using GP 2 programs for encoding and decoding between arbitrary graphs and so-called register graphs, we show that GP 2 is computationally complete in a strong sense: every computable graph function can be directly computed with a GP 2 program which transforms input graphs into output graphs. Moreover, by carefully restricting the form of rules and control constructs in translated programs, we identify simple graph programs as a computationally complete sublanguage of GP 2. Simple programs use unconditional rules and abandon, besides other features, the non-deterministic choice of rules.