article · 2008

ABSTRACT Visibly Pushdown Automata for Streaming XML

Viraj Kumar, P. Madhusudan, Mahesh Viswanathan

Cited by 0Abstract and details only

Abstract

We 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 we demonstrate the power and ease visibly pushdown automata give in the design of streaming algorithms for XML documents. We 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. For the latter problem, we consider both pre-order typing and post-order typing of a document, which dynamically determines types at open-tags and close-tags respectively as soon as they are met. We also generalize the problems of pre-order and post-order typing to prefix querying. We show that a deterministic Vpa yields an algorithm to the problem of answering in one pass the set of all answers to any query that has the property that a node satisfying the query is determined solely by the prefix leading to the node. All the streaming algorithms we develop in this paper are based on the construction of deterministic Vpas, and hence, for any fixed problem, the algorithms process each element of the input in constant time, and use space O(d), where d is the depth of the document.

Cite this paper

APA 7

Kumar, V., Madhusudan, P., & Viswanathan, M. (2008). ABSTRACT Visibly Pushdown Automata for Streaming XML.

MLA 9

Kumar, Viraj, et al. “ABSTRACT Visibly Pushdown Automata for Streaming XML.” 2008.

Chicago

Kumar, Viraj, P. Madhusudan, and Mahesh Viswanathan. 2008. “ABSTRACT Visibly Pushdown Automata for Streaming XML.”

Harvard

Kumar, V., Madhusudan, P. and Viswanathan, M. (2008) ‘ABSTRACT Visibly Pushdown Automata for Streaming XML’.

BibTeX

@article{kumar2008abstract,
  title = {{ABSTRACT Visibly Pushdown Automata for Streaming XML}},
  author = {Kumar, Viraj and Madhusudan, P. and Viswanathan, Mahesh},
  year = {2008}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.