The Logic of Counting Query Answers

2015/01/28 by Hubie Chen, Stefan Mengel, Chen, Hubie +1
Computer Science · #Advanced Graph Theory Research #Bayesian Modeling and Causal Inference #Computational Complexity (cs.CC) #Data Management and Algorithms #FOS: Computer and information sciences #Logic in Computer Science (cs.LO)

paper · pdf · doi:10.48550/arxiv.1501.07195

openalex publication_date 2015/01/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

• The core of a graph

Related

• Approximate Evaluation of First-Order Counting Queries
• Counting Query Answers over a DL-Lite Knowledge Base (extended version)
• First-Order Logic with Counting: At Least, Weak Hanf Normal Forms Always\n Exist and Can Be Computed!
• Consistent Query Answering for Primary Keys and Conjunctive Queries with Counting
• A Trichotomy in the Complexity of Counting Answers to Conjunctive Queries