論文の概要: A Fast Model Counting Algorithm for Two-Variable Logic with Counting and Modulo Counting Quantifiers

• arxiv url: http://arxiv.org/abs/2605.03391v1
• Date: Tue, 05 May 2026 05:58:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-06 19:35:43.791209
• Title: A Fast Model Counting Algorithm for Two-Variable Logic with Counting and Modulo Counting Quantifiers
• Title（参考訳）: 数量演算器とモデュロ数演算器を用いた2変数論理の高速モデルカウントアルゴリズム
• Authors: Shixin Sun, Astrid Klipfel, Ondřej Kuželka, Yuanhong Wang, Yi Chang,
• Abstract要約: 我々は、$mathbfC2$上のWFOMCのリフトアルゴリズムであるIncrementalWFOMC3とそのモジュロカウント拡張である$mathbf2_textmod$を紹介する。 まず、WFOMCが$mathbfC2$でより厳密なデータ複雑度を導出し、カウントパラメータの2次実行から線形実行までの度合いを下げる。 次に、$mathbfC2mod$がドメインリフト可能であることを証明する。
• 参考スコア（独自算出の注目度）: 14.737223920007722
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Weighted first-order model counting (WFOMC) is a central task in lifted probabilistic inference: It asks for the weighted sum of all models of a first-order sentence over a finite domain. A long line of work has identified domain-liftable fragments of first-order logic, that is, syntactic classes for which WFOMC can be solved in time polynomial in the domain size. Among them, the two-variable fragment with counting quantifiers, $\mathbf{C}^2$, is one of the most expressive known liftable fragments. Existing algorithms for $\mathbf{C}^2$, however, establish tractability through multi-stage reductions that eliminate counting quantifiers via cardinality constraints, which introduces substantial practical overhead as the domain size grows. In this paper, we introduce IncrementalWFOMC3, a lifted algorithm for WFOMC on $\mathbf{C}^2$ and its modulo counting extension, $\mathbf{C}^2_{\text{mod}}$. Instead of relying on reduction techniques, IncrementalWFOMC3 operates directly on a Scott normal form that retains counting quantifiers throughout inference. This direct treatment yields two main results. First, we derive a tighter data-complexity bound for WFOMC in $\mathbf{C}^2$, reducing the degree of the polynomial from quadratic to linear in the counting parameters. Second, we prove that $\mathbf{C}^2_{\text{mod}}$ is domain-liftable, extending tractability from $\mathbf{C}^2$ to a richer fragment with native modulo counting support. Finally, our empirical evaluation shows that IncrementalWFOMC3 delivers orders-of-magnitude runtime improvements and better scalability than both existing WFOMC algorithms and state-of-the-art propositional model counters.
• Abstract（参考訳）: 重み付き一階モデルカウント(WFOMC)は、昇降確率推論における中心的なタスクである: 有限領域上の一階文の全モデルの重み付き和を求める。 長い研究の行は、一階述語論理のドメインリフト可能な断片、すなわち、WFOMCを時間多項式でドメインサイズで解くことができる構文クラスを特定した。 中でも、数量化子を持つ2変数のフラグメントである$\mathbf{C}^2$は、最も表現力のある持ち上げ可能なフラグメントの1つである。 しかし、$\mathbf{C}^2$ の既存のアルゴリズムは、数量化器を濃度制約によって排除する多段階還元によってトラクタビリティを確立する。 本稿では、$\mathbf{C}^2$上のWFOMCのリフトアルゴリズムであるIncrementalWFOMC3とそのモジュロカウント拡張である$\mathbf{C}^2_{\text{mod}}$を紹介する。 インクリメンタルWFOMC3は減算技術に頼る代わりに、スコット正規形式で直接動作し、推論全体を通して数量化子を保持する。 この直接的な治療は2つの主要な結果をもたらす。 まず、WFOMCに対して$\mathbf{C}^2$でより厳密なデータ複雑度を導出する。 次に、$\mathbf{C}^2_{\text{mod}}$がドメインリフト可能であることを証明する。 最後に、IncrementalWFOMC3は、既存のWFOMCアルゴリズムと最先端の命題モデルカウンタの両方よりも、オーダー・オブ・マグニチュード・ランタイムの改善とスケーラビリティを提供することを示す。

関連論文リスト

• Tractable Weighted First-Order Model Counting with Bounded Treewidth Binary Evidence [2.5551288018371157]
  重み付き一階述語モデルカウント問題(WFOMC)は、与えられた一階述語論理文のモデルの重み付き和を計算することを要求する。 本稿では,WFOMCを2本の木の破片に対して演算するアルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2025-11-12T10:12:39Z)
• Effective Policy Learning for Multi-Agent Online Coordination Beyond Submodular Objectives [64.16056378603875]
  マルチエージェントオンライン協調問題に対する2つのポリシー学習アルゴリズムを提案する。 1つめの textttMA-SPL は MA-OC 問題に対して最適な$(fracce)$-approximation を達成することができる。 第2のオンラインアルゴリズムである textttMA-MPL は同じ近似比を同時に維持できる。
  論文  参考訳（メタデータ） (2025-09-26T17:16:34Z)
• Weighted First Order Model Counting for Two-variable Logic with Axioms on Two Relations [5.843053614714943]
  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。
  論文  参考訳（メタデータ） (2025-08-15T14:54:17Z)
• 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)
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials [93.59919600451487]
  多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。 1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。 テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
  論文  参考訳（メタデータ） (2022-11-10T00:40:37Z)
• 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)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• Higher-order Derivatives of Weighted Finite-state Machines [68.43084108204741]
  本研究では、重み付き有限状態機械の正規化定数に関する高次微分の計算について検討する。 文献に記載されていないすべての順序の導関数を評価するための一般アルゴリズムを提案する。 我々のアルゴリズムは以前のアルゴリズムよりもはるかに高速である。
  論文  参考訳（メタデータ） (2021-06-01T19:51:55Z)
• Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint [75.85952446237599]
  修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。 最適なデータ依存上界を導出する。 また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
  論文  参考訳（メタデータ） (2020-08-12T15:40:21Z)

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

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