2007 · 67 citations · 15 references
ComputingComputer ScienceInformation TechnologyComputer ArchitectureNatural Language ProcessingProgramming LanguagesAutomata TheoryFinite AutomataParsingPushdown AutomataStream ProcessingStreaming AlgorithmsPushdown Automata ParsingVisibly Pushdown AutomataXml ParsingXml Stream Processing
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.
15
Introduction to automata theory, languages, and computation
Computer Languages · 1980 · 6.9K citations
Rajeev Alur, P. Madhusudan · 2004 · 555 citations · Full text
Fernando Berzal · ACM SIGMOD Record · 2003 · 358 citations
Stream processing of XPath queries with predicates
Ashish Gupta, Dan Suciu · 2003 · 282 citations