XML Transformation by Tree-Walking Transducers with Invisible Pebbles

Summary: Extend pebble tree automata/transducers with unbounded 'invisible' pebbles, enabling recognition of all regular tree languages and an XPath-like path algebra that captures every MSO-definable binary pattern. Show MSO tests on observable configs, model XSLT recursion, retain decidable typechecking, and often reduce typechecking complexity for conjunctive queries using MSO binary patterns. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1415
Venue: PODS
Year: 2007
Pagerank: 5.9643797e-05
Overall Rank: 6,137 | 57.90%
DOI: 10.1145/1265530.1265540

Incoming Non-self Citations Over Time

Authors

1. Joost Engelfriet (Leiden University)
2. Hendrik Jan Hoogeboom (Leiden University)
3. Bart Samwel (Leiden University)

BibTeX Citation

@inproceedings{engelfriet_pods07,
        address = {New York, NY, USA},
        series = {{PODS} '07},
        title = {{XML Transformation by Tree-Walking Transducers with Invisible Pebbles}},
        url = {https://dl.acm.org/doi/10.1145/1265530.1265540},
        doi = {10.1145/1265530.1265540},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Engelfriet, Joost and Hoogeboom, Hendrik Jan and Samwel, Bart},
        year = {2007}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,442	XPath, Transitive Closure Logic, and Nested Tree Walking Automata	2008	PODS	5.8776391e-05
12,575	Type Inference and Type Checking for Queries on Execution Traces	2008	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 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,564	Conjunctive Queries over Trees	2004	PODS	0.00010349456
3,711	The Expressivity of XPath with Transitive Closure*	2006	PODS	7.1778094e-05
4,051	XML Type Checking with Macro Tree Transducers	2005	PODS	6.9364294e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,442	XPath, Transitive Closure Logic, and Nested Tree Walking Automata	2008	PODS
2	13,875	Trees, Automata and XML (Invited Tutorial)	2004	PODS
3	12,634	Querying XML with Update Syntax	2007	SIGMOD
4	12,624	Expressiveness and Complexity of XML Publishing Transducers	2007	PODS
5	5,346	Running Tree Automata on Probabilistic XML	2009	PODS
6	12,365	The Complexity of Text-Preserving XML Transformations	2011	PODS
7	13,954	On the Power of Walking for Querying Tree-Structured Data	2002	PODS
8	3,274	Frontiers of Tractability for Typechecking Simple XML Transformations	2004	PODS
9	4,051	XML Type Checking with Macro Tree Transducers	2005	PODS
10	1,372	Typechecking for XML Transformers	2000	PODS