The Complexity of Text-Preserving XML Transformations

Summary: Defines text-preserving XML transforms whose output words are a subsequence of the input; characterizes them as copy- and reorder-free. Analyzes decision complexity: PTIME for top-down, EXPTIME-complete for DTL+XPath, decidable for DTL+MSO, and computes maximal input schemas. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1553
Venue: PODS
Year: 2011
Pagerank: 5.093636e-05
Overall Rank: 12,365 | 15.17%
DOI: 10.1145/1989284.1989316

Incoming Non-self Citations Over Time

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

Authors

1. Timos Antonopoulos (Hasselt University; Transnational University of Limburg)
2. Wim Martens (Technical University of Dortmund)
3. Frank Neven (Hasselt University; Transnational University of Limburg)

BibTeX Citation

@inproceedings{antonopoulos_pods11,
        address = {New York, NY, USA},
        series = {{PODS} '11},
        title = {{The Complexity of Text-Preserving XML Transformations}},
        url = {https://dl.acm.org/doi/10.1145/1989284.1989316},
        doi = {10.1145/1989284.1989316},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Antonopoulos, Timos and Martens, Wim and Neven, Frank},
        year = {2011}
}

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
4,051	XML Type Checking with Macro Tree Transducers	2005	PODS	6.9364294e-05
4,504	The Complexity of Query Containment in Expressive Fragments of XPath 2.0	2007	PODS	6.6592957e-05
13,954	On the Power of Walking for Querying Tree-Structured Data	2002	PODS	-

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,318	On the Complexity of Managing Probabilistic XML Data	2007	PODS
2	13,954	On the Power of Walking for Querying Tree-Structured Data	2002	PODS
3	12,634	Querying XML with Update Syntax	2007	SIGMOD
4	2,864	Typing and Querying XML Documents: Some Complexity Bounds	2003	PODS
5	13,846	Regular Rewriting of Active XML and Unambiguity	2005	PODS
6	2,049	XML Data Exchange: Consistency and Query Answering	2005	PODS
7	4,051	XML Type Checking with Macro Tree Transducers	2005	PODS
8	12,624	Expressiveness and Complexity of XML Publishing Transducers	2007	PODS
9	12,413	A Learning Algorithm for Top-Down XML Transformations	2010	PODS
10	3,274	Frontiers of Tractability for Typechecking Simple XML Transformations	2004	PODS