Towards Efficient Implementation of XML Schema Content Models. Kilpel̈ainen, P. and Tuhkanen, R. In pages 239-241.
doi  abstract   bibtex   
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.
@inproceedings{ kil04,
  crossref = {doceng04},
  author = {Pekka Kilpel̈ainen and Rauno Tuhkanen},
  title = {Towards Efficient Implementation of XML Schema Content Models},
  pages = {239-241},
  doi = {10.1145/1030397.1030441},
  uri = {http://portal.acm.org/citation.cfm?doid=1030441},
  topic = {xsd[0.7]},
  abstract = {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.}
}
Downloads: 0