Time and Space Measures for a Complete Graph Computation Model

12/22/2022
by   Brian Courtehoute, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset