Fugu-MT 論文翻訳(概要): Containment in Monadic Disjunctive Datalog, MMSNP, and Expressive Description Logics

論文の概要: Containment in Monadic Disjunctive Datalog, MMSNP, and Expressive Description Logics

arxiv url: http://arxiv.org/abs/2010.11842v1
Date: Thu, 22 Oct 2020 16:25:00 GMT
ステータス: 処理完了
システム内更新日: 2022-10-04 07:35:18.229223
Title: Containment in Monadic Disjunctive Datalog, MMSNP, and Expressive Description Logics
Title（参考訳）: Monadic Disjunctive Datalog, MMSNPおよびExpressive Description Logicsにおける包含
Authors: Pierre Bourhis and Carsten Lutz
Abstract要約: 我々は,MDDLog (Monadic Disjunctive Datalog) と MMSNP (制約満足度問題の論理的一般化) と Ontology-mediated query (OMQs) の3つの密接に関連する形式におけるクエリの包摂について検討した。 2NEXPTIME完全性を証明し、この結果をモナディックな解離データログとOMQに拡張する。
参考スコア（独自算出の注目度）: 17.17606390337468
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We study query containment in three closely related formalisms: monadic disjunctive Datalog (MDDLog), MMSNP (a logical generalization of constraint satisfaction problems), and ontology-mediated queries (OMQs) based on expressive description logics and unions of conjunctive queries. Containment in MMSNP was known to be decidable due to a result by Feder and Vardi, but its exact complexity has remained open. We prove 2NEXPTIME-completeness and extend this result to monadic disjunctive Datalog and to OMQs.
Abstract（参考訳）: 本稿では,MDDLog (Monadic Disjunctive Datalog) と MMSNP (MMSNP) とオントロジーによるクエリ (OMQs) の3つの関連する形式について,表現的記述論理と接続的クエリの結合に基づいて検討する。 mmsnpの封じ込めはfederとvardiによって決定可能であることが知られていたが、正確な複雑さは残っていない。 2NEXPTIME完全性を証明し、この結果をモナディックな解離データログとOMQに拡張する。

関連論文リスト

Data Complexity in Expressive Description Logics With Path Expressions [7.832189413179361]
本稿では,表現的記述論理ZOIQ(ALCHb Self reg OIQ)の準フォレスト上でのデータ複雑性について検討する。これにより、ZOIQの決定可能なフラグメントに対するデータ複雑性の展望が完成し、OWL2(SRファミリー)の決定可能なフラグメントに関する既知の結果が改善される。
論文参考訳（メタデータ） (2024-06-11T09:37:51Z)
Neuro-Symbolic Integration Brings Causal and Reliable Reasoning Proofs [95.07757789781213]
LLMの複雑な推論には2行のアプローチが採用されている。 1行の作業は様々な推論構造を持つLLMを誘導し、構造出力は自然に中間推論ステップと見なすことができる。他方の行では、LCMのない宣言的解法を用いて推論処理を行い、推論精度は向上するが、解法のブラックボックスの性質により解釈性に欠ける。具体的には,Prologインタプリタが生成した中間検索ログにアクセスし,人間可読推論に解釈可能であることを示す。
論文参考訳（メタデータ） (2023-11-16T11:26:21Z)
Modeling Hierarchical Reasoning Chains by Linking Discourse Units and Key Phrases for Reading Comprehension [80.99865844249106]
本稿では,論理的推論の基盤として,対話レベルと単語レベルの両方の文脈を扱う総合グラフネットワーク(HGN)を提案する。具体的には、ノードレベルの関係とタイプレベルの関係は、推論過程におけるブリッジと解釈できるが、階層的な相互作用機構によってモデル化される。
論文参考訳（メタデータ） (2023-06-21T07:34:27Z)
MURMUR: Modular Multi-Step Reasoning for Semi-Structured Data-to-Text Generation [102.20036684996248]
多段階推論を用いた半構造化データからテキストを生成するための,ニューロシンボリックなモジュラーアプローチであるMURMURを提案する。 WebNLG や LogicNLG のような2つのデータ・テキスト生成タスクについて実験を行った。
論文参考訳（メタデータ） (2022-12-16T17:36:23Z)
Maieutic Prompting: Logically Consistent Reasoning with Recursive Explanations [71.2950434944196]
ノイズや一貫性のない言語モデルでさえも問題に対する正しい答えを推測するMaieutic Promptingを開発する。 Maieutic Promptingは最先端のプロンプト法よりも最大20%精度が高い。
論文参考訳（メタデータ） (2022-05-24T06:36:42Z)
LogicSolver: Towards Interpretable Math Word Problem Solving with Logical Prompt-enhanced Learning [135.8654475934613]
我々はまず,11,495MWPからなる高品質MWPデータセットInterMWPを構築した。本稿では論理的プロンプトと解釈を用いた新しい手法であるLogicrを提案する。これらの改良されたセマンティック表現により、我々のLogicrは、生成された解表現に従って対応する解表現と解釈可能な知識を生成する。
論文参考訳（メタデータ） (2022-05-17T11:01:52Z)
On the Relationship between Shy and Warded Datalog+/- [3.4696964555947694]
DatalogEは、存在量化によるDatalogの拡張である。知識グラフの現代的な応用に適しているが、そのような言語に対するクエリ応答(QA)は一般には決定不可能であることが知られている。異なる断片が出現し、表現力とQAの計算複雑性のバランスをとるDatalogEに構文的制限が導入された。
論文参考訳（メタデータ） (2022-02-13T11:24:22Z)
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)
VQA-LOL: Visual Question Answering under the Lens of Logic [58.30291671877342]
画像に関する疑問に答えるように訓練された視覚的質問応答システムが,複数の質問の論理的構成に答えられるかどうかを検討する。本稿では,VQAデータセットをベンチマークとして拡張し,論理的構成や言語的変換を含む質問を行う。本稿では,論理的結合性を理解するために質問注意と論理意図を用いたLOLモデルと,新しいFr'echet-Compatibility Lossを提案する。
論文参考訳（メタデータ） (2020-02-19T17:57:46Z)

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