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.00065762967 |
| 95 | Maintaining Views Incrementally | 1993 | SIGMOD | 0.00050896659 |
| 1,649 | Finitely Representable Databases | 1994 | PODS | 0.00011017687 |
| 2,131 | Incremental Evaluation of Rules and its Relationship to Parallelism | 1991 | SIGMOD | 9.4776341e-05 |
| 4,632 | Dyn-FO: A Parallel, Dynamic Complexity Class (Preliminary Version) | 1994 | PODS | 6.0342363e-05 |
| 5,534 | Maintenance of Stratified Databases Viewed as a Belief Revision System | 1987 | PODS | 5.4541693e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 7,293 | On Tree-Based Techniques for Query Evaluation | 1992 | PODS | 4.7740089e-05 |
| 11,826 | Bounded Query Rewriting Using Views | 2016 | PODS | 4.1945683e-05 |
| 7,085 | Querying Big Data by Accessing Small Data | 2015 | PODS | 4.8388174e-05 |
| 3,999 | EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract) | 1987 | PODS | 6.5469939e-05 |
| 143 | Optimization of Nonrecursive Queries | 1986 | VLDB | 0.00041510555 |
| 6,948 | Semantic Acyclicity on Graph Databases | 2013 | PODS | 4.8898337e-05 |
| 12,727 | Dynamic Tree Isomorphism via First-order Updates to a Relational Database | 1998 | PODS | 4.1945683e-05 |
| 11,556 | The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs | 2020 | PODS | 4.1945683e-05 |
| 6,167 | Enumeration of First-Order Queries on Classes of Structures With Bounded Expansion | 2013 | PODS | 5.1717635e-05 |
| 5,744 | Size and Treewidth Bounds for Conjunctive Queries | 2009 | PODS | 5.3441438e-05 |