Lifted Inference with Tree Axioms

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F21%3A00354304" target="_blank" >RIV/68407700:21230/21:00354304 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.24963/kr.2021/57" target="_blank" >https://doi.org/10.24963/kr.2021/57</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.24963/kr.2021/57" target="_blank" >10.24963/kr.2021/57</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Lifted Inference with Tree Axioms

Popis výsledku v původním jazyce

We consider the problem of weighted first-order model counting (WFOMC): given a first-order sentence ϕ and domain size n element ℕ, determine the weighted sum of models of ϕ over the domain {1, ..., n}. Past work has shown that any sentence using at most two logical variables admits an algorithm for WFOMC that runs in time polynomial in the given domain size (Van den Broeck 2011; Van den Broeck, Meert, and Darwiche 2014). In this paper, we extend this result to any two-variable sentence ϕ with the addition of a tree axiom, stating that some distinguished binary relation in ϕ forms a tree in the graph-theoretic sense.

Název v anglickém jazyce

Lifted Inference with Tree Axioms

Popis výsledku anglicky

We consider the problem of weighted first-order model counting (WFOMC): given a first-order sentence ϕ and domain size n element ℕ, determine the weighted sum of models of ϕ over the domain {1, ..., n}. Past work has shown that any sentence using at most two logical variables admits an algorithm for WFOMC that runs in time polynomial in the given domain size (Van den Broeck 2011; Van den Broeck, Meert, and Darwiche 2014). In this paper, we extend this result to any two-variable sentence ϕ with the addition of a tree axiom, stating that some distinguished binary relation in ϕ forms a tree in the graph-theoretic sense.

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í

2021

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

Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning

ISBN

978-1-956792-99-7

ISSN

2334-1033

e-ISSN

—

Počet stran výsledku

10

Strana od-do

599-608

Název nakladatele

International Joint Conferences on Artificial Intelligence Organization

Místo vydání

—

Místo konání akce

Virtual conference

Datum konání akce

3. 11. 2021

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

WRD - Celosvětová akce

Kód UT WoS článku

—