Lifted Inference with Tree Axioms

Result code in 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>

Result on the web

<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>

Result language

angličtina

Original language name

Lifted Inference with Tree Axioms

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

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

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

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

Publication year

2021

Confidentiality

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

Article name in the collection

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

ISBN

978-1-956792-99-7

ISSN

2334-1033

e-ISSN

—

Number of pages

10

Pages from-to

599-608

Publisher name

International Joint Conferences on Artificial Intelligence Organization

Place of publication

—

Event location

Virtual conference

Event date

Nov 3, 2021

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—