论文标题
完整图计算模型的时间和空间度量
Time and Space Measures for a Complete Graph Computation Model
论文作者
论文摘要
我们提出了一个基于GP 2图程序子类的计算模型，该模型可以模拟空间o（s（n）log s（n））空间复杂性的任何离线Turing机器（s（n））。模拟仅需要二次时间开销。我们的模型与Schönhage的存储修改机和Kolmogorov-uspenskii机器共享此属性。这些机器使用低级指示指令，而我们的基于GP 2的模型则使用基于模式的转换规则和高级控制构建体。
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.
