Paper Info
Title
Linear Time Membership for a Class of XML Types with Interleaving and Counting
Abstract
Regular Expressions (REs) form the basis of most XML type lan- guages, such as DTDs, XML Schema types, and XDuce types (Thomp- son et al. 2004; Hosoya and Pierce 2003). In this context, the in- terleaving operator would be a natural addition to the language of REs, as witnessed by the presence of limited forms of interleav- ing in XSD (the all group), Relax-NG, and SGML. Unfortunately, membership checking for REs with interleaving is NP-hard in gen- eral. We present here a restricted class of REs with interleaving and counting which admits a linear membership algorithm. This restricted class is known to be expressive enough for the vast ma- jority of the content models used in real-world DTDs and XSD schemas; moreover, we have proved in (Ghelli et al. 2007) that the same class admits a polynomial algorithm for subtyping and type- equivalence, problems which are EXPSPACE-complete for the full language of REs with interleaving. We first present an algorithm for membership of a list of words into a RE with interleaving and counting, based on the translation of the RE into a set of constraints. We generalize the approach in order to check membership of XML trees into a class of EDTDs with interleaving and counting, which models the crucial aspects of DTDs and XSD schemas. Finally, we extend the approach to REs with intersection.
Year
Venue
Keywords
2008
PLAN-X
regular expression,xml schema,linear time
Field
DocType
Citations 
XML,Theoretical computer science,Time complexity,Mathematics,Interleaving
Conference
4
PageRank 
References 
Authors
0.46
7
3
Name
Order
Citations
PageRank
Giorgio Ghelli11300255.19
Dario Colazzo228334.21
Carlo Sartiani324028.54