Fugu-MT 論文翻訳(概要): Data Complexity in Expressive Description Logics With Path Expressions

論文の概要: Data Complexity in Expressive Description Logics With Path Expressions

arxiv url: http://arxiv.org/abs/2406.07095v1
Date: Tue, 11 Jun 2024 09:37:51 GMT
ステータス: 処理完了
システム内更新日: 2024-06-12 16:44:39.000774
Title: Data Complexity in Expressive Description Logics With Path Expressions
Title（参考訳）: 経路表現を伴う表現的記述論理におけるデータ複雑度
Authors: Bartosz Bednarczyk,
Abstract要約: 本稿では,表現的記述論理ZOIQ(ALCHb Self reg OIQ)の準フォレスト上でのデータ複雑性について検討する。これにより、ZOIQの決定可能なフラグメントに対するデータ複雑性の展望が完成し、OWL2(SRファミリー)の決定可能なフラグメントに関する既知の結果が改善される。
参考スコア（独自算出の注目度）: 7.832189413179361
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We investigate the data complexity of the satisfiability problem for the very expressive description logic ZOIQ (a.k.a. ALCHb Self reg OIQ) over quasi-forests and establish its NP-completeness. This completes the data complexity landscape for decidable fragments of ZOIQ, and reproves known results on decidable fragments of OWL2 (SR family). Using the same technique, we establish coNEXPTIME-completeness (w.r.t. the combined complexity) of the entailment problem of rooted queries in ZIQ.
Abstract（参考訳）: 擬似フォレスト上の非常に表現力豊かな記述論理ZOIQ(ALCHb Self reg OIQ)に対する満足度問題のデータ複雑性について検討し、NP完全性を確立する。これにより、ZOIQの決定可能なフラグメントに対するデータ複雑性の展望が完成し、OWL2(SRファミリー)の決定可能なフラグメントに関する既知の結果が改善される。同じ手法を用いて、ZIQ におけるルートクエリのentailment問題における coNEXPTIME-completeness (w.r.t.) を確立する。

関連論文リスト

RiTeK: A Dataset for Large Language Models Complex Reasoning over Textual Knowledge Graphs [12.846097618151951]
我々は,テキスト知識グラフ(RiTeK)を用いたLLMの複雑な推論のためのデータセットを開発し,広範なトポロジ的構造を網羅する。多様なトポロジ構造、注釈付き情報、複雑なテキスト記述を統合した現実的なユーザクエリを合成する。そこで我々はモンテカルロ木探索法 (CTS) を導入し, 特定のクエリに対してテキストグラフから関係経路情報を自動的に抽出する手法を提案する。
論文参考訳（メタデータ） (2024-10-17T19:33:37Z)
Seek and Solve Reasoning for Table Question Answering [49.006950918895306]
本稿では,大規模言語モデルの推論機能を活用して,表に基づく質問応答(TQA)の性能を向上させる。人間がTQAタスクを解く方法に触発されて、私たちはLLMにまず関連する情報を求め、質問に答えるように指示するSeek-and-seekパイプラインを提案します。本稿では,パイプラインから抽出した単一段TQA分解プロンプトについて述べる。
論文参考訳（メタデータ） (2024-09-09T02:41:00Z)
Meta Operator for Complex Query Answering on Knowledge Graphs [58.340159346749964]
我々は、異なる複雑なクエリタイプではなく、異なる論理演算子型が一般化性を向上させる鍵であると主張する。本稿では,メタ演算子を限られたデータで学習し,様々な複雑なクエリの演算子のインスタンスに適応するメタ学習アルゴリズムを提案する。実験結果から,メタオペレータの学習は,従来のCQAモデルやメタCQAモデルよりも効果的であることが示唆された。
論文参考訳（メタデータ） (2024-03-15T08:54:25Z)
Learning temporal formulas from examples is hard [2.8851756275902476]
本稿では,線形時間論理式(LTL)を例から学習する問題について検討する。学習問題は完全論理とほぼすべてのフラグメントに対してNP完全であることを示す。
論文参考訳（メタデータ） (2023-12-26T21:16:19Z)
When Do Program-of-Thoughts Work for Reasoning? [51.2699797837818]
本稿では,コードと推論能力の相関性を測定するために,複雑性に富んだ推論スコア(CIRS)を提案する。具体的には、抽象構文木を用いて構造情報をエンコードし、論理的複雑性を計算する。コードはhttps://github.com/zjunlp/EasyInstructのEasyInstructフレームワークに統合される。
論文参考訳（メタデータ） (2023-08-29T17:22:39Z)
Rethinking Complex Queries on Knowledge Graphs with Neural Link Predictors [58.340159346749964]
本稿では,証明可能な推論能力を備えた複雑なクエリを用いたエンドツーエンド学習を支援するニューラルシンボリック手法を提案する。これまでに検討されていない10種類の新しいクエリを含む新しいデータセットを開発する。提案手法は,新しいデータセットにおいて先行手法を著しく上回り,既存データセットにおける先行手法を同時に上回っている。
論文参考訳（メタデータ） (2023-04-14T11:35:35Z)
Successive Prompting for Decomposing Complex Questions [50.00659445976735]
最近の研究は、大規模言語モデル(LM)の機能を活用して、数ショットで複雑な質問応答を行う。そこでは、複雑なタスクを単純なタスクに繰り返し分解し、それを解決し、最終解を得るまでプロセスを繰り返します。我々の最良のモデル(逐次プロンプト付き)は、DROPデータセットの数ショットバージョンにおいて、5%の絶対F1の改善を実現します。
論文参考訳（メタデータ） (2022-12-08T06:03:38Z)
Query2Particles: Knowledge Graph Reasoning with Particle Embeddings [49.64006979045662]
本稿では,知識グラフにエッジを欠いた複雑な論理的クエリに応答するクエリ埋め込み手法を提案する。回答エンティティは、エンティティの埋め込みとクエリの埋め込みの類似性に応じて選択される。埋め込み空間上の様々な領域から多様な回答を検索するために,複雑なKGクエリ応答方法Q2Pを提案する。
論文参考訳（メタデータ） (2022-04-27T11:16:08Z)
From Conjunctive Queries to Instance Queries in Ontology-Mediated Querying [17.79631575141597]
本稿では,ALCファミリーの表現的記述論理と接続的クエリの(一意)に基づくオントロジーによるクエリについて考察する。この結果には,このような書き換えが可能なタイミングの正確な特徴と,書き換え可能性を決定するための厳密な複雑性境界が含まれている。
論文参考訳（メタデータ） (2020-10-22T16:40:59Z)
A tetrachotomy of ontology-mediated queries with a covering axiom [1.749935196721634]
我々の懸念は、標準的なデータベースクエリへの記述とそれらの最適な書き換えを介し、クエリに応答する際のデータ複雑さを効率的に決定することである。我々は、疎結合シロップ(d-シロップ)と呼ばれるブール共役型クエリに焦点を当てる。一部のd-シロップは指数的な大きさの分解能しか持たないが、そのうちのいくつかは二重指数サイズの正存在量書き換えと単帰的データログ書き換えのみである。
論文参考訳（メタデータ） (2020-06-07T14:47:07Z)
When is Ontology-Mediated Querying Efficient? [10.971122842236024]
関係データベース上でのオントロジーによるクエリの評価について検討する。 OMQ のクラスの特徴として,複雑な組み合わせによるトラクタブルなクラスを提供しています。また、与えられた OMQ が有界木幅の OMQ に等しいかどうかを決定する複雑さについても検討する。
論文参考訳（メタデータ） (2020-03-17T16:32:00Z)

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