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)
Incoming Non-self Citations Over Time
Authors
- 1. Frank Neven
- 2. Thomas Schwentick
Incoming Citations (Sorted by Pagerank)
Showing 3 of 3 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 882 | DTD Inference for Views of XML Data | 2000 | PODS | 0.00015657456 |
| 4,010 | A Web Odyssey: from Codd to XML | 2001 | PODS | 6.5351699e-05 |
| 7,361 | Extended Path Expressions for XML | 2001 | PODS | 4.7524599e-05 |
Previous
Page 1 / 1
Next
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 |
|---|---|---|---|---|
| 922 | Mind Your Grammar: a New Approach to Modelling Text | 1987 | VLDB | 0.00015297648 |
| 1,688 | Automata Theory for Database Theoreticians | 1989 | PODS | 0.00010913301 |
| 5,871 | Expressiveness of Structured Document Query Languages Based on Attribute Grammars (extended abstract) | 1998 | PODS | 5.2943906e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 7,497 | Stackless Processing of Streamed Trees | 2021 | PODS | 4.7180617e-05 |
| 10,899 | Consistent Query Answering for Primary Keys on Rooted Tree Queries | 2024 | PODS | 4.1945683e-05 |
| 1,812 | Expressive Languages for Path Queries over Graph-Structured Data | 2010 | PODS | 0.00010467069 |
| 1,688 | Automata Theory for Database Theoreticians | 1989 | PODS | 0.00010913301 |
| 5,198 | Algebras for Querying Text Regions (Extended Abstract) | 1995 | PODS | 5.6346171e-05 |
| 5,296 | Running Tree Automata on Probabilistic XML | 2009 | PODS | 5.5802694e-05 |
| 2,855 | Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach | 2003 | VLDB | 8.0059865e-05 |
| 4,946 | Querying Graph Patterns | 2011 | PODS | 5.8149362e-05 |
| 5,055 | Enumeration on Trees with Tractable Combined Complexity and Efficient Updates | 2019 | PODS | 5.7312839e-05 |
| 5,871 | Expressiveness of Structured Document Query Languages Based on Attribute Grammars (extended abstract) | 1998 | PODS | 5.2943906e-05 |