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)

Paper ID: had189375ea7cad2c
Venue: PODS
Year: 1995
Pagerank: 4.9793485e-05
Overall Rank: 13,278 | 10.73%
DOI: 10.1145/212433.220204

Incoming Non-self Citations Over Time

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

Authors

1. Guozhu Dong (University of Melbourne)
2. Jianwen Su (University of California Santa Barbara)

BibTeX Citation

@inproceedings{dong_pods95,
        address = {New York, NY, USA},
        series = {{PODS} '95},
        title = {{Space-Bounded FOIES}},
        url = {https://dl.acm.org/doi/10.1145/212433.220204},
        doi = {10.1145/212433.220204},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Dong, Guozhu and Su, Jianwen},
        year = {1995}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

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
39	Efficiently Updating Materialized Views	1986	SIGMOD	0.00046602544
62	Maintaining Views Incrementally	1993	SIGMOD	0.00039045511
2,292	Finitely Representable Databases	1994	PODS	8.6854411e-05
2,523	Incremental Evaluation of Rules and its Relationship to Parallelism	1991	SIGMOD	8.3464708e-05
5,225	Dyn-FO: A Parallel, Dynamic Complexity Class (Preliminary Version)	1994	PODS	6.220859e-05
5,784	Maintenance of Stratified Databases Viewed as a Belief Revision System	1987	PODS	5.9961885e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,954	Querying Big Data by Accessing Small Data	2015	PODS
2	4,479	EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract)	1987	PODS
3	143	Optimization of Nonrecursive Queries	1986	VLDB
4	7,140	Semantic Acyclicity on Graph Databases	2013	PODS
5	8,311	First-Order Query Evaluation with Cardinality Conditions	2018	PODS
6	13,210	Dynamic Tree Isomorphism via First-order Updates to a Relational Database	1998	PODS
7	12,056	The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs	2020	PODS
8	5,164	Enumeration of First-Order Queries on Classes of Structures With Bounded Expansion	2013	PODS
9	6,043	Size and Treewidth Bounds for Conjunctive Queries	2009	PODS
10	4,152	Enumeration for FO Queries over Nowhere Dense Graphs	2018	PODS