Tree Automata and XPath on Compressed Trees

Markus Lohrey; Sebastian Maneth

doi:10.1007/11605157_19

Tree Automata and XPath on Compressed Trees

Markus Lohrey, Sebastian Maneth

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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 language	English
Title of host publication	Implementation and Application of Automata
Subtitle of host publication	10th International Conference, CIAA 2005, Sophia Antipolis, France, June 27-29, 2005, Revised Selected Papers
Editors	Jacques Farré, Igor Litovsky, Sylvain Schmitz
Place of Publication	Berlin, Heidelberg
Publisher	Springer
Pages	225-237
Number of pages	13
ISBN (Electronic)	978-3-540-33097-4
ISBN (Print)	978-3-540-31023-5
DOIs	https://doi.org/10.1007/11605157_19
Publication status	Published - 2006

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Berlin Heidelberg
Volume	3845
ISSN (Print)	0302-9743

Access to Document

10.1007/11605157_19

http://link.springer.com/chapter/10.1007/11605157_19

Cite this

Lohrey, M., & Maneth, S. (2006). Tree Automata and XPath on Compressed Trees. In J. Farré, I. Litovsky, & S. Schmitz (Eds.), Implementation and Application of Automata: 10th International Conference, CIAA 2005, Sophia Antipolis, France, June 27-29, 2005, Revised Selected Papers (pp. 225-237). (Lecture Notes in Computer Science; Vol. 3845). Springer. https://doi.org/10.1007/11605157_19

Lohrey, Markus ; Maneth, Sebastian. / Tree Automata and XPath on Compressed Trees. Implementation and Application of Automata: 10th International Conference, CIAA 2005, Sophia Antipolis, France, June 27-29, 2005, Revised Selected Papers. editor / Jacques Farré ; Igor Litovsky ; Sylvain Schmitz. Berlin, Heidelberg : Springer, 2006. pp. 225-237 (Lecture Notes in Computer Science).

@inproceedings{504028683fb047baaee1fea9822503bd,

title = "Tree Automata and XPath on Compressed Trees",

abstract = "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.",

author = "Markus Lohrey and Sebastian Maneth",

year = "2006",

doi = "10.1007/11605157_19",

language = "English",

isbn = "978-3-540-31023-5",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "225--237",

editor = "Jacques Farr{\'e} and Igor Litovsky and Sylvain Schmitz",

booktitle = "Implementation and Application of Automata",

address = "United Kingdom",

}

Lohrey, M & Maneth, S 2006, Tree Automata and XPath on Compressed Trees. in J Farré, I Litovsky & S Schmitz (eds), Implementation and Application of Automata: 10th International Conference, CIAA 2005, Sophia Antipolis, France, June 27-29, 2005, Revised Selected Papers. Lecture Notes in Computer Science, vol. 3845, Springer, Berlin, Heidelberg, pp. 225-237. https://doi.org/10.1007/11605157_19

Tree Automata and XPath on Compressed Trees. / Lohrey, Markus; Maneth, Sebastian.
Implementation and Application of Automata: 10th International Conference, CIAA 2005, Sophia Antipolis, France, June 27-29, 2005, Revised Selected Papers. ed. / Jacques Farré; Igor Litovsky; Sylvain Schmitz. Berlin, Heidelberg: Springer, 2006. p. 225-237 (Lecture Notes in Computer Science; Vol. 3845).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Tree Automata and XPath on Compressed Trees

AU - Lohrey, Markus

AU - Maneth, Sebastian

PY - 2006

Y1 - 2006

N2 - 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.

AB - 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.

U2 - 10.1007/11605157_19

DO - 10.1007/11605157_19

M3 - Conference contribution

SN - 978-3-540-31023-5

T3 - Lecture Notes in Computer Science

SP - 225

EP - 237

BT - Implementation and Application of Automata

A2 - Farré, Jacques

A2 - Litovsky, Igor

A2 - Schmitz, Sylvain

PB - Springer

CY - Berlin, Heidelberg

ER -

Lohrey M, Maneth S. Tree Automata and XPath on Compressed Trees. In Farré J, Litovsky I, Schmitz S, editors, Implementation and Application of Automata: 10th International Conference, CIAA 2005, Sophia Antipolis, France, June 27-29, 2005, Revised Selected Papers. Berlin, Heidelberg: Springer. 2006. p. 225-237. (Lecture Notes in Computer Science). doi: 10.1007/11605157_19

Tree Automata and XPath on Compressed Trees

Abstract

Publication series

Access to Document

Fingerprint

Cite this