Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/694
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Blass, Andreas | - |
dc.contributor.author | Gurevich, Yuri | - |
dc.contributor.author | VAN DEN BUSSCHE, Jan | - |
dc.date.accessioned | 2005-03-24T11:24:02Z | - |
dc.date.available | 2005-03-24T11:24:02Z | - |
dc.date.issued | 2000 | - |
dc.identifier.citation | Proceedings of the International Workshop on Abstract State Machines, Theory and Applications. p. 22-33 | - |
dc.identifier.isbn | 3-540-67959-6 | - |
dc.identifier.issn | 0302-9743 | - |
dc.identifier.uri | http://hdl.handle.net/1942/694 | - |
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 ${{\it while}_{\it new}}$, two well-known computationally complete query languages. We then show that when a language such as ${{\it while}_{\it new}}$ is extended with a duplicate elimination mechanism, polynomial-time simulations between the language and BGS become possible. | - |
dc.language.iso | en | - |
dc.publisher | Springer-Verlag | - |
dc.relation.ispartofseries | Lecture Notes In Computer Science | - |
dc.title | Abstract State Machines and Computationally Complete Query Languages | - |
dc.type | Journal Contribution | - |
local.bibliographicCitation.conferencename | Proceedings of the International Workshop on Abstract State Machines, Theory and Applications | - |
dc.identifier.epage | 33 | - |
dc.identifier.spage | 22 | - |
local.bibliographicCitation.jcat | A1 | - |
local.type.refereed | Refereed | - |
local.type.specified | Article | - |
local.relation.ispartofseriesnr | 1912 | - |
dc.bibliographicCitation.oldjcat | A2 | - |
item.fullcitation | Blass, Andreas; Gurevich, Yuri & VAN DEN BUSSCHE, Jan (2000) Abstract State Machines and Computationally Complete Query Languages. In: Proceedings of the International Workshop on Abstract State Machines, Theory and Applications. p. 22-33. | - |
item.fulltext | No Fulltext | - |
item.contributor | Blass, Andreas | - |
item.contributor | Gurevich, Yuri | - |
item.contributor | VAN DEN BUSSCHE, Jan | - |
item.accessRights | Closed Access | - |
Appears in Collections: | Research publications |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.