Weighted First-Order Model Counting in the Two-Variable Fragment With Counting Quantifiers
arXiv:2007.05619v328 citations
Originality Synthesis-oriented
AI Analysis
This work is incremental, extending a prior result to a more expressive logical fragment, which may benefit researchers in knowledge representation and automated reasoning.
The paper tackled the problem of weighted first-order model counting (WFOMC) in the two-variable fragment with counting quantifiers, extending a known polynomial-time result to this more expressive logic.
It is known due to the work of Van den Broeck et al [KR, 2014] that weighted first-order model counting (WFOMC) in the two-variable fragment of first-order logic can be solved in time polynomial in the number of domain elements. In this paper we extend this result to the two-variable fragment with counting quantifiers.