論文の概要: Weighted First Order Model Counting for Two-variable Logic with Axioms on Two Relations

• arxiv url: http://arxiv.org/abs/2508.11515v1
• Date: Fri, 15 Aug 2025 14:54:17 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-18 14:51:24.053979
• Title: Weighted First Order Model Counting for Two-variable Logic with Axioms on Two Relations
• Title（参考訳）: 2つの関係の公理を持つ2変数論理の重み付き一階モデルカウント
• Authors: Qipeng Kuang, Václav Kůla, Ondřej Kuželka, Yuanhong Wang, Yuyi Wang,
• Abstract要約: WFOMC for $textFO2$ with two linear order relations and $textFO2$ with two acyclic relations is $mathsf#P_1$-hard。 We provide a algorithm in time in the domain size of WFOMC of $textC2$ with a linear order relation, its successor relation and other successor relation。
• 参考スコア（独自算出の注目度）: 5.843053614714943
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.
• Abstract（参考訳）: 重み付き一階述語モデルカウント問題(WFOMC)は、与えられた一階述語論理文のモデルの重み付け和を与えられたドメイン上で計算することを要求する。 WFOMCがドメインサイズに対して多項式時間で計算できるフラグメントの境界は、2変数のフラグメント($\text{FO}^2$)と3変数のフラグメント($\text{FO}^3$)の間にある。 WFOMC for \FO Three{} は $\mathsf{\#P_1}$-hard であり、多項式時間アルゴリズムは WFOMC for $\text{FO}^2$ と $\text{C}^2$ であり、線形順序公理、巡回公理、連結公理などの特定の公理によって拡張される可能性がある。 既存のすべての研究は、一つの区別された関係上の公理で断片を拡張することに集中しており、複数の関係上の公理の複雑性境界を理解するためのギャップを残している。 本研究では,2変量フラグメントの2つの関係の公理による拡張について検討し,負と正の両方の結果を示した。 WFOMC for $\text{FO}^2$ with two linear order relations and $\text{FO}^2$ with two acyclic relations is $\mathsf{\#P_1}$-hard。 逆に、線形順序関係を持つ$\text{C}^2$のWFOMCのドメインサイズにおける時間多項式のアルゴリズム、その後継関係および他の後継関係を提供する。

関連論文リスト

• Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability [85.07238533644636]
  $Phi$-equilibriaは、オンライン学習とゲーム理論の中心にある、強力で柔軟なフレームワークだ。 効率的なオンラインアルゴリズムは、$textpoly(d, k)/epsilon2$ラウンドを使用して、平均$Phi$-regretを最大$epsilon$で生成することを示す。 また、オンライン設定において、ほぼ一致した下限を示し、その結果、$Phi$-regretの学習可能性を取得する偏差の族が初めて得られる。
  論文  参考訳（メタデータ） (2025-02-25T19:08:26Z)
• Lifted Inference beyond First-Order Logic [8.577974472273256]
  関係性の一つが有向非巡回グラフ、連結グラフ、木、森である場合、mathrmC2$文はドメインリフト可能であることを示す。 我々の結果は「分割による数え方」という新奇で一般的な方法論に頼っている。
  論文  参考訳（メタデータ） (2023-08-22T18:58:21Z)
• Weighted First Order Model Counting with Directed Acyclic Graph Axioms [7.766921168069532]
  多くのSRLにおける確率的推論と学習は、重み付き第一モデルカウント(WFOMC)に還元できる WFOMCは難解であることが知られている(mathrm#P$ complete)。 我々は,DAG(Directed Acyclic Graph)を除外したフラグメント$mathrmC2$,すなわち公理DAGを表す公理化グラフがドメインリフト可能であることを示す。
  論文  参考訳（メタデータ） (2023-02-20T08:35:13Z)
• Lifted Inference with Linear Order Axiom [0.0]
  We consider the task of weighted first-order model counting (WFOMC) 我々は、少なくとも2つの論理変数を持つ論理文の WFOMC が $n$ の時間で実行可能であることを示す。 線形順序でWFOMCをn$で計算できる新しい動的プログラミングベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-11-02T14:38:01Z)
• FeDXL: Provable Federated Learning for Deep X-Risk Optimization [105.17383135458897]
  我々は、既存のアルゴリズムが適用できないXリスクのファミリーを最適化するために、新しい連邦学習(FL)問題に取り組む。 Xリスクに対するFLアルゴリズムを設計する際の課題は、複数のマシンに対する目的の非可逆性と、異なるマシン間の相互依存にある。
  論文  参考訳（メタデータ） (2022-10-26T00:23:36Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。 すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
  論文  参考訳（メタデータ） (2022-09-04T10:01:39Z)
• Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policies [88.75843804630772]
  我々は既存の境界に対して,$Oleft(mathrmpoly(S,A,log K)sqrtKright)を後悔するアルゴリズムを設計する。 この結果は、定常政策の近似力、安定性、および濃度特性を確立する新しい構造補題の列に依存している。
  論文  参考訳（メタデータ） (2022-03-24T08:14:12Z)
• Stochastic behavior of outcome of Schur-Weyl duality measurement [45.41082277680607]
  我々は、$n$ qubits上のシュル=ワイル双対性に基づく分解によって定義される測定に焦点をあてる。 我々は、$n$が無限大に進むとき、中心極限の一種を含む様々な種類の分布を導出する。
  論文  参考訳（メタデータ） (2021-04-26T15:03:08Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。