J. Dreier, P. Rossmanith:

"Approximate Evaluation of First-Order Counting Queries";

Talk: ACM-SIAM Symposium on Discrete Algorithms (SODA), Alexandria, Virginia, U.S.; 2021-01-10 - 2021-01-13; in: "Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms", (2021), ISBN: 978-1-61197-646-5; 1 - 20.

Kuske and Schweikardt introduced the very expressive rstorder

counting logic FOC(P) to model database queries with

counting operations. They showed that there is an e cient

model-checking algorithm on graphs with bounded degree,

while Grohe and Schweikardt showed that probably no such

algorithm exists for trees of bounded depth. We analyze

the fragment FO(f>0g) of this logic. While we remove

for example subtraction and comparison between two nonatomic

counting terms, this logic remains quite expressive:

We allow nested counting and comparison between counting

terms and arbitrarily large numbers. Our main result is

an approximation scheme of the model-checking problem for

FO(f>0g) that runs in linear fpt time on structures with

bounded expansion. This scheme either gives the correct

answer or says \I do not know." The latter answer may

only be given if small perturbations in the number-symbols

of the formula could make it both satis ed and unsatis ed.

This is complemented by showing that exactly solving the

model-checking problem for FO(f>0g) is already hard on

trees of bounded depth and just slightly increasing the

expressiveness of FO(f>0g) makes even approximation hard

on trees.

http://dx.doi.org/10.1137/1.9781611976465.104

https://publik.tuwien.ac.at/files/publik_299562.pdf

Created from the Publication Database of the Vienna University of Technology.