First-order query evaluation on structures of bounded degree

Details First-order query evaluation on structures of bounded degree First-order query evaluation on structures of bounded degree

2011-05-18

arxiv.org/abs/1105.3583v4

LMCS 7 (2:20) 2011

Computer Science

Logic in Computer Science

Scientific paper

10.2168/LMCS-7(2:20)2011

We consider the enumeration problem of first-order queries over structures of bounded degree. It was shown that this problem is in the Constant-Delaylin class. An enumeration problem belongs to Constant-Delaylin if for an input of size n it can be solved by: - an O(n) precomputation phase building an index structure, - followed by a phase enumerating the answers with no repetition and a constant delay between two consecutive outputs. In this article we give a different proof of this result based on Gaifman's locality theorem for first-order logic. Moreover, the constants we obtain yield a total evaluation time that is triply exponential in the size of the input formula, matching the complexity of the best known evaluation algorithms.

Affiliated with

Also associated with

No associations

Rating

First-order query evaluation on structures of bounded degree does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with First-order query evaluation on structures of bounded degree, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and First-order query evaluation on structures of bounded degree will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-53856