XPath Node Selection over Grammar-Compressed Trees

Sebastian Maneth, Tom Sebastian

Research output: Chapter in Book/Report/Conference proceedingConference contribution


XML document markup is highly repetitive and therefore well compressible using grammar-based compression. Downward, navigational XPath can be executed over grammar-compressed trees in PTIME: the query is translated into an automaton which is executed in one pass over the grammar. This result is well-known and has been mentioned before. Here we present precise bounds on the time complexity of this problem, in terms of big-O notation. For a given grammar and XPath query, we consider three different tasks: (1) to count the number of nodes selected by the query, (2) to materialize the pre-order numbers of the selected nodes, and (3) to serialize the subtrees at the selected nodes.
Original languageEnglish
Title of host publicationProceedings Second International Workshop on Trends in Tree Automata and Tree Transducers, TTATT 2013, Hanoi, Vietnam, 19/10/2013.
PublisherCornell University Press
Number of pages11
Publication statusPublished - 2013


Dive into the research topics of 'XPath Node Selection over Grammar-Compressed Trees'. Together they form a unique fingerprint.

Cite this