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
相关论文
共 50 条
  • [1] Expressiveness and complexity of generic graph machines
    Gemis, M
    Paredaens, J
    Peelman, P
    Van den Bussche, J
    THEORY OF COMPUTING SYSTEMS, 1998, 31 (03) : 231 - 249
  • [2] Expressiveness and complexity of graph logic
    Dawar, Anui
    Gardner, Philippa
    Ghelli, Giorgio
    INFORMATION AND COMPUTATION, 2007, 205 (03) : 263 - 310
  • [3] Timed recursive state machines: Expressiveness and complexity
    Benerecetti, Massimo
    Peron, Adriano
    THEORETICAL COMPUTER SCIENCE, 2016, 625 : 85 - 124
  • [4] Graph-based Discriminators: Sample Complexity and Expressiveness
    Livni, Roi
    Mansour, Yishay
    ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 32 (NIPS 2019), 2019, 32
  • [5] THE GENERIC COMPLEXITY OF THE GRAPH TRIANGULATION PROBLEM
    Rybalov, A. N.
    PRIKLADNAYA DISKRETNAYA MATEMATIKA, 2022, (58): : 105 - 111
  • [6] ON GENERIC COMPLEXITY OF THE GRAPH CLUSTERING PROBLEM
    Rybalov, A. N.
    PRIKLADNAYA DISKRETNAYA MATEMATIKA, 2019, (46): : 72 - 77
  • [7] On the generic complexity of the searching graph isomorphism problem
    Rybalov, Alexander
    GROUPS COMPLEXITY CRYPTOLOGY, 2015, 7 (02) : 191 - 193
  • [8] Generic case complexity of the Graph Isomorphism Problem
    Noskov, Gennady A.
    Rybalov, Alexander N.
    GROUPS COMPLEXITY CRYPTOLOGY, 2016, 8 (01) : 9 - 20
  • [9] Expressiveness, meanings and machines
    Davidson, Joe
    Michaelson, Greg
    COMPUTABILITY-THE JOURNAL OF THE ASSOCIATION CIE, 2018, 7 (04): : 367 - 394
  • [10] ON THE EXPRESSIVENESS AND COMPLEXITY OF ATL
    Laroussinie, Francois
    Markey, Nicolas
    Oreiby, Ghassan
    LOGICAL METHODS IN COMPUTER SCIENCE, 2008, 4 (02)
12345