A Learning Algorithm for Top-Down XML Transformations

Summary: Generalizes regular-language learnability to deterministic top-down tree transducers (dtops): proves a Myhill–Nerode theorem for dtops and gives a polynomial-size sample learning algorithm that handles copying, deletion, and permutation. Presents a DTD-based encoding of unranked XML trees so dtops can realize many practical XSLT-like transformations beyond first-child/next-sibling encodings. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1526
Venue: PODS
Year: 2010
Pagerank: 5.093636e-05
Overall Rank: 12,413 | 14.84%
DOI: 10.1145/1807085.1807122

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Aurélien Lemay (INRIA; Lille Laboratory of Fundamental Computer Science; University of Lille)
2. Sebastian Maneth (National ICT Australia; University of New South Wales)
3. Joachim Niehren (INRIA; Lille Laboratory of Fundamental Computer Science; University of Lille)

BibTeX Citation

@inproceedings{lemay_pods10,
        address = {New York, NY, USA},
        series = {{PODS} '10},
        title = {{A Learning Algorithm for Top-Down XML Transformations}},
        url = {https://dl.acm.org/doi/10.1145/1807085.1807122},
        doi = {10.1145/1807085.1807122},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Lemay, Aurélien and Maneth, Sebastian and Niehren, Joachim},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
263	Reconciling Schemas of Disparate Data Sources: A Machine-Learning Approach	2001	SIGMOD	0.0002305693
416	Translating Web Data	2002	VLDB	0.00018877803
4,051	XML Type Checking with Macro Tree Transducers	2005	PODS	6.9364294e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,634	Querying XML with Update Syntax	2007	SIGMOD
2	12,624	Expressiveness and Complexity of XML Publishing Transducers	2007	PODS
3	3,185	Inference of Concise DTDs from XML Data	2006	VLDB
4	13,875	Trees, Automata and XML (Invited Tutorial)	2004	PODS
5	2,967	Labeling Dynamic XML Trees	2002	PODS
6	12,412	Simplifying XML Schema: Single-Type Approximations of Regular Tree Languages	2010	PODS
7	3,274	Frontiers of Tractability for Typechecking Simple XML Transformations	2004	PODS
8	4,051	XML Type Checking with Macro Tree Transducers	2005	PODS
9	5,346	Running Tree Automata on Probabilistic XML	2009	PODS
10	12,365	The Complexity of Text-Preserving XML Transformations	2011	PODS