Brian Courtehoute (University of York) |
Detlef Plump (University of York) |
We present a computation model based on a subclass of GP 2 graph programs which can simulate any off-line Turing machine of space complexity O(s(n) log s(n)) in space O(s(n)). The simulation only requires a quadratic time overhead. Our model shares this property with Schönhage's storage modification machines and Kolmogorov-Uspenskii machines. These machines use low-level pointer instructions whereas our GP 2-based model uses pattern-based transformation rules and high-level control constructs. |
ArXived at: https://dx.doi.org/10.4204/EPTCS.374.4 | bibtex | |
Comments and questions to: eptcs@eptcs.org |
For website issues: webmaster@eptcs.org |