一句话：证明 FO2 及其带计数约束扩展在采样意义下具有域可提升性，给出多项式时间精确采样算法。
本文研究 Wang 等人提出的有限域上一阶逻辑句子的采样问题：如何高效地采样给定一阶句子的一个模型。作者将此前仅适用于全称量化子片段 UFO2 的结果推广到完整二变量片段 FO2，证明 FO2 在采样意义下具有域可提升性，即存在运行时间关于域大小多项式的采样算法。进一步，他们证明即使加入计数约束，如 ∀x∃=k y: φ(x,y) 和 ∃=k x∀y: φ(x,y)，其中 φ 无量词，该结论仍然成立。所提方法是构造性的，所得算法可用于组合结构的均匀生成，以及 Markov 逻辑网络和概率逻辑程序等统计关系模型中的采样。
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 FO2 (UFO2) to the entire fragment of FO2. Specifically, we prove the domain-liftability under sampling of FO2, meaning that there exists a sampling algorithm for FO2 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∃=ky : φ(x, y) and ∃=kx∀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.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@inproceedings{WangP0K23,
title = {On Exact Sampling in the Two-Variable Fragment of First-Order Logic},
author = {Yuanhong Wang and Juhua Pu and Yuyi Wang and Ondřej Kuželka},
booktitle = {LICS},
year = {2023},
doi = {10.1109/lics56636.2023.10175742}
}