論文の概要: Fitting Description Logic Ontologies to ABox and Query Examples

• arxiv url: http://arxiv.org/abs/2508.08007v1
• Date: Mon, 11 Aug 2025 14:11:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-12 21:23:29.135805
• Title: Fitting Description Logic Ontologies to ABox and Query Examples
• Title（参考訳）: ABoxとクエリの例に記述論理オントロジーを適用する
• Authors: Maurice Funk, Marvin Grosser, Carsten Lutz,
• Abstract要約: 記述ロジックは$mathcalALC$と$mathcalALCI$をオントロジー言語と様々なクエリ言語とみなす。 得られた全ての適合問題に対して、有効な特徴付けを提供し、適合オントロジーが存在するかどうかを決定するための計算複雑性を決定する。 この問題は、AQとフルCQには$ Small CONP$、CQとUCQには$2E Small XPTsmall IME$-completeであることが判明した。
• 参考スコア（独自算出の注目度）: 9.25388936622029
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study a fitting problem inspired by ontology-mediated querying: given a collection of positive and negative examples of the form $(\mathcal{A},q)$ with $\mathcal{A}$ an ABox and $q$ a Boolean query, we seek an ontology $\mathcal{O}$ that satisfies $\mathcal{A} \cup \mathcal{O} \vDash q$ for all positive examples and $\mathcal{A} \cup \mathcal{O}\not\vDash q$ for all negative examples. We consider the description logics $\mathcal{ALC}$ and $\mathcal{ALCI}$ as ontology languages and a range of query languages that includes atomic queries (AQs), conjunctive queries (CQs), and unions thereof (UCQs). For all of the resulting fitting problems, we provide effective characterizations and determine the computational complexity of deciding whether a fitting ontology exists. This problem turns out to be ${\small CO}NP$ for AQs and full CQs and $2E{\small XP}T{\small IME}$-complete for CQs and UCQs. These results hold for both $\mathcal{ALC}$ and $\mathcal{ALCI}$.
• Abstract（参考訳）: オントロジーを媒介とするクエリに着想を得た適合問題を研究する: $(\mathcal{A},q)$ with $\mathcal{A}$ an ABox and $q$ a Boolean query, we seek a ontology $\mathcal{O}$ that satisfies $\mathcal{A} \cup \mathcal{O} \vDash q$ for all positive example and $\mathcal{A} \cup \mathcal{O}\not\vDash q$ for all negative example。 我々は、オントロジー言語として$\mathcal{ALC}$と$\mathcal{ALCI}$と、原子クエリ(AQ)、結合クエリ(CQ)、それらの結合(UCQ)を含む様々なクエリ言語について考察する。 得られた全ての適合問題に対して、有効な特徴付けを提供し、適合オントロジーが存在するかどうかを決定するための計算複雑性を決定する。 この問題は、AQ と完全 CQ に対して${\small CO}NP$、CQ と UCQ に対して $2E{\small XP}T{\small IME}$-complete であることが判明した。 これらの結果は $\mathcal{ALC}$ と $\mathcal{ALCI}$ の両方に対して成り立つ。

関連論文リスト

• CSPs with Few Alien Constraints [12.330326247154968]
  CSP$(mathcalA cup mathcalB)$ ここで$mathcalA$は構造、$mathcalB$は異方構造である。 我々は、以前分類の試みを免れたいくつかのよく研究された問題に対して、接続を確立し、転送可能な複雑性結果を得る。
  論文  参考訳（メタデータ） (2024-08-23T08:34:13Z)
• Quantum Sabotage Complexity [0.7812210699650152]
  ここでは$mathsfQ(f_mathsfsab)$を示し、$f_mathsfsab$の量子クエリ複雑性を示す。 f$がインデックス関数であるとき、$mathsfQ(f_mathsfsab)=Theta(sqrtmathsfsab)$は、$mathsfQ(f_mathsfsab)=Theta(sqrtmathsf)の可能性を除外する。
  論文  参考訳（メタデータ） (2024-08-22T17:57:58Z)
• Statistical Query Lower Bounds for Learning Truncated Gaussians [43.452452030671694]
  この問題のSQアルゴリズムの複雑さは、$dmathrmpoly (1/epsilon)$であり、クラス$mathcalC$が単純である場合でも、$mathrmpoly(d/epsilon)が情報理論的に十分であることを示す。
  論文  参考訳（メタデータ） (2024-03-04T18:30:33Z)
• SQ Lower Bounds for Learning Bounded Covariance GMMs [46.289382906761304]
  P= sum_i=1k w_i MathcalN(boldsymbol mu_i,mathbf Sigma_i)$ という形で、分離されたガウスの混合を $mathbbRd$ で学習することに焦点を当てる。 この問題に対する統計的クエリ(SQ)アルゴリズムは、少なくともdOmega (1/epsilon)$の複雑さを必要とすることを証明している。
  論文  参考訳（メタデータ） (2023-06-22T17:23:36Z)
• A Fast Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [55.2480439325792]
  多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。 本稿では,差分に基づく探索法 (CombGapE) アルゴリズムを提案する。 我々は,CombGapEアルゴリズムが,合成データセットと実世界のデータセットの両方において,既存の手法を大幅に上回っていることを数値的に示す。
  論文  参考訳（メタデータ） (2023-06-15T15:37:31Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
  論文  参考訳（メタデータ） (2022-03-17T23:52:08Z)
• Linear Bandits on Uniformly Convex Sets [88.3673525964507]
  線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。 2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
  論文  参考訳（メタデータ） (2021-03-10T07:33:03Z)
• Proving Non-Inclusion of B\"uchi Automata based on Monte Carlo Sampling [19.09848789158933]
  B"uchiautoa non-inclusion $mathcalL(mathcalA) notsubseteq mathcalL(mathcalB)$を証明するための具体的なアルゴリズムを提案する。 $mathsfIMC2$は、B"uchiautoaのインクルージョンに対する反例を見つける高速で信頼性の高い方法である。
  論文  参考訳（メタデータ） (2020-07-05T10:17:02Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)

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

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