Query Automata (extended abstract)

Summary: Define Query Automata: deterministic two-way finite automata on ranked and unranked trees that select nodes (unary queries) based on state and label, addressing document DBs' ranked vs unranked grammars. Characterize expressiveness via MSO and give non-emptiness/equivalence complexity. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1174
Venue: PODS
Year: 1999
Pagerank: 5.9150511e-05
Overall Rank: 6,318 | 56.66%
DOI: 10.1145/303976.303997

Incoming Non-self Citations Over Time

Authors

1. Frank Neven (Limburgs Universitair Centrum)
2. Thomas Schwentick (Johannes Gutenberg University Mainz)

BibTeX Citation

@inproceedings{neven_pods99,
        address = {New York, NY, USA},
        series = {{PODS} '99},
        title = {{Query Automata (extended abstract)}},
        url = {https://dl.acm.org/doi/10.1145/303976.303997},
        doi = {10.1145/303976.303997},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Neven, Frank and Schwentick, Thomas},
        year = {1999}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,290	DTD Inference for Views of XML Data	2000	PODS	0.00011312135
4,178	A Web Odyssey: from Codd to XML	2001	PODS	6.849218e-05
7,876	Extended Path Expressions for XML	2001	PODS	5.5249028e-05

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
1,289	Mind Your Grammar: a New Approach to Modelling Text	1987	VLDB	0.00011314
1,856	Automata Theory for Database Theoreticians	1989	PODS	9.6053834e-05
6,319	Expressiveness of Structured Document Query Languages Based on Attribute Grammars (extended abstract)	1998	PODS	5.9150511e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,919	Stackless Processing of Streamed Trees	2021	PODS
2	11,121	Consistent Query Answering for Primary Keys on Rooted Tree Queries	2024	PODS
3	1,575	Expressive Languages for Path Queries over Graph-Structured Data	2010	PODS
4	1,856	Automata Theory for Database Theoreticians	1989	PODS
5	5,635	Algebras for Querying Text Regions (Extended Abstract)	1995	PODS
6	5,346	Running Tree Automata on Probabilistic XML	2009	PODS
7	2,625	Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach	2003	VLDB
8	4,986	Querying Graph Patterns	2011	PODS
9	5,579	Enumeration on Trees with Tractable Combined Complexity and Efficient Updates	2019	PODS
10	6,319	Expressiveness of Structured Document Query Languages Based on Attribute Grammars (extended abstract)	1998	PODS