Tree Automata and XPath on Compressed Trees

Markus Lohrey, Sebastian Maneth

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


The complexity of various membership problems for tree automata on compressed trees is analyzed. Two compressed representations are considered: dags, which allow to share identical subtrees in a tree, and straight-line context-free tree grammars, which moreover allow to share identical intermediate parts of a tree. Several completeness results for the classes NL, P, and PSPACE are obtained. Finally, the complexity of the XPath evaluation problem on trees that are compressed via straight-line context-free tree grammars is investigated.
Original languageEnglish
Title of host publicationImplementation and Application of Automata
Subtitle of host publication10th International Conference, CIAA 2005, Sophia Antipolis, France, June 27-29, 2005, Revised Selected Papers
EditorsJacques Farré, Igor Litovsky, Sylvain Schmitz
Place of PublicationBerlin, Heidelberg
PublisherSpringer Berlin Heidelberg
Number of pages13
ISBN (Electronic)978-3-540-33097-4
ISBN (Print)978-3-540-31023-5
Publication statusPublished - 2006

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg
ISSN (Print)0302-9743

Cite this