Trees, Automata and XML (Invited Tutorial)

Summary: Tutorial surveying string and tree automata (and matching logics) as foundations for XML formalisms—DTDs, XPath, query/transformation languages—and for reasoning about expressive power. Focus on automata-enabled static analyses: containment, satisfiability, type checking. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1323
Venue: PODS
Year: 2004
Pagerank: -
Overall Rank: 13,875 | 4.81%
DOI: 10.1145/1055558.1055589

Incoming Non-self Citations Over Time

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

Authors

1. Thomas Schwentick (Philipps University Marburg)

BibTeX Citation

@inproceedings{schwentick_pods04,
        address = {New York, NY, USA},
        series = {{PODS} '04},
        title = {{Trees, Automata and XML (Invited Tutorial)}},
        url = {https://dl.acm.org/doi/10.1145/1055558.1055589},
        doi = {10.1145/1055558.1055589},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Schwentick, Thomas},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,412	Simplifying XML Schema: Single-Type Approximations of Regular Tree Languages	2010	PODS
2	6,137	XML Transformation by Tree-Walking Transducers with Invisible Pebbles	2007	PODS
3	12,634	Querying XML with Update Syntax	2007	SIGMOD
4	6,442	XPath, Transitive Closure Logic, and Nested Tree Walking Automata	2008	PODS
5	13,954	On the Power of Walking for Querying Tree-Structured Data	2002	PODS
6	12,624	Expressiveness and Complexity of XML Publishing Transducers	2007	PODS
7	4,051	XML Type Checking with Macro Tree Transducers	2005	PODS
8	3,274	Frontiers of Tractability for Typechecking Simple XML Transformations	2004	PODS
9	2,864	Typing and Querying XML Documents: Some Complexity Bounds	2003	PODS
10	5,346	Running Tree Automata on Probabilistic XML	2009	PODS