Expressiveness and Complexity of XML Publishing Transducers

Summary: Introduce publishing transducers: a machine model that generates XML trees via iterative relational queries, parameterized by query class, temporary storage, and optional virtual nodes, capturing existing XML-publishing languages. Characterize membership/emptiness/equivalence (PTIME→undecidable) and map expressiveness to PSPACE, linear-datalog fragments and logical tree transductions. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1417
Venue: PODS
Year: 2007
Pagerank: 5.093636e-05
Overall Rank: 12,624 | 13.39%
DOI: 10.1145/1265530.1265542

Incoming Non-self Citations Over Time

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

Authors

1. Wenfei Fan (AT&T; University of Edinburgh)
2. Floris Geerts (Hasselt University; Transnational University of Limburg; University of Edinburgh)
3. Frank Neven (Hasselt University; Transnational University of Limburg)

BibTeX Citation

@inproceedings{fan_pods07,
        address = {New York, NY, USA},
        series = {{PODS} '07},
        title = {{Expressiveness and Complexity of XML Publishing Transducers}},
        url = {https://dl.acm.org/doi/10.1145/1265530.1265542},
        doi = {10.1145/1265530.1265542},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Fan, Wenfei and Geerts, Floris and Neven, Frank},
        year = {2007}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
377	Data Exchange: Getting to the Core	2003	PODS	0.00019643793
535	Efficiently Publishing Relational Data as XML Documents	2000	VLDB	0.00017003136
1,082	A Transducer-Based XML Query Processor	2002	VLDB	0.00012257574
2,049	XML Data Exchange: Consistency and Query Answering	2005	PODS	9.255274e-05
2,261	Type Inference for Queries on Semistructured Data (Extended Abstract)	1999	PODS	8.846133e-05
4,619	DTD-Directed Publishing with Attribute Translation Grammars	2002	VLDB	6.6033756e-05
13,877	Incremental Evaluation of Schema-Directed XML Publishing	2004	SIGMOD	-
13,954	On the Power of Walking for Querying Tree-Structured Data	2002	PODS	-

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,274	Frontiers of Tractability for Typechecking Simple XML Transformations	2004	PODS
2	8,417	XML Schema Mappings	2009	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	5,346	Running Tree Automata on Probabilistic XML	2009	PODS
6	12,410	Certain Answers for XML Queries	2010	PODS
7	1,564	Conjunctive Queries over Trees	2004	PODS
8	4,051	XML Type Checking with Macro Tree Transducers	2005	PODS
9	12,365	The Complexity of Text-Preserving XML Transformations	2011	PODS
10	13,954	On the Power of Walking for Querying Tree-Structured Data	2002	PODS