Expressiveness and Complexity of Generic Graph Machines

被引：0
作者：
M. Gemis
J. Paredaens
P. Peelman
J. Van den Bussche
机构：
[1] University of Antwerp (UIA),
[2] Informatica,undefined
[3] Universiteitsplein 1,undefined
[4] B-2610 Antwerp,undefined
[5] Belgium pareda@uia.ua.ac.be,undefined
来源：
Theory of Computing Systems | 1998年 / 31卷
关键词：
Computation Model; Generic Complexity; Graph Structure; Complexity Class; Generic Graph;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
The Generic Graph Machine (GGM) model is a Turing machine-like model for expressing generic computations working directly on graph structures. In this paper we present a number of observations concerning the expressiveness and complexity of GGMs. Our results comprise the following: (i) an intrinsic characterization of the pairs of graphs that are an input—output pair of some GGM; (ii) a comparison between GGM complexity and TM complexity; and (iii) a detailed discussion on the connections between the GGM model and other generic computation models considered in the literature, in particular the generic complexity classes of Abiteboul and Vianu, and the Database Method Schemes of Denninghoff and Vianu.
引用
收藏
页码：231 / 249
页数：18
相关论文
共 25 条
123