{"ID":2881985,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.11515","arxiv_id":"2508.11515","title":"Weighted First Order Model Counting for Two-variable Logic with Axioms on Two Relations","abstract":"The Weighted First-Order Model Counting Problem (WFOMC) asks to compute the weighted sum of models of a given first-order logic sentence over a given domain. The boundary between fragments for which WFOMC can be computed in polynomial time relative to the domain size lies between the two-variable fragment ($\\text{FO}^2$) and the three-variable fragment ($\\text{FO}^3$). It is known that WFOMC for \\FOthree{} is $\\mathsf{\\#P_1}$-hard while polynomial-time algorithms exist for computing WFOMC for $\\text{FO}^2$ and $\\text{C}^2$, possibly extended by certain axioms such as the linear order axiom, the acyclicity axiom, and the connectedness axiom. All existing research has concentrated on extending the fragment with axioms on a single distinguished relation, leaving a gap in understanding the complexity boundary of axioms on multiple relations. In this study, we explore the extension of the two-variable fragment by axioms on two relations, presenting both negative and positive results. We show that WFOMC for $\\text{FO}^2$ with two linear order relations and $\\text{FO}^2$ with two acyclic relations are $\\mathsf{\\#P_1}$-hard. Conversely, we provide an algorithm in time polynomial in the domain size for WFOMC of $\\text{C}^2$ with a linear order relation, its successor relation and another successor relation.","short_abstract":"The Weighted First-Order Model Counting Problem (WFOMC) asks to compute the weighted sum of models of a given first-order logic sentence over a given domain. The boundary between fragments for which WFOMC can be computed in polynomial time relative to the domain size lies between the two-variable fragment ($\\text{FO}^2...","url_abs":"https://arxiv.org/abs/2508.11515","url_pdf":"https://arxiv.org/pdf/2508.11515v1","authors":"[\"Qipeng Kuang\",\"Václav Kůla\",\"Ondřej Kuželka\",\"Yuanhong Wang\",\"Yuyi Wang\"]","published":"2025-08-15T14:54:17Z","proceeding":"cs.LO","tasks":"[\"cs.LO\",\"cs.AI\"]","methods":"[]","has_code":false}