Lifted Inference with Linear Order Axiom
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F23%3A00366948" target="_blank" >RIV/68407700:21230/23:00366948 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1609/aaai.v37i10.26449" target="_blank" >https://doi.org/10.1609/aaai.v37i10.26449</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1609/aaai.v37i10.26449" target="_blank" >10.1609/aaai.v37i10.26449</a>
Alternative languages
Result language
angličtina
Original language name
Lifted Inference with Linear Order Axiom
Original language description
We consider the task of weighted first-order model counting (WFOMC) used for probabilistic inference in the area of statistical relational learning. Given a formula φ, domain size n and a pair of weight functions, what is the weighted sum of all models of φ over a domain of size n? It was shown that computing WFOMC of any logical sentence with at most two logical variables can be done in time polynomial in n. However, it was also shown that the task is #P1-complete once we add the third variable, which inspired the search for extensions of the two-variable fragment that would still permit a running time polynomial in n. One of such extension is the two-variable fragment with counting quantifiers. In this paper, we prove that adding a linear order axiom (which forces one of the predicates in φ to introduce a linear ordering of the domain elements in each model of φ) on top of the counting quantifiers still permits a computation time polynomial in the domain size. We present a new dynamic programming-based algorithm which can compute WFOMC with linear order in time polynomial in n, thus proving our primary claim.
Czech name
—
Czech description
—
Classification
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)
Result continuities
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)
Others
Publication year
2023
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of the 37th AAAI Conference on Artificial Intelligence
ISBN
978-1-57735-880-0
ISSN
2159-5399
e-ISSN
2374-3468
Number of pages
10
Pages from-to
12295-12304
Publisher name
AAAI Press
Place of publication
Menlo Park
Event location
Washington, DC
Event date
Feb 7, 2023
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—