English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In this paper, we study the sampling problem for first-order logic proposedrecently by Wang et al. -- how to efficiently sample a model of a givenfirst-order sentence on a finite domain? We extend their result for theuniversally-quantified subfragment of two-variable logic $\mathbf{FO}^2$($\mathbf{UFO}^2$) to the entire fragment of $\mathbf{FO}^2$. Specifically, weprove the domain-liftability under sampling of $\mathbf{FO}^2$, meaning thatthere exists a sampling algorithm for $\mathbf{FO}^2$ that runs in timepolynomial in the domain size. We then further show that this result continuesto hold even in the presence of counting constraints, such as $\forallx\exists_{=k} y: \varphi(x,y)$ and $\exists_{=k} x\forall y: \varphi(x,y)$, forsome quantifier-free formula $\varphi(x,y)$. Our proposed method isconstructive, and the resulting sampling algorithms have potential applicationsin various areas, including the uniform generation of combinatorial structuresand sampling in statistical-relational models such as Markov logic networks andprobabilistic logic programs.

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