論文の概要: Minimal Model Reasoning in Description Logics: Don't Try This at Home!

• arxiv url: http://arxiv.org/abs/2508.05350v1
• Date: Thu, 07 Aug 2025 12:56:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-08 18:59:39.8629
• Title: Minimal Model Reasoning in Description Logics: Don't Try This at Home!
• Title（参考訳）: 記述論理における最小モデル推論: 家で試すな!
• Authors: Federica Di Stefano, Quentin Manière, Magdalena Ortiz, Mantas Šimkus,
• Abstract要約: 我々は、$mathcalEL$に対して、最小限のモデルにおける概念が既に決定不可能であることを示します。 決定性を取り戻すため、TBoxに非循環条件を課し、最悪のケースの複雑さを倍指数時間以下に抑える。 そこでは,DL-Lite$_textcore$で肯定的な結果が得られた。
• 参考スコア（独自算出の注目度）: 4.387337528923525
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Reasoning with minimal models has always been at the core of many knowledge representation techniques, but we still have only a limited understanding of this problem in Description Logics (DLs). Minimization of some selected predicates, letting the remaining predicates vary or be fixed, as proposed in circumscription, has been explored and exhibits high complexity. The case of `pure' minimal models, where the extension of all predicates must be minimal, has remained largely uncharted. We address this problem in popular DLs and obtain surprisingly negative results: concept satisfiability in minimal models is undecidable already for $\mathcal{EL}$. This undecidability also extends to a very restricted fragment of tuple-generating dependencies. To regain decidability, we impose acyclicity conditions on the TBox that bring the worst-case complexity below double exponential time and allow us to establish a connection with the recently studied pointwise circumscription; we also derive results in data complexity. We conclude with a brief excursion to the DL-Lite family, where a positive result was known for DL-Lite$_{\text{core}}$, but our investigation establishes ExpSpace-hardness already for its extension DL-Lite$_{\text{horn}}$.
• Abstract（参考訳）: 最小限のモデルによる推論は、常に多くの知識表現技術の中核にあるが、説明論理学(DL)では、この問題について限定的な理解しか得られていない。 いくつかの選択された述語を最小化し、残りの述語が変化したり、固定されるようにすることは、概説で提案されているように、探索され、高い複雑性を示す。 すべての述語の拡張が最小でなければならない 'pure' 最小のモデルの場合、ほとんど無チャートのままである。 最小モデルにおける概念満足度はすでに$\mathcal{EL}$に対して決定不可能である。 この決定不可能性は、タプル生成依存関係の非常に制限された断片にまで拡張される。 決定可能性を取り戻すために、我々はTBoxに非循環条件を課し、最悪の場合の複雑性を2倍指数時間以下に抑え、最近研究された点周条件との接続を確立する。 DL-Lite$_{\text{core}}$に対して肯定的な結果が知られているDL-Liteファミリーへの簡単な遠足で結論を下すが、我々の調査は拡張DL-Lite$_{\text{horn}}$に対してExpSpace-hardnessをすでに確立している。

関連論文リスト

• A Fine-Grained Complexity View on Propositional Abduction -- Algorithms and Lower Bounds [6.6362553223890535]
  我々は、見過ごされているように見えるが自然なパラメータ n の下で、難解な誘引問題の複雑さを分析する。 SigmaP$ と NP- および coNP-完全 フラグメントに対していくつかの正の値が得られる。 我々はこれを低い境界で補い、多くのフラグメントは(強い)指数時間仮説の下で改善を除外する。
  論文  参考訳（メタデータ） (2025-05-15T11:56:19Z)
• 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)
• Identifying General Mechanism Shifts in Linear Causal Representations [58.6238439611389]
  我々は,未知の潜在因子の線形混合を観測する線形因果表現学習環境について考察する。 近年の研究では、潜伏要因の復元や、それに基づく構造因果モデルの構築が可能であることが示されている。 非常に穏やかな標準仮定の下では、シフトしたノードの集合を識別することが可能である。
  論文  参考訳（メタデータ） (2024-10-31T15:56:50Z)
• Lower Bounds for Learning in Revealing POMDPs [88.23337313766355]
  本稿では, 難易度の高い環境下での強化学習(RL)の基本的限界について検討する。 Emphmulti-steping POMDPs に対して、潜伏状態空間依存はサンプル複雑性において少なくとも$Omega(S1.5)$であることを示す。
  論文  参考訳（メタデータ） (2023-02-02T18:59:30Z)
• Expected Worst Case Regret via Stochastic Sequential Covering [14.834625066344582]
  我々は、既知のミニマックス後悔を一般化し包含する、予想される最悪のミニマックス後悔の概念を導入する。 そのようなミニマックスの後悔に対して、我々は上大域シーケンシャル被覆という新しい概念を通じて厳密な境界を確立する。 対数損失と一般に混合可能な損失に対する最小限の後悔に対する厳密な境界を確立することで,本手法の有効性を実証する。
  論文  参考訳（メタデータ） (2022-09-09T17:31:46Z)
• Near-Optimal Sample Complexity Bounds for Constrained MDPs [25.509556551558834]
  減算CMDPにおける準最適政策を学習するために,サンプルの複雑さを極小値と下位値で表す。 CMDPの学習は,少ない制約違反を許す場合と同等に容易であるが,制約違反を要求しない場合には本質的に困難であることを示す。
  論文  参考訳（メタデータ） (2022-06-13T15:58:14Z)
• Expressivity of Planning with Horn Description Logic Ontologies (Technical Report) [12.448670165713652]
  我々は、記述論理(DL)オントロジーを計画することで定式化されたオープンワールドな状態制約に対処する。 派生述語を用いた標準PDDLへの新しいコンパイル方式を提案する。 提案手法は,DLで計画する既存のベンチマークよりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-03-17T14:50:06Z)
• A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs [117.82903457289584]
  有限水平マルコフ決定過程(MDPs)における新たな問題依存的下界を導出する。 我々の下界は一般の場合よりもかなり小さく、最小の作用ギャップでスケールしないことが示される。 この最後の結果($poly(H)$の条件で、$H$は地平線である)は、楽観的なアルゴリズムのポリシーギャップに基づいて、後悔の意を表すことによって達成可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-24T13:46:09Z)
• Bilinear Classes: A Structural Framework for Provable Generalization in RL [119.42509700822484]
  Bilinear Classesは強化学習の一般化を可能にする新しい構造フレームワークである。 このフレームワークは、サンプルの複雑さが達成可能な、ほとんどすべての既存のモデルを取り込んでいる。 我々の主な成果は、双線形クラスのためのサンプル複雑性を持つRLアルゴリズムである。
  論文  参考訳（メタデータ） (2021-03-19T16:34:20Z)
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection [71.9765117768556]
  本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。 この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。 本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
  論文  参考訳（メタデータ） (2020-09-04T04:10:39Z)

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

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