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

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F23%3A00367161" target="_blank" >RIV/68407700:21230/23:00367161 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1109/LICS56636.2023.10175742" target="_blank" >https://doi.org/10.1109/LICS56636.2023.10175742</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1109/LICS56636.2023.10175742" target="_blank" >10.1109/LICS56636.2023.10175742</a>

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

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

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2023

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)

ISBN

979-8-3503-3587-3

ISSN

1043-6871

e-ISSN

2575-5528

Počet stran výsledku

13

Strana od-do

—

Název nakladatele

IEEE Xplore

Místo vydání

—

Místo konání akce

Boston

Datum konání akce

26. 6. 2023

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

001036707700031