Faster Lifting for Ordered Domains with Predecessor Relations

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F25%3A00387937" target="_blank" >RIV/68407700:21230/25:00387937 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.3233/FAIA251008" target="_blank" >https://doi.org/10.3233/FAIA251008</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.3233/FAIA251008" target="_blank" >10.3233/FAIA251008</a>

Result language

angličtina

Original language name

Faster Lifting for Ordered Domains with Predecessor Relations

Original language description

We investigate lifted inference on ordered domains with predecessor relations, where the elements of the domain respect a total (cyclic) order, and every element has a distinct (clockwise) predecessor. Previous work has explored this problem through weighted first-order model counting (WFOMC), which computes the weighted sum of models for a given first-order logic sentence over a finite domain. In WFOMC, the order constraint is typically encoded by the linear order axiom introducing a binary predicate in the sentence to impose a linear ordering on the domain elements. The immediate and second predecessor relations are then encoded by the linear order predicate. Although WFOMC with the linear order axiom is theoretically tractable, existing algorithms struggle with practical applications, particularly when the predecessor relations are involved. In this paper, we treat predecessor relations as a native part of the axiom and devise a novel algorithm that inherently supports these relations. The proposed algorithm not only provides an exponential speedup for the immediate and second predecessor relations, which are known to be tractable, but also handles the general k-th predecessor relations. The extensive experiments on lifted inference tasks and combinatorics math problems demonstrate the efficiency of our algorithm, achieving speedups of a full order of magnitude.

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

<a href="/en/project/GA23-07299S" target="_blank" >GA23-07299S: Statistical Relational Learning in Dynamic Domains</a><br>

Continuities

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

Publication year

2025

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

28th European Conference on Artificial Intelligence, 25-30 October 2025, Bologna, Italy – Including 14th Conference on Prestigious Applications of Intelligent Systems (PAIS 2025)

ISBN

978-1-64368-631-8

ISSN

0922-6389

e-ISSN

1879-8314

Number of pages

8

Pages from-to

1784-1791

Publisher name

IOS Press

Place of publication

Amsterdam

Event location

Bologna

Event date

Oct 27, 2025

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—