論文の概要: An ExpTime Upper Bound for $\mathcal{ALC}$ with Integers (Extended
Version)
- arxiv url: http://arxiv.org/abs/2006.02078v1
- Date: Wed, 3 Jun 2020 07:28:39 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-25 18:21:17.099371
- Title: An ExpTime Upper Bound for $\mathcal{ALC}$ with Integers (Extended
Version)
- Title（参考訳）: 整数付き$\mathcal{ALC}$のExpTimeアッパーバウンド(拡張バージョン)
- Authors: Nadia Labai, Magdalena Ortiz, Mantas \v{S}imkus
- Abstract要約: 比較が可能な豊富な整数領域を持つ$mathcalALC$の拡張について検討する。
単一指数時間で自動理論技術を用いて一貫性を解くことができることを示す。
- 参考スコア（独自算出の注目度）: 7.831410227443102
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Concrete domains, especially those that allow to compare features with
numeric values, have long been recognized as a very desirable extension of
description logics (DLs), and significant efforts have been invested into
adding them to usual DLs while keeping the complexity of reasoning in check.
For expressive DLs and in the presence of general TBoxes, for standard
reasoning tasks like consistency, the most general decidability results are for
the so-called $\omega$-admissible domains, which are required to be dense.
Supporting non-dense domains for features that range over integers or natural
numbers remained largely open, despite often being singled out as a highly
desirable extension. The decidability of some extensions of $\mathcal{ALC}$
with non-dense domains has been shown, but existing results rely on powerful
machinery that does not allow to infer any elementary bounds on the complexity
of the problem. In this paper, we study an extension of $\mathcal{ALC}$ with a
rich integer domain that allows for comparisons (between features, and between
features and constants coded in unary), and prove that consistency can be
solved using automata-theoretic techniques in single exponential time, and thus
has no higher worst-case complexity than standard $\mathcal{ALC}$. Our upper
bounds apply to some extensions of DLs with concrete domains known from the
literature, support general TBoxes, and allow for comparing values along paths
of ordinary (not necessarily functional) roles.
- Abstract（参考訳）: 具体的なドメイン、特に特徴と数値を比較することを可能にするドメインは、長い間、記述論理(dls)の非常に望ましい拡張として認識されてきた。
表現力のあるDLや一般的なTBoxの存在下では、一貫性のような標準的な推論タスクにおいて、最も一般的な決定可能性の結果は、高密度でなければならないいわゆる$\omega$-admissibleドメインである。
整数や自然数にまたがる機能に対するナンセンスなドメインのサポートは、しばしば非常に望ましい拡張として除外されるにもかかわらず、ほとんどオープンのままであった。
非密度領域を持つ$\mathcal{ALC}$のいくつかの拡張の決定性は示されているが、既存の結果は問題の複雑さに基本的な境界を推測できない強力な機械に依存している。
本稿では,機能比較を可能にするリッチ整数領域を持つ$\mathcal{alc}$の拡張について検討し,単一指数時間でオートマトン理論を用いて一貫性を解決できることを証明し,標準$\mathcal{alc}$よりも最悪の場合の複雑性をもたないことを示す。
我々の上限は、文献から知られている具体的なドメインを持つdlsの拡張に適用され、一般的なtboxをサポートし、通常の(必ずしも機能的ではない)役割の経路に沿って値を比較することができる。
関連論文リスト
- MathGAP: Out-of-Distribution Evaluation on Problems with Arbitrarily Complex Proofs [80.96119560172224]
大規模言語モデル(LLM)は、高い精度で算術語問題を解くことができるが、訓練された言語よりも複雑な問題にどのように一般化するかは、ほとんど分かっていない。
本研究では、任意に複雑な算術証明問題に対する LLM の評価フレームワーク、MathGAP を提案する。
論文 参考訳（メタデータ） (2024-10-17T12:48:14Z) - Complexity-Theoretic Implications of Multicalibration [8.315801422499863]
多精度予測器はより強い条件を満たす:それらはコレクションの各セットで校正される。
この複雑性理論的正則性レンマは、異なる領域に影響を及ぼすことが知られている。
すべての函数(その硬さによらず)が不随伴なハードコア集合の小さな集合を持つことが示される。
論文 参考訳（メタデータ） (2023-12-28T18:53:21Z) - Hierarchies for Semidefinite Optimization in
$\mathcal{C}^\star$-Algebras [0.0]
本稿では,$mathcalCstar$-algebras上での一般コーンプログラムの有限次元緩和法を提案する。
我々は NPA のような一般化された問題に対するよく知られた階層性やラッサール階層、一般 SDP の拡張対称性の低下を示す。
論文 参考訳（メタデータ） (2023-09-25T09:01:30Z) - Real-time Regular Expression Matching [65.268245109828]
本稿では,有限状態オートマトン,正規表現マッチング,パターン認識,指数的爆破問題について述べる。
本稿では,正規言語の複雑なクラスに対する指数的爆破問題に対する理論的およびハードウェア的解法を提案する。
論文 参考訳（メタデータ） (2023-08-20T09:25:40Z) - Generalization Bounds for Stochastic Gradient Descent via Localized
$\varepsilon$-Covers [16.618918548497223]
本稿では,SGDの軌道に局在する新しい被覆手法を提案する。
このローカライゼーションは、境界数によって測定されるアルゴリズム固有のクラスタリングを提供する。
これらの結果は様々な文脈で導き出され、既知の最先端のラベルレートが向上する。
論文 参考訳（メタデータ） (2022-09-19T12:11:07Z) - Neural Set Function Extensions: Learning with Discrete Functions in High
Dimensions [63.21838830509772]
集合関数を低次元連続領域に拡張するためのフレームワークを開発する。
我々のフレームワークは、よく知られた拡張を特殊ケースとして仮定する。
我々は低次元ニューラルネットワークボトルネックを高次元空間における表現に変換する。
論文 参考訳（メタデータ） (2022-08-08T10:58:02Z) - Noncommutative extensions of parameters in the asymptotic spectrum of
graphs [0.0]
任意の函数は、類似した性質を持つ非可換グラフへの無数の拡張を持つか、あるいはそのような拡張を全く持たないことを示す。
特に、Lov'asz数に対する許容指数の集合、射影階数、複素数上で有界な分数Haemerは極大である。
論文 参考訳（メタデータ） (2022-07-21T13:55:12Z) - Learning Aggregation Functions [78.47770735205134]
任意の濃度の集合に対する学習可能なアグリゲータであるLAF(Learning Aggregation Function)を紹介する。
半合成および実データを用いて,LAFが最先端の和(max-)分解アーキテクチャより優れていることを示す実験を報告する。
論文 参考訳（メタデータ） (2020-12-15T18:28:53Z) - Finite-Function-Encoding Quantum States [52.77024349608834]
任意の$d$値論理関数を符号化する有限関数符号化(FFE)を導入する。
それらの構造的特性について検討する。
論文 参考訳（メタデータ） (2020-12-01T13:53:23Z) - On Function Approximation in Reinforcement Learning: Optimism in the
Face of Large State Spaces [208.67848059021915]
強化学習のコアにおける探索・探索トレードオフについて検討する。
特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。
私たちの後悔の限界はエピソードの数とは無関係です。
論文 参考訳（メタデータ） (2020-11-09T18:32:22Z) - Generalized Score Matching for General Domains [6.982738885923204]
一般領域で支持される密度関数の推定は、データが実空間の固有部分集合に自然に制限されているときに発生する。
我々は、非常に一般的なドメインのクラスでサポートされている密度に対応するスコアマッチングの自然な一般化を提供する。
論文 参考訳（メタデータ） (2020-09-24T00:53:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。