論文の概要: Exploring Non-Regular Extensions of Propositional Dynamic Logic with Description-Logics Features
- arxiv url: http://arxiv.org/abs/2307.09913v3
- Date: Mon, 8 Apr 2024 07:19:32 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-10 05:07:30.527327
- Title: Exploring Non-Regular Extensions of Propositional Dynamic Logic with Description-Logics Features
- Title（参考訳）: 記述-論理的特徴を持つ命題動的論理の非正規拡張の探索
- Authors: Bartosz Bednarczyk,
- Abstract要約: ALCを拡張した記述論理において、非正規経路表現が満足度チェックとクエリの決定可能性に与える影響について検討する。
以上の結果から, ALCvpl における概念満足度問題に対する決定性は, 一見無作為な自己演算子を加えると失われることがわかった。
古典的なデータベース設定とは対照的に、r#s#の非正則な原子を含むクエリに対するクエリエンテーメントの不確定性を確立する。
- 参考スコア（独自算出の注目度）: 7.832189413179361
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate the impact of non-regular path expressions on the decidability of satisfiability checking and querying in description logics extending ALC. Our primary objects of interest are ALCreg and ALCvpl, the extensions of with path expressions employing, respectively, regular and visibly-pushdown languages. The first one, ALCreg, is a notational variant of the well-known Propositional Dynamic Logic of Fischer and Ladner. The second one, ALCvpl, was introduced and investigated by Loding and Serre in 2007. The logic ALCvpl generalises many known decidable non-regular extensions of ALCreg. We provide a series of undecidability results. First, we show that decidability of the concept satisfiability problem for ALCvpl is lost upon adding the seemingly innocent Self operator. Second, we establish undecidability for the concept satisfiability problem for ALCvpl extended with nominals. Interestingly, our undecidability proof relies only on one single non-regular (visibly-pushdown) language, namely on r#s# := { r^n s^n | n in N } for fixed role names r and s. Finally, in contrast to the classical database setting, we establish undecidability of query entailment for queries involving non-regular atoms from r#s#, already in the case of ALC-TBoxes.
- Abstract（参考訳）: ALCを拡張した記述論理において、非正規経路表現が満足度チェックとクエリの決定可能性に与える影響について検討する。
我々の関心の対象は ALCreg と ALCvpl である。
第一の ALCreg は、フィッシャーとラドナーのよく知られた命題動的論理の記法的変種である。
第2のALCvplは2007年にLoding and Serreによって導入され調査された。
ALCvpl は ALCreg の多くの既知の決定不能な非正規拡張を一般化する。
一連の決定不可能な結果が得られます。
まず, ALCvpl における概念満足度問題に対する決定性は, 一見無作為な自己演算子を加えると失われることを示す。
第2に,ALCvpl における概念満足度問題に対して,命名法で拡張した不確定性を確立した。
興味深いことに、我々の不確定性証明は、r#s# := { r^n s^n | n in N } で固定されたロール名 r と s に対して、1つの非正規(可視的プッシュダウン)言語にのみ依存する。
最後に、従来のデータベース設定とは対照的に、既にALC-TBoxesの場合において、r#s#の非正則な原子を含むクエリに対するクエリエンテーメントの非決定性を確立する。
関連論文リスト
- The Sticky Path to Expressive Querying: Decidability of Navigational Queries under Existential Rules [4.557963624437784]
本稿では,これらの断片の問合せの可否が正規経路クエリ(RPQ)にまで拡張されるのかを考察する。
有限ユニフィケーション集合(短い: fus)として知られる2番目の主要な断片群に対して、対応する結果は大部分が解明されている。
正の面では、この問題はスティッキー・ルールセットの顕著なファス・サブクラスに対して決定可能であることを証明し、RPQ形式主義の非常に穏やかな拡張が問題を再び決定不能にする点に注意する。
論文 参考訳（メタデータ） (2024-07-19T15:11:09Z) - H-STAR: LLM-driven Hybrid SQL-Text Adaptive Reasoning on Tables [56.73919743039263]
本稿では,2段階のプロセスにシンボル的アプローチと意味的アプローチ(テキスト的アプローチ)を統合し,制約に対処する新しいアルゴリズムを提案する。
実験の結果,H-STARは3つの質問応答(QA)と事実検証データセットにおいて,最先端の手法を大幅に上回っていることがわかった。
論文 参考訳（メタデータ） (2024-06-29T21:24:19Z) - On Loop Formulas with Variables [2.1955512452222696]
最近、フェラーリス、リー、リフシッツはグラウンド化に言及しない安定モデルの新たな定義を提案した。
我々は、Chen, Lin, Wang, Zhang による変数を持つループ公式のアイデアとの関係を示す。
論理プログラムの構文を拡張して、明示的な量化を許容し、その意味論を安定モデルの新しい言語のサブクラスとして定義する。
論文 参考訳（メタデータ） (2023-07-15T06:20:43Z) - Interpretability at Scale: Identifying Causal Mechanisms in Alpaca [62.65877150123775]
本研究では、Boundless DASを用いて、命令に従う間、大規模言語モデルにおける解釈可能な因果構造を効率的に探索する。
私たちの発見は、成長し、最も広くデプロイされている言語モデルの内部構造を忠実に理解するための第一歩です。
論文 参考訳（メタデータ） (2023-05-15T17:15:40Z) - Finite Entailment of UCRPQs over ALC Ontologies [0.82179684645881]
我々は、クエリ言語、結合正則経路クエリの結合(UCRPQ)を考える。
記述論理 ALC を用いて,UCRPQ の包含のための厳密な 2EXP バウンドを示す。
入力オートマトンの背後にある決定論的有限オートマトンによって誘導される解釈の階層化を導入する新しいオートマトンベースの技術がある。
論文 参考訳（メタデータ） (2022-04-29T17:38:13Z) - The Price of Selfishness: Conjunctive Query Entailment for ALCSelf is
2ExpTime-hard [11.193504036335503]
論理に基づく知識表現では、クエリ応答は基本的に単に満足度チェックに置き換えられている。
基本記述論理 ALC の知識ベースでは、連結クエリ(CQ)応答の計算複雑性はExpTime-complete であることが知られている。
自己演算子のみによるALCの拡張さえも,CQ含意の複雑さを2ExpTimeに高めることを示す。
論文 参考訳（メタデータ） (2021-06-29T08:12:03Z) - On the KLM properties of a fuzzy DL with Typicality [0.0]
ファジィ論理を典型演算子で拡張することにより,多層パーセプトロンのファジィ多重参照セマンティクスを定義する手法が提案されている。
本稿では,その特性について考察する。
論文 参考訳（メタデータ） (2021-06-01T10:57:46Z) - Superposition with Lambdas [59.87497175616048]
匿名関数を含むがブール関数を除いた拡張多型高階論理のクラスフラグメントに対する重ね合わせ計算を設計する。
推論ルールは$betaeta$-equivalence class of $lambda$-termsで動作し、難解な完全性を達成するために高階統一に依存する。
論文 参考訳（メタデータ） (2021-01-31T13:53:17Z) - Superposition for Lambda-Free Higher-Order Logic [62.997667081978825]
本稿では,意図的および拡張的クラス数$lambda$-free高階論理に対して,難解な完全重ね合わせ計算を導入する。
計算は完全単調でなくてもよい項順でパラメタ化され、$lambda$フリーの高次語彙パスとKnuth-Bendixの順序を使うことができる。
論文 参考訳（メタデータ） (2020-05-05T12:10:21Z) - Conditional Self-Attention for Query-based Summarization [49.616774159367516]
条件依存モデリング用に設計されたニューラルネットワークモジュールであるテキスト条件自己アテンション(CSA)を提案する。
DebatepediaとHotpotQAベンチマークデータセットの実験は、CSAがバニラトランスフォーマーを一貫して上回っていることを示している。
論文 参考訳（メタデータ） (2020-02-18T02:22:31Z) - Best Arm Identification for Cascading Bandits in the Fixed Confidence
Setting [81.70513857417106]
CascadeBAIを設計し、分析する。これは、$K$アイテムのベストセットを見つけるアルゴリズムである。
CascadeBAIの時間的複雑さの上限は、決定的な分析課題を克服することによって導かれる。
その結果,カスケードBAIの性能は,時間的複雑性の低い境界の導出により,いくつかの実践的状況において最適であることが示唆された。
論文 参考訳（メタデータ） (2020-01-23T16:47:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。