概要 - 「高階Datalogにおける否定の力」

タイトル

「高階Datalogにおける否定の力」

時間

2025-07-27 12:33:21

著者

{"Angelos Charalambidis","Babis Kostopoulos","Christos Nomikos","Panos Rondogiannis"}

カテゴリ

{cs.PL,cs.CC,cs.DB,cs.LO}

リンク
http://arxiv.org/abs/2507.20251v1

PDF リンク
http://arxiv.org/pdf/2507.20251v1

概要

この論文は、well-foundedとstable modelセマNTIXの両方の下で、高階Datalogの表現力を調査し、複雑性クラスとの関係を確立しています。著者たちは、(k + 1)-Order Datalogがwell-foundedセマNTIXの下でk-EXPを捕らえることを証明し、(k + 1)-Order Datalogがstable modelセマNTIXの下で慎重な推論と大胆な推論をそれぞれ用いてco-(k-NEXP)とk-NEXPを捕らえることを示しました。彼らはまた、この表現力が言語の層状断片に保たれていることも示しました。論文の主要な貢献は以下の通りです： 1. 著者たちは、(k + 1)-Order Datalogがwell-foundedセマNTIXの下でinputデータベースの事前の順序付けを必要とせずにk-EXPを捕らえることを証明しました。この結果は、存在量詞変数を持たない言語の断片や(k + 1)-Order Datalogの層状断片にも適用されます。 2. 著者たちは、(k + 1)-Order Datalogがstable modelセマNTIXの下で慎重な推論を用いてco-(k-NEXP)を捕らえ、大胆な推論を用いてk-NEXPを捕らえることを示しました。これらの結果は、存在量詞変数の有無に関わらず、(k + 1)-Order Datalogの層状部分と単純な非層状部分（選択ルール）からなる断片に適用されます。 3. 著者たちは、高階論理プログラミングの文脈で秩序と非決定論の興味深いトレードオフを示しました：well-foundedセマNTIXの下でプログラムの秩序を高めると、stable modelセマNTIXの下で低階プログラムの非決定論によって提供される表現力を超えることができます。著者たちは、否定は高階Datalogで強力な構造であり、言語の表現力が否定を取り入れることで大幅に強化されることを結論付けました。また、k階プログラムから(k + 1)階プログラムへの形式変換の開発や、高階Datalogの実装など、今後の研究のためのいくつかの挑戦的な方向を示しました。

推奨論文

AQuilt: 専門用LLMsのための低コスト、高い関連性を持つデータ統合にロジックと自己検査を織り交ぜたもの

「同等に有効なモデルからの任意の予測」

量子回路暗号化に基づく暗号化状態量子コンパイルスキーム

生物伝達物質を介した合成MC：腸-脳軸の治療的調節

GEPA: 反映的なプルミプト進化が强化学習を超える可能性があります

ロボットサッカーのための効率的なライン検出

最もシンプルな非局在化量子臨界点のブートストラッピング

デジタルツインと生成型AIを通じてサイバーセキュリティ教育を可能にする

3DGauCIM：デジタルCIMを通じて、高フレームレートリアルタイムエッジレンダリングのための静的/動的3Dガウススプラッティングを加速します

シロフの境界におけるリース評価と積分拡張