Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/693
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Gemis, Marc | - |
dc.contributor.author | Paredaens, Jan | - |
dc.contributor.author | Peelman, Peter | - |
dc.contributor.author | VAN DEN BUSSCHE, Jan | - |
dc.date.accessioned | 2005-03-24T11:22:16Z | - |
dc.date.available | 2005-03-24T11:22:16Z | - |
dc.date.issued | 1998 | - |
dc.identifier.citation | Theory of Computing Systems, 31(3). p. 231-249 | - |
dc.identifier.uri | http://hdl.handle.net/1942/693 | - |
dc.description.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. | - |
dc.format.extent | 160336 bytes | - |
dc.format.mimetype | application/pdf | - |
dc.language.iso | en | - |
dc.publisher | Springer-Verlag | - |
dc.title | Expressiveness and complexity of generic graph machines | - |
dc.type | Journal Contribution | - |
dc.identifier.epage | 249 | - |
dc.identifier.issue | 3 | - |
dc.identifier.spage | 231 | - |
dc.identifier.volume | 31 | - |
local.type.specified | Article | - |
dc.bibliographicCitation.oldjcat | - | |
dc.identifier.doi | 10.1007/s002240000087 | - |
item.fullcitation | Gemis, Marc; Paredaens, Jan; Peelman, Peter & VAN DEN BUSSCHE, Jan (1998) Expressiveness and complexity of generic graph machines. In: Theory of Computing Systems, 31(3). p. 231-249. | - |
item.accessRights | Open Access | - |
item.contributor | Gemis, Marc | - |
item.contributor | Paredaens, Jan | - |
item.contributor | Peelman, Peter | - |
item.contributor | VAN DEN BUSSCHE, Jan | - |
item.fulltext | With Fulltext | - |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
expressiveness.pdf | 156.58 kB | Adobe PDF | View/Open |
SCOPUSTM
Citations
1
checked on Sep 2, 2020
WEB OF SCIENCETM
Citations
1
checked on Apr 16, 2024
Page view(s)
56
checked on Sep 7, 2022
Download(s)
186
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.