Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/623
Full metadata record
DC FieldValueLanguage
dc.contributor.authorNEVEN, Frank-
dc.contributor.authorVAN DEN BUSSCHE, Jan-
dc.date.accessioned2005-03-09T13:52:21Z-
dc.date.available2005-03-09T13:52:21Z-
dc.date.issued2002-
dc.identifier.citationJOURNAL OF THE ACM, 49(1). p. 56-100-
dc.identifier.issn0004-5411-
dc.identifier.urihttp://hdl.handle.net/1942/623-
dc.description.abstractStructured document databases can be naturally viewed as derivation trees of a context-free grammar. Under this view, the classical formalism of attribute grammars becomes a formalism for structured document query languages. From this perspective, we study the expressive power of BAGs: Boolean-valued attribute grammars with propositional logic formulas as semantic rules, and RAGs: relation-valued attribute grammars with first-order logic formulas as semantic rules. BAGs can express only unary queries; RAGs can express queries of any arity. We first show that the (unary) queries expressible by BAGs are precisely those definable in monadic second-order logic. We then show that the queries expressible by RAGs are precisely those definable by first-order inductions of linear depth, or, equivalently, those computable in linear time on a parallel machine with polynomially many processors. Further, we show that RAGs that only use synthesized attributes are strictly weaker than RAGs that use both synthesized and inherited attributes. We show that RAGs are more expressive than monadic second-order logic for queries of any arity. Finally, we discuss relational attribute grammars in the context of BAGs and RAGs. We show that in the case of BAGs this does not increase the expressive power, while different semantics for relational RAGs capture the complexity classes NP, coNP and UP ∩ coUP.-
dc.format.extent506447 bytes-
dc.format.mimetypeapplication/pdf-
dc.language.isoen-
dc.publisherACM Press New York, NY, USA-
dc.titleExpressiveness of structured document query languages based on attribute grammars-
dc.typeJournal Contribution-
dc.identifier.epage100-
dc.identifier.issue1-
dc.identifier.spage56-
dc.identifier.volume49-
local.bibliographicCitation.jcatA1-
local.type.refereedRefereed-
local.type.specifiedArticle-
dc.bibliographicCitation.oldjcatA1-
dc.identifier.isi000175090500004-
dc.identifier.urlhttp://doi.acm.org/10.1145/505241.505245-
item.fulltextWith Fulltext-
item.accessRightsOpen Access-
item.validationecoom 2003-
item.fullcitationNEVEN, Frank & VAN DEN BUSSCHE, Jan (2002) Expressiveness of structured document query languages based on attribute grammars. In: JOURNAL OF THE ACM, 49(1). p. 56-100.-
item.contributorVAN DEN BUSSCHE, Jan-
item.contributorNEVEN, Frank-
crisitem.journal.issn0004-5411-
crisitem.journal.eissn1557-735X-
Appears in Collections:Research publications
Files in This Item:
File Description SizeFormat 
21neven.pdf494.58 kBAdobe PDFView/Open
Show simple item record

WEB OF SCIENCETM
Citations

26
checked on Jul 1, 2022

Page view(s)

58
checked on Jul 2, 2022

Download(s)

220
checked on Jul 2, 2022

Google ScholarTM

Check


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