The Logic of Counting Query Answers

Abstract

We consider the problem of counting the number of answers to a first-order formula on a finite structure. We present and study an extension of first-order logic in which algorithms for this counting problem can be naturally and conveniently expressed, in senses that are made precise and that are motivated by the wish to understand tractable cases of the counting problem.

Cited by in corpus (2)

• Homomorphisms are indeed a good basis for counting: Three fixed-template dichotomy theorems, for the price of one
• Parametrised Complexity of Model Checking and Satisfiability in Propositional Dependence Logic