Fugu-MT 論文翻訳(概要): Efficient TBox Reasoning with Value Restrictions using the $\mathcal{FL}

論文の概要: Efficient TBox Reasoning with Value Restrictions using the $\mathcal{FL}_{o}$wer reasoner

arxiv url: http://arxiv.org/abs/2107.12877v1
Date: Tue, 27 Jul 2021 15:20:53 GMT
ステータス: 処理完了
システム内更新日: 2021-07-28 14:45:03.970684
Title: Efficient TBox Reasoning with Value Restrictions using the $\mathcal{FL}_{o}$wer reasoner
Title（参考訳）: $\mathcal{FL}_{o}$wer 推論器を用いた値制限付き効率的なTBox推論
Authors: Franz Baader, Patrick Koopmann, Friedrich Michel, Anni-Yasmin Turhan, Benjamin Zarrie{\ss}
Abstract要約: $mathcalFL_o$wer は、拡張 $mathcalFL_bot$ of $mathcalFLFL$ with the top and bottom concept で記述できる。 $mathcalFL_o$wer は、拡張 $mathcalFL_bot$ of $mathcalFLFL$ で書かれた概念をトップとボトムで扱うこともできる。
参考スコア（独自算出の注目度）: 8.977167559181982
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: The inexpressive Description Logic (DL) $\mathcal{FL}_0$, which has conjunction and value restriction as its only concept constructors, had fallen into disrepute when it turned out that reasoning in $\mathcal{FL}_0$ w.r.t. general TBoxes is ExpTime-complete, i.e., as hard as in the considerably more expressive logic $\mathcal{ALC}$. In this paper, we rehabilitate $\mathcal{FL}_0$ by presenting a dedicated subsumption algorithm for $\mathcal{FL}_0$, which is much simpler than the tableau-based algorithms employed by highly optimized DL reasoners. Our experiments show that the performance of our novel algorithm, as prototypically implemented in our $\mathcal{FL}_o$wer reasoner, compares very well with that of the highly optimized reasoners. $\mathcal{FL}_o$wer can also deal with ontologies written in the extension $\mathcal{FL}_{\bot}$ of $\mathcal{FL}_0$ with the top and the bottom concept by employing a polynomial-time reduction, shown in this paper, which eliminates top and bottom. We also investigate the complexity of reasoning in DLs related to the Horn-fragments of $\mathcal{FL}_0$ and $\mathcal{FL}_{\bot}$.
Abstract（参考訳）: 非表現的記述論理(DL) $\mathcal{FL}_0$ は、その唯一の概念コンストラクタとして結合と値制限を持つが、$\mathcal{FL}_0$ w.r.t の推論が原因で不評であった。一般的なTBoxesはExpTime完全、すなわちかなり表現力のある論理である$\mathcal{ALC}$と同じくらい難しい。本稿では,高度に最適化されたDL推論器が使用するテーブルーベースアルゴリズムよりもはるかに単純な$\mathcal{FL}_0$に対して,専用の仮定アルゴリズムを提示することにより,$\mathcal{FL}_0$を修復する。実験の結果,新しいアルゴリズムの性能は,$\mathcal{FL}_o$wer推論器でプロトタイプ的に実装されており,高度に最適化された推論器と非常によく比較できることがわかった。また、$\mathcal{fl}_o$wer は拡張 $\mathcal{fl}_{\bot}$ of $\mathcal{fl}_0$ で記述されたオントロジーを扱うこともできる。また、$\mathcal{FL}_0$ および $\mathcal{FL}_{\bot}$ のホーンフラッグメントに関連する DL の推論の複雑さについても検討する。

関連論文リスト

Hamiltonian simulation for low-energy states with optimal time dependence [45.02537589779136]
低エネルギー部分空間内のハミルトン$H$の下で時間発展をシミュレートする作業を考える。我々は,$O(tsqrtlambdaGamma + sqrtlambda/Gammalog (1/epsilon))$クエリを,任意の$Gamma$に対するブロックエンコーディングに使用する量子アルゴリズムを提案する。
論文参考訳（メタデータ） (2024-04-04T17:58:01Z)
An Optimal Algorithm for Strongly Convex Min-min Optimization [79.11017157526815]
既存の最適な一階法には$mathcalO(sqrtmaxkappa_x,kappa_y log 1/epsilon)$nabla_x f(x,y)$と$nabla_y f(x,y)$の両方の計算が必要である。我々は$mathcalO(sqrtkappa_x log 1/epsilon)$nabla_x f(x,
論文参考訳（メタデータ） (2022-12-29T19:26:12Z)
Logarithmic Regret from Sublinear Hints [76.87432703516942]
自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
論文参考訳（メタデータ） (2021-11-09T16:50:18Z)
Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文参考訳（メタデータ） (2021-02-15T08:16:51Z)
An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文参考訳（メタデータ） (2020-08-24T06:50:57Z)
$Q$-learning with Logarithmic Regret [60.24952657636464]
楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
論文参考訳（メタデータ） (2020-06-16T13:01:33Z)
An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications [28.54236118020831]
本稿では,最適な$O(n log (kappa))$オアラーク評価を用いた新しい切削平面アルゴリズムを提案する。また、評価毎に$n2$の時間を改善できないため、実行時間が最適であることを示す。
論文参考訳（メタデータ） (2020-04-08T20:56:40Z)
Optimal Contextual Pricing and Extensions [32.152826900874075]
このアルゴリズムは$Omega(d log T)$ lower bound up to the $d log d$ additive factor。これらのアルゴリズムは、凸領域のスタイナー固有値を様々なスケールで有界化する新しい手法に基づいている。
論文参考訳（メタデータ） (2020-03-03T18:46:29Z)
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)

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

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