Towards efficient implementation of XML schema content models
Pekka Kilpeläinen, Rauno Tuhkanen · 2004
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.