REVIEW 1 cited by
First-order queries on classes of structures with bounded expansion
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original abstract
We consider the evaluation of first-order queries over classes of databases with bounded expansion. The notion of bounded expansion is fairly broad and generalizes bounded degree, bounded treewidth and exclusion of at least one minor. It was known that over a class of databases with bounded expansion, first-order sentences could be evaluated in time linear in the size of the database. We give a different proof of this result. Moreover, we show that answers to first-order queries can be enumerated with constant delay after a linear time preprocessing. We also show that counting the number of answers to a query can be done in time linear in the size of the database.
Forward citations
Cited by 1 Pith paper
-
Triadic First-Order Logic Queries in Temporal Networks
FOLTY is the first algorithm for thresholded FOL triadic motif queries on temporal networks, with O(m α log σ_max) running time matching the best temporal triangle counters.
Discussion (0). Continue with ORCID to comment.