論文の概要: 2-ASP(Q) programs with weak constraints: Complexity and efficient implementation

• arxiv url: http://arxiv.org/abs/2605.27338v1
• Date: Tue, 26 May 2026 17:44:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-27 17:51:42.575077
• Title: 2-ASP(Q) programs with weak constraints: Complexity and efficient implementation
• Title（参考訳）: 制約が弱い2-ASP(Q)プログラム:複雑さと効率的な実装
• Authors: Andrea Cuteri, Giuseppe Mazzotta, Francesco Ricca,
• Abstract要約: 本稿では、2つの量化器と2-ASP(Q)wという弱い制約を持つASP(Q)プログラムのクラスに焦点を当てる。 理論的には、2-ASP(Q)wプログラムの主計算タスクの完全複雑性を特徴付ける。 実用面では、Casperシステムにおける計算(最適)定量化解集合の新たな戦略を導入する。
• 参考スコア（独自算出の注目度）: 4.760079434948197
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: ASP(Q) extends Answer Set Programming (ASP) with Quantifiers over answer sets. In this paper we focus on the class of ASP(Q) programs with two quantifiers and weak constraints, denoted as 2-ASP(Q)^w. 2-ASP(Q)^w is a practically relevant fragment of ASP(Q) that is expressive enough to capture optimization problems up to the class Delta_3^P. On the theoretical side, we provide a complete complexity characterization of the main computational tasks for 2-ASP(Q)^w programs, including tight completeness results and the analysis of nontrivial cases that have not been addressed in previous works. On the practical side, we introduce novel strategies for computing (optimal) quantified answer sets in the Casper system, that rely on a Counterexample-Guided Abstraction Refinement (CEGAR) technique tailored to ASP(Q). An experimental evaluation on hard benchmarks from different application domains shows that the proposed techniques are effective in practice.
• Abstract（参考訳）: ASP(Q) は Answer Set Programming (ASP) を拡張した。 本稿では、2つの量化器と2-ASP(Q)^wという弱い制約を持つASP(Q)プログラムのクラスに焦点を当てる。 2-ASP(Q)^w は ASP(Q) の実質的に関係する断片であり、最適化問題をクラス Delta_3^P まで捉えるのに十分な表現である。 理論的には、2-ASP(Q)^wプログラムの主計算タスクの完全複雑性を解析し、厳密な完全性の結果と、これまでの研究で未解決の非自明なケースの解析を行う。 実用面では、カスパーシステムにおいて、ASP(Q) に適合した反例誘導抽象リファインメント(CEGAR)技術に依存する、計算(最適)定量化解集合の新たな戦略を導入する。 異なるアプリケーション領域からのハードベンチマークを実験的に評価した結果,提案手法が実際に有効であることが示唆された。

関連論文リスト

• Counting Answer Sets of Disjunctive Answer Set Programs [28.739355096774155]
  本稿では,解法論理プログラムの解集合をカウントする新しいフレームワークSharpASP-SRを提案する。 SharpASP-SRは, 応答数が大きいインスタンスにおいて, 既存のカウンタを著しく上回っていることを示す。
  論文  参考訳（メタデータ） (2025-07-15T18:41:19Z)
• SPARE: Single-Pass Annotation with Reference-Guided Evaluation for Automatic Process Supervision and Reward Modelling [58.05959902776133]
  私たちはSingle-Passを紹介します。 Reference-Guided Evaluation (SPARE)は、効率的なステップごとのアノテーションを可能にする新しい構造化フレームワークである。 数学的推論(GSM8K, MATH)、マルチホップ質問応答(MuSiQue-Ans)、空間推論(SpaRP)にまたがる4つの多様なデータセットにおけるSPAREの有効性を実証する。 ProcessBenchでは、SPAREがデータ効率のよいアウト・オブ・ディストリビューションの一般化を実証し、トレーニングサンプルの$sim$16%しか使用していない。
  論文  参考訳（メタデータ） (2025-06-18T14:37:59Z)
• T$^2$: An Adaptive Test-Time Scaling Strategy for Contextual Question Answering [49.5489716597489]
  T$2$: Think-to-Thinkは質問の複雑さに基づいて推論深度を動的に適応する新しいフレームワークである。 T$2$は、質問を構造的要素に分解し、候補推論戦略と同じような例を生成し、これらの戦略を複数の基準に対して評価し、元の質問に最も適切な戦略を適用する、という4つの重要なステップで機能する。
  論文  参考訳（メタデータ） (2025-05-23T03:18:02Z)
• Enhancing Multi-Step Reasoning Abilities of Language Models through Direct Q-Function Optimization [49.362750475706235]
  強化学習(Reinforcement Learning, RL)は、大規模言語モデルを人間の好みと整合させ、複雑なタスクを遂行する能力を向上させる上で重要な役割を担っている。 反応生成過程をマルコフ決定プロセス(MDP)として定式化し,ソフトアクター・クリティック(SAC)フレームワークを用いて,言語モデルによって直接パラメータ化されたQ関数を最適化する,直接Q関数最適化(DQO)を提案する。 GSM8KとMATHという2つの数学問題解決データセットの実験結果から、DQOは従来の手法よりも優れており、言語モデルを整合させるための有望なオフライン強化学習手法として確立されている。
  論文  参考訳（メタデータ） (2024-10-11T23:29:20Z)
• Quantifying over Optimum Answer Sets [6.390468088226495]
  ASP(Q)はエレガントでコンパクトな方法でモデリングを符号化する方法を欠いている。 本稿では、コンポーネントプログラムが弱い制約を含むことができるASP(Q)の拡張を提案する。 様々なアプリケーションシナリオを通して、新しいフォーマリズムのモデリング機能を紹介します。
  論文  参考訳（メタデータ） (2024-08-14T17:53:13Z)
• An efficient solver for ASP(Q) [4.198045959496482]
  ASP(Q) は Answer Set Programming (ASP) を拡張し、階層構造からの問題の宣言的かつモジュラーなモデリングを可能にする。 本稿では,QBF における ASP(Q) プログラムのより効率的なエンコーディング手順と最適化されたエンコーディングの両方を特徴とする,qasp のアイデアに基づく新しい実装を提案する。
  論文  参考訳（メタデータ） (2023-05-17T07:59:53Z)
• Synergies between Disentanglement and Sparsity: Generalization and Identifiability in Multi-Task Learning [79.83792914684985]
  我々は,最大スパース基底予測器が不整合表現をもたらす条件を提供する新しい識別可能性の結果を証明した。 この理論的な結果から,両レベル最適化問題に基づくアンタングル表現学習の実践的アプローチを提案する。
  論文  参考訳（メタデータ） (2022-11-26T21:02:09Z)
• Efficient Knowledge Compilation Beyond Weighted Model Counting [7.828647825246474]
  このような問題に対する一般的なフレームワークとして,第2レベル代数モデルカウント (2AMC) を導入している。 KC(Knowledge Compilation)に基づく第1レベルのテクニックは、変数順序制約を課すことで、特定の2AMCインスタンスに適応している。 2AMC問題の論理構造を利用して、これらの制約の一部を省略し、負の効果を制限できることが示される。
  論文  参考訳（メタデータ） (2022-05-16T08:10:40Z)
• Harnessing Incremental Answer Set Solving for Reasoning in Assumption-Based Argumentation [1.5469452301122177]
  仮定に基づく議論(ABA)は、中心的な構造化された議論形式である。 近年のASPの進歩により、ABAのNPハード推論タスクを効率的に解けるようになった。
  論文  参考訳（メタデータ） (2021-08-09T17:34:05Z)

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

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