The Logic of Counting Query Answers: A Study via Existential Positive Queries.
Hubie Chen, Stefan Mengel · arXiv (Cornell University) · 2015
We consider the computational complexity of counting the number of answers to a logical formula on a finite structure. In the setting of parameterized complexity, we present a trichotomy theorem on classes of existential positive queries. We then proceed to study an extension of first-order logic in which algorithms for the counting problem at hand can be naturally and conveniently expressed.