Weighted First-Order Model Counting in the Two-Variable Fragment With Counting Quantifiers

Abstract

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.

arXiv commentThis version: Fixed typos in the statement of Proposition 4 (missing dependency on bit-complexity of w and \overline{w} in the statement of the proposition) and in Eq. 19 (missing negation)