XPath, Transitive Closure Logic, and Nested Tree Walking Automata

Summary: Shows that XPath with Kleene‑star and subtree‑relativisation captures exactly FO(MTC) and is characterized by nested tree‑walking automata, yielding a strict separation from MSO on trees (resolves an open question). Analyzes complexity: combined query evaluation in PTIME, while satisfiability, containment and automaton emptiness are 2ExpTime‑complete (Core XPath: ExpTime‑complete). (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1464
Venue: PODS
Year: 2008
Pagerank: 5.8776391e-05
Overall Rank: 6,442 | 55.81%
DOI: 10.1145/1376916.1376952

Incoming Non-self Citations Over Time

Authors

1. Balder ten Cate (University of Amsterdam)
2. Luc Segoufin (INRIA)

BibTeX Citation

@inproceedings{cate_pods08,
        address = {New York, NY, USA},
        series = {{PODS} '08},
        title = {{XPath, Transitive Closure Logic, and Nested Tree Walking Automata}},
        url = {https://dl.acm.org/doi/10.1145/1376916.1376952},
        doi = {10.1145/1376916.1376952},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Cate, Balder ten and Segoufin, Luc},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,641	High-Performance Complex Event Processing over XML Streams	2012	SIGMOD	6.5913488e-05
12,491	Satisfiability of Downward XPath with Data Equality Tests	2009	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
666	Efficient Algorithms for Processing XPath Queries	2002	VLDB	0.00015166582
1,916	XPath Satisfiability in the Presence of DTDs	2005	PODS	9.4878711e-05
3,711	The Expressivity of XPath with Transitive Closure*	2006	PODS	7.1778094e-05
4,504	The Complexity of Query Containment in Expressive Fragments of XPath 2.0	2007	PODS	6.6592957e-05
6,137	XML Transformation by Tree-Walking Transducers with Invisible Pebbles	2007	PODS	5.9643797e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,132	The Complexity of XPath Query Evaluation	2003	PODS
2	12,684	Structural Characterizations of the Semantics of XPath as Navigation Tool on a Document	2006	PODS
3	395	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS
4	8,550	Conditional XPath, the first order complete XPath dialect*	2004	PODS
5	8,440	On XPath with Transitive Axes and Data Tests	2013	PODS
6	13,954	On the Power of Walking for Querying Tree-Structured Data	2002	PODS
7	1,564	Conjunctive Queries over Trees	2004	PODS
8	12,491	Satisfiability of Downward XPath with Data Equality Tests	2009	PODS
9	4,504	The Complexity of Query Containment in Expressive Fragments of XPath 2.0	2007	PODS
10	3,711	The Expressivity of XPath with Transitive Closure*	2006	PODS