Towards Efficient Implementation of XML Schema Content Models

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.