Space-Bounded FOIES
Summary: Characterize space of FOIES by maximal auxiliary arity k; define FOIES_k and prove tight arity bounds and separations for standard graph queries via Ehrenfeucht–Fraïssé arguments. Show undirected transitive closure requires k=2, resolving Patnaik–Immerman PODS'94 open problem. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
- 1. Guozhu Dong
- 2. Jianwen Su
Incoming Citations (Sorted by Pagerank)
Showing 0 of 0 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 6 of 6 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 55 | Efficiently Updating Materialized Views | 1986 | SIGMOD | 0.00065687017 |
| 97 | Maintaining Views Incrementally | 1993 | SIGMOD | 0.00050863077 |
| 1,648 | Finitely Representable Databases | 1994 | PODS | 0.00011007456 |
| 2,134 | Incremental Evaluation of Rules and its Relationship to Parallelism | 1991 | SIGMOD | 9.4690121e-05 |
| 4,633 | Dyn-FO: A Parallel, Dynamic Complexity Class (Preliminary Version) | 1994 | PODS | 6.0283752e-05 |
| 5,542 | Maintenance of Stratified Databases Viewed as a Belief Revision System | 1987 | PODS | 5.4488003e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 7,289 | On Tree-Based Techniques for Query Evaluation | 1992 | PODS | 4.7692311e-05 |
| 11,834 | Bounded Query Rewriting Using Views | 2016 | PODS | 4.1905499e-05 |
| 7,061 | Querying Big Data by Accessing Small Data | 2015 | PODS | 4.8400281e-05 |
| 3,990 | EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract) | 1987 | PODS | 6.5536618e-05 |
| 144 | Optimization of Nonrecursive Queries | 1986 | VLDB | 0.00041430126 |
| 6,945 | Semantic Acyclicity on Graph Databases | 2013 | PODS | 4.8874695e-05 |
| 12,736 | Dynamic Tree Isomorphism via First-order Updates to a Relational Database | 1998 | PODS | 4.1905499e-05 |
| 11,560 | The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs | 2020 | PODS | 4.1905499e-05 |
| 6,175 | Enumeration of First-Order Queries on Classes of Structures With Bounded Expansion | 2013 | PODS | 5.1667995e-05 |
| 5,752 | Size and Treewidth Bounds for Conjunctive Queries | 2009 | PODS | 5.3393414e-05 |