Kazana, Wojciech and Segoufin, Luc - First-order query evaluation on structures of bounded degree

lmcs:903 - Logical Methods in Computer Science, June 29, 2011, Volume 7, Issue 2 - https://doi.org/10.2168/LMCS-7(2:20)2011
First-order query evaluation on structures of bounded degree

Authors: Kazana, Wojciech and Segoufin, Luc

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.

Volume: Volume 7, Issue 2
Published on: June 29, 2011
Submitted on: November 19, 2010
Keywords: Computer Science - Logic in Computer Science,F.4.1, F.1.3


Consultation statistics

This page has been seen 195 times.
This article's PDF has been downloaded 120 times.