Association for Computing Machinery
The authors propose the study of Visibly Pushdown Automata (VPA) for processing XML documents. VPAs are pushdown automata where the input determines the stack operation, and XML documents are naturally visibly pushdown with the VPA pushing onto the stack on open-tags and popping the stack on close-tags. In this paper, they demonstrate the power and ease visibly pushdown automata give in the design of streaming algorithms for XML documents. They study the problems of type-checking streaming XML documents against SDTD schemas, and the problem of typing tags in a streaming XML document according to an SDTD schema.