Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.jlamp.2016.12.001 | Journal of Logical and Algebraic Methods in Programming |
Keywords | Field | DocType |
Graph programs,GP 2,Rule-based programming,Computational completeness,Random access machines,Graph transformation | Discrete mathematics,Modular decomposition,Programming language,Graph property,Partial k-tree,Theoretical computer science,Null graph,Graph product,Graph rewriting,Clique-width,Graph (abstract data type),Mathematics | Journal |
Volume | Issue | ISSN |
88 | 1 | 2352-2208 |
Citations | PageRank | References |
2 | 0.51 | 12 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Detlef Plump | 1 | 604 | 62.14 |