Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/606
Full metadata record
DC FieldValueLanguage
dc.contributor.authorMARTENS, Wim-
dc.contributor.authorNEVEN, Frank-
dc.contributor.authorSchwentick, Thomas-
dc.date.accessioned2005-03-03T13:52:05Z-
dc.date.available2005-03-03T13:52:05Z-
dc.date.issued2005-
dc.identifier.citationDATABASE THEORY - ICDT 2005. p. 68-82-
dc.identifier.issn0302-9743-
dc.identifier.urihttp://hdl.handle.net/1942/606-
dc.description.abstractIt is shown that the class of regular tree languages admitting one-pass preorder typing is exactly the class defined by restrained competition tree grammars introduced by Murata et al. [14]. In a streaming context, the former is the largest class of XSDs where every element in a document can be typed when its opening tag is met. The main technical machinery consists of semantical characterizations of restrained competition grammars and their subclasses. In particular, they can be characterized in terms of the context of nodes, closure properties, allowed patterns and guarded DTDs. It is further shown that deciding whether a schema is restrained competition is tractable. Deciding whether a schema is equivalent to a restained competition tree grammar, or one of its subclasses, is much more difficult: it is complete for EXPTIME. We show that our semantical characterizations allow for easy optimization and minimization algorithms. Finally, we relate the notion of one-pass preorder typing to the existing XML Schema standard.-
dc.format.extent390139 bytes-
dc.format.mimetypeapplication/pdf-
dc.language.isoen-
dc.relation.ispartofseriesLECTURE NOTES IN COMPUTER SCIENCE-
dc.titleWhich XML Schemas Admit 1-Pass Preorder Typing?-
dc.typeJournal Contribution-
local.bibliographicCitation.conferencenameDATABASE THEORY - ICDT 2005-
dc.identifier.epage82-
dc.identifier.spage68-
local.bibliographicCitation.jcatA1-
local.type.refereedRefereed-
local.type.specifiedArticle-
local.relation.ispartofseriesnr3363-
dc.bibliographicCitation.oldjcatA1-
dc.identifier.doi10.1007/b104421-
dc.identifier.isi000227472000005-
item.accessRightsOpen Access-
item.fullcitationMARTENS, Wim; NEVEN, Frank & Schwentick, Thomas (2005) Which XML Schemas Admit 1-Pass Preorder Typing?. In: DATABASE THEORY - ICDT 2005. p. 68-82.-
item.fulltextWith Fulltext-
item.validationecoom 2006-
crisitem.journal.issn0302-9743-
Appears in Collections:Research publications
Files in This Item:
File Description SizeFormat 
36 icdt05.pdf381 kBAdobe PDFView/Open
Show simple item record

Google ScholarTM

Check

Altmetric


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