Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/693
Title: Expressiveness and complexity of generic graph machines
Authors: Gemis, Marc
Paredaens, Jan
Peelman, Peter
VAN DEN BUSSCHE, Jan 
Issue Date: 1998
Publisher: Springer-Verlag
Source: Theory of Computing Systems, 31(3). p. 231-249
Abstract: 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 betweenGGMcomplexity 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.
Document URI: http://hdl.handle.net/1942/693
DOI: 10.1007/s002240000087
Type: Journal Contribution
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
expressiveness.pdf156.58 kBAdobe PDFView/Open
Show full item record

SCOPUSTM   
Citations

1
checked on Sep 2, 2020

WEB OF SCIENCETM
Citations

1
checked on May 14, 2022

Page view(s)

48
checked on May 19, 2022

Download(s)

156
checked on May 19, 2022

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.