Towards Efficient Implementation of XML Schema Content Models

Pekka Kilpeläinen, Rauno Tuhkanen


XML Schema uses an extension of traditional regular expressions for describing allowed contents of document elements. Iteration is described through numeric attributes minOccurs and maxOccurs attached to content-describing elements such as sequence, choice, and element. These numeric occurrence indicators are a challenge to standard automata-based solutions. Straightforward solutions require space that is exponential with respect to the length of the expressions. We describe a strategy to implement unambiguous content model expressions as counter automata, which are of linear size only.


Bibliography Navigation: Reference List; Author Index; Title Index; Keyword Index

Generated by sharef2html on 2011-04-15, 02:00:41.