On Exact Sampling in the Two-Variable Fragment of First-Order Logic

Code

• github.com/lucienwang1009/lifted_sampling_ufo2
  OfficialIn papernone★ 2

Abstract

In this paper, we study the sampling problem for first-order logic proposed recently by Wang et al. -- how to efficiently sample a model of a given first-order sentence on a finite domain? We extend their result for the universally-quantified subfragment of two-variable logic FO^2 (UFO^2) to the entire fragment of FO^2. Specifically, we prove the domain-liftability under sampling of FO^2, meaning that there exists a sampling algorithm for FO^2 that runs in time polynomial in the domain size. We then further show that this result continues to hold even in the presence of counting constraints, such as x_=k y: (x,y) and _=k x y: (x,y), for some quantifier-free formula (x,y). Our proposed method is constructive, and the resulting sampling algorithms have potential applications in various areas, including the uniform generation of combinatorial structures and sampling in statistical-relational models such as Markov logic networks and probabilistic logic programs.

Tasks

Reproductions