論文の概要: Solving Combinatorial Counting Problems with Weighted First-Order Model Counting

• arxiv url: http://arxiv.org/abs/2605.24845v1
• Date: Sun, 24 May 2026 03:29:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-26 19:50:18.474938
• Title: Solving Combinatorial Counting Problems with Weighted First-Order Model Counting
• Title（参考訳）: 重み付き1次モデル計数による組合せ数問題の解法
• Authors: Yuanhong Wang, Juhua Pu, Yuxu Zhou, Yuyi Wang, Ondřej Kuželka,
• Abstract要約: 我々は,すべてのCofolaプログラムを適切に定義されたカウント問題にマッピングする型付き言語であるCofola(LAnguage with First Preserving logic)を提案する。 Cofolaは簡潔な仕様と、実用的なエンドツーエンドの均一な解決パイプラインを生成する。
• 参考スコア（独自算出の注目度）: 2.2680525506361717
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Combinatorial counting problems pervade artificial intelligence, statistics, and discrete mathematics. Whether the task is enumerating subsets, multisets, permutations, partitions, or compositions under structural and arithmetic constraints, solving it remains a stubbornly manual exercise. Closed-form derivations are powerful but brittle, while naive encodings to propositional model counting or constraint satisfaction destroy the exchangeability that makes counting tractable in the first place. We present Cofola (COmbinatorial counting LAnguage with First-Order logic), a typed declarative language whose primitives are the combinatorial objects that recur in everyday counting questions, including sets, bags, tuples, sequences, circles, partitions, and compositions, together with natural relational and arithmetic constraints over them. A denotational semantics maps every Cofola program to a well-defined combinatorial counting problem, and a three-phase compilation pipeline (preprocessing, decomposition, and symmetry-preserving encoding) reduces this problem to a weighted first-order model counting (WFOMC) instance augmented with coefficient-extraction constraints. To stay inside known domain-liftable fragments whenever possible, the encoding groups indistinguishable entities, breaks the symmetry of unordered groupings lexicographically, and encodes sequences and circles via order axioms. On a suite of representative combinatorial counting problems, ranging from textbook math problems to multi-object scenarios that the closest prior framework cannot express, Cofola produces concise specifications and a uniform solving pipeline that is practical end-to-end.
• Abstract（参考訳）: 組合せカウント問題は人工知能、統計学、離散数学に及んでいる。 タスクが部分集合、多重集合、置換、分割、あるいは構成を構造的および算術的制約の下で列挙しているかどうかに関わらず、この課題は頑固に手作業で解決される。 クローズドフォームの導出は強力だが不安定であり、命題モデルの数え上げや制約満足度への素早いエンコーディングは、そもそも数え上げが難しくなる交換性を損なう。 コフォラ(Cofola、LAnguage with First-Order logic、LAnguage with LAnguage with First-Order logic)は、自然関係とそれらの上の算術的制約とともに、集合、バッグ、タプル、列、円、分割、合成を含む、日常的な数え上げ問題に再帰する組合せ的オブジェクトをプリミティブとする、型付き宣言言語である。 意味論的意味論は、すべてのコフォラプログラムをよく定義された組合せカウント問題にマッピングし、3相コンパイルパイプライン(前処理、分解、対称性保存エンコーディング)により、係数抽出制約を付加した重み付き1次モデルカウント(WFOMC)インスタンスにこの問題を還元する。 可能な限り、既知のドメインリフト可能なフラグメントの中に留まるために、符号化可能群は区別不能な実体を分解し、非順序のグルーピングの対称性を語彙的に破り、順序公理を介してシーケンスと円を符号化する。 教科書数学の問題から、最も近い先行フレームワークが表現できない多目的シナリオまで、一連の代表的組合せ数問題において、Cofolaは簡潔な仕様と、実用的なエンドツーエンドである一様解決パイプラインを生成する。

関連論文リスト

• Automatic Generation of Polynomial Symmetry Breaking Constraints [0.0]
  対称性ブレーカーとして使用できる不等式列をランダムに生成する手法を提案する。 この方法は任意の基底と整数プログラムに固有の記号置換のグループを入力として要求する。 単純な対称性ブレーカー、特に少数の変数と置換を組み合わせることで、作業時間を大幅に短縮することが判明した。
  論文  参考訳（メタデータ） (2026-02-09T06:05:10Z)
• Syzygy of Thoughts: Improving LLM CoT with the Minimal Free Resolution [59.39066657300045]
  CoT(Chain-of-Thought)は、問題を逐次ステップに分解することで、大きな言語モデル(LLM)の推論を促進する。 思考のシジー(Syzygy of Thoughts, SoT)は,CoTを補助的,相互関連的な推論経路を導入して拡張する新しいフレームワークである。 SoTはより深い論理的依存関係をキャプチャし、より堅牢で構造化された問題解決を可能にする。
  論文  参考訳（メタデータ） (2025-04-13T13:35:41Z)
• From Exponential to Polynomial Complexity: Efficient Permutation Counting with Subword Constraints [0.0]
  置換による異なる置換を数えることは、特に複数のサブワードを含む場合、分析における長年の課題である。 本稿では,置換による異なる置換を計算するための閉形式式を示す新しいフレームワークを提案する。 次に、新たな式を開発することにより、基本公式を複数のサブワードを扱うように拡張する。
  論文  参考訳（メタデータ） (2024-11-23T19:52:11Z)
• Synthesising Recursive Functions for First-Order Model Counting: Challenges, Progress, and Conjectures [12.47276164048813]
  1次モデルカウント(英: First-order model counting、FOMC)は、有限領域の1次論理において文のモデルを数えるように要求する計算問題である。 私たちは、典型的にドメイン再帰に伴う制限を緩和し、サイクルを含むかもしれない有向グラフを扱う。 これらの改良により、アルゴリズムはそれまで到達範囲を超えていた問題を数えるための効率的な解を見つけることができる。
  論文  参考訳（メタデータ） (2023-06-07T06:49:01Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。 これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。 本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
  論文  参考訳（メタデータ） (2022-11-16T18:59:54Z)
• Lifting Symmetry Breaking Constraints with Inductive Logic Programming [2.036811219647753]
  我々は、Symmetry Breaking Constraintsを解釈可能な一階制約の集合に引き上げる、Answer Set Programmingのための新しいモデル指向のアプローチを導入する。 実験は、我々のフレームワークがインスタンス固有のSBCから一般的な制約を学習できることを実証する。
  論文  参考訳（メタデータ） (2021-12-22T11:27:48Z)
• An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
  データから制約をマイニングするための一般的なフレームワークを提案する。 特に、構造化された出力予測の推論を整数線形プログラミング(ILP)問題とみなす。 提案手法は,9×9のスドクパズルの解法を学習し,基礎となるルールを提供することなく,例からツリー問題を最小限に分散させることが可能であることを示す。
  論文  参考訳（メタデータ） (2020-06-18T20:09:53Z)
• Consistency of a Recurrent Language Model With Respect to Incomplete Decoding [67.54760086239514]
  逐次言語モデルから無限長のシーケンスを受信する問題について検討する。 不整合に対処する2つの対策として、トップkと核サンプリングの一貫性のある変種と、自己終端の繰り返し言語モデルを提案する。
  論文  参考訳（メタデータ） (2020-02-06T19:56:15Z)

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

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