Time and Space Measures for a Complete Graph Computation Model

Brian Courtehoute; Detlef Plump

doi:10.4204/EPTCS.374.4

Time and Space Measures for a Complete Graph Computation Model

Brian Courtehoute, Detlef Plump

University of York

Research output: Contribution to journal › Conference article › peer-review

Abstract

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 [17]. These machines use low-level pointer instructions whereas our GP 2-based model uses pattern-based transformation rules and high-level control constructs.

Original language	English
Pages (from-to)	23-44
Number of pages	22
Journal	Electronic Proceedings in Theoretical Computer Science, EPTCS
Volume	374
DOIs	https://doi.org/10.4204/EPTCS.374.4
Publication status	Published - 22 Dec 2022
Externally published	Yes
Event	13th International Workshop on Graph Computation Models - Nantes, France Duration: 6 Jul 2022 → 6 Jul 2022 Conference number: 13 https://gcm2022.github.io/

Access to Document

10.4204/EPTCS.374.4Licence: CC BY

Cite this

@article{82b56f2f234c4c67a34cb3af24de306d,

title = "Time and Space Measures for a Complete Graph Computation Model",

abstract = "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{\"o}nhage's storage modification machines and Kolmogorov-Uspenskii machines [17]. These machines use low-level pointer instructions whereas our GP 2-based model uses pattern-based transformation rules and high-level control constructs.",

keywords = "Turing machines, Computation Models, Sch{\"o}nhage{\textquoteright}s storage modification machines, Kolmogorov-Uspenskii machines",

author = "Brian Courtehoute and Detlef Plump",

note = "Publisher Copyright: {\textcopyright} B. Courtehoute \& D. Plump.; 13th International Workshop on Graph Computation Models, GCM 2022 ; Conference date: 06-07-2022 Through 06-07-2022",

year = "2022",

month = dec,

day = "22",

doi = "10.4204/EPTCS.374.4",

language = "English",

volume = "374",

pages = "23--44",

journal = "Electronic Proceedings in Theoretical Computer Science, EPTCS",

issn = "2075-2180",

publisher = "Open Publishing Association",

url = "https://gcm2022.github.io/",

}

TY - JOUR

T1 - Time and Space Measures for a Complete Graph Computation Model

AU - Courtehoute, Brian

AU - Plump, Detlef

N1 - Conference code: 13

PY - 2022/12/22

Y1 - 2022/12/22

N2 - 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 [17]. These machines use low-level pointer instructions whereas our GP 2-based model uses pattern-based transformation rules and high-level control constructs.

AB - 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 [17]. These machines use low-level pointer instructions whereas our GP 2-based model uses pattern-based transformation rules and high-level control constructs.

KW - Turing machines

KW - Computation Models

KW - Schönhage’s storage modification machines

KW - Kolmogorov-Uspenskii machines

UR - https://www.scopus.com/pages/publications/85145438638

U2 - 10.4204/EPTCS.374.4

DO - 10.4204/EPTCS.374.4

M3 - Conference article

AN - SCOPUS:85145438638

SN - 2075-2180

VL - 374

SP - 23

EP - 44

JO - Electronic Proceedings in Theoretical Computer Science, EPTCS

JF - Electronic Proceedings in Theoretical Computer Science, EPTCS

T2 - 13th International Workshop on Graph Computation Models

Y2 - 6 July 2022 through 6 July 2022

ER -

Time and Space Measures for a Complete Graph Computation Model

Abstract

Access to Document

Other files and links

Fingerprint

Cite this