Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/2506
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Blass, A | - |
dc.contributor.author | Gurevich, Y | - |
dc.contributor.author | VAN DEN BUSSCHE, Jan | - |
dc.date.accessioned | 2007-11-15T09:02:09Z | - |
dc.date.available | 2007-11-15T09:02:09Z | - |
dc.date.issued | 2002 | - |
dc.identifier.citation | INFORMATION AND COMPUTATION, 174(1). p. 20-36 | - |
dc.identifier.issn | 0890-5401 | - |
dc.identifier.uri | http://hdl.handle.net/1942/2506 | - |
dc.description.abstract | Abstract state machines (ASMs) form a relatively new computation model holding the promise that they can simulate any computational system in lockstep, In particular, an instance of the ASM model has recently been introduced for computing queries to relational databases, This model, to which we refer as the BGS model, provides a powerful query language in which all computable queries can be expressed. In this paper, we show that when one is only interested in polynomial-time computations, BGS is strictly more powerful than both QL and while(new), two well-known computationally complete query languages. We then show that when a language such as while(new) is extended with a duplicate elimination mechanism, polynomial-time simulations between the language and BGS become possible. (C) 2002 Elsevier Science (USA). | - |
dc.language.iso | en | - |
dc.publisher | ACADEMIC PRESS INC ELSEVIER SCIENCE | - |
dc.subject.other | ASM; choiceless; polynomial time; database query; complete query language; QL; while | - |
dc.title | Abstract state machines and computationally complete query languages | - |
dc.type | Journal Contribution | - |
dc.identifier.epage | 36 | - |
dc.identifier.issue | 1 | - |
dc.identifier.spage | 20 | - |
dc.identifier.volume | 174 | - |
local.format.pages | 17 | - |
local.bibliographicCitation.jcat | A1 | - |
dc.description.notes | Univ Michigan, Dept Math, Ann Arbor, MI 48109 USA. Microsoft Corp, Res, Redmond, WA 98052 USA. Limburgs Univ Ctr, B-3590 Diepenbeek, Belgium.Blass, A, Univ Michigan, Dept Math, Ann Arbor, MI 48109 USA. | - |
local.type.refereed | Refereed | - |
local.type.specified | Article | - |
dc.bibliographicCitation.oldjcat | A1 | - |
dc.identifier.doi | 10.1007/3-540-44518-8_3 | - |
dc.identifier.isi | 000175514800002 | - |
item.fullcitation | Blass, A; Gurevich, Y & VAN DEN BUSSCHE, Jan (2002) Abstract state machines and computationally complete query languages. In: INFORMATION AND COMPUTATION, 174(1). p. 20-36. | - |
item.fulltext | No Fulltext | - |
item.contributor | Blass, A | - |
item.contributor | Gurevich, Y | - |
item.contributor | VAN DEN BUSSCHE, Jan | - |
item.validation | ecoom 2003 | - |
item.accessRights | Closed Access | - |
crisitem.journal.issn | 0890-5401 | - |
crisitem.journal.eissn | 1090-2651 | - |
Appears in Collections: | Research publications |
SCOPUSTM
Citations
6
checked on Sep 2, 2020
WEB OF SCIENCETM
Citations
6
checked on Oct 6, 2024
Page view(s)
58
checked on Jul 28, 2023
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.