Daily Arxiv

This is a page that curates AI-related papers published worldwide.
All content here is summarized using Google Gemini and operated on a non-profit basis.
Copyright for each paper belongs to the authors and their institutions; please make sure to credit the source when sharing.

Weighted First Order Model Counting for Two-variable Logic with Axioms on Two Relations

Created by
  • Haebom

Author

Qipeng Kuang, V aclav K\r{u}la, Ond\v{r}ej Ku\v{z}elka, Yuanhong Wang, Yuyi Wang

Outline

This paper addresses the Weighted First-Order Model Computation (WFOMC) problem, which computes the weighted sum of models of weighted first-order logic sentences. The bounds on the pieces for which WFOMC can be computed in polynomial time for the domain size lie between the two-variable piece ($\text{FO}^2$) and the three-variable piece ($\text{FO}^3$). While WFOMC for $\text{FO}^3$ is $\mathsf{P_1}$-hard, polynomial-time algorithms exist for $\text{FO}^2$ and $\text{C}^2$, although they can be extended to specific axioms such as the linear order axiom, the axiom of acyclicity, and the axiom of connectedness. Previous research has focused on extending the piece to axioms for a single distinct relation, leaving gaps in our understanding of the complexity bounds for axioms for multiple relations. This paper explores the extension of the two-variable piece to axioms for two relations, presenting both negative and positive results. We show that the WFOMC for $\text{FO}^2$ with two linear order relations and $\text{FO}^2$ with two acyclic relations is $\mathsf{ P_1}$-hard. Conversely, we provide a polynomial-time algorithm for the WFOMC of $\text{C}^2$ with a linear order relation, its successor, and another successor.

Takeaways, Limitations

Takeaways: Deepened our understanding of the complexity bounds of the WFOMC of two-variable fragments with axioms about two relations. In particular, we contributed to clarifying the complexity bounds by showing that the WFOMC of $\text{FO}^2$ with two linear ordinal relations or two acyclic relations cannot be solved in polynomial time. Conversely, we showed that polynomial-time algorithms exist under certain conditions, suggesting the possibility of developing practical algorithms.
Limitations: The complexity of the WFOMC for various combinations of axioms remains an open question. Research on relationships other than the two discussed in this study is needed. Further research on more general multivariate fragments is also a topic of ongoing research.
👍