論文の概要: Satisfiability and Containment of Recursive SHACL
- arxiv url: http://arxiv.org/abs/2108.13063v1
- Date: Mon, 30 Aug 2021 08:51:03 GMT
- ステータス: 処理完了
- システム内更新日: 2021-08-31 14:45:35.266674
- Title: Satisfiability and Containment of Recursive SHACL
- Title(参考訳): 再帰的SHACLの満足度と満足度
- Authors: Paolo Pareti, George Konstantinidis, Fabio Mogavero
- Abstract要約: シェープ制約言語(Shapes Constraint Language, SHACL)は、グラフ上の特定の形状を検証することでRDFデータを検証するための最近のW3C勧告言語である。
これまでの研究は、バリデーション問題と、満足度と封じ込めの標準決定問題に主に焦点を合わせてきた。
我々は、SHACLのセマンティクスを正確に把握するSCLと呼ばれる新しい一階言語への翻訳を提供することにより、SHACLの異なる特徴を包括的に研究する。
また、SCLの2階拡張であるMSCLを提示し、単一の形式論理フレームワーク、メインで定義できるようにしました。
- 参考スコア(独自算出の注目度): 4.8986598953553555
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Shapes Constraint Language (SHACL) is the recent W3C recommendation
language for validating RDF data, by verifying certain shapes on graphs.
Previous work has largely focused on the validation problem and the standard
decision problems of satisfiability and containment, crucial for design and
optimisation purposes, have only been investigated for simplified versions of
SHACL. Moreover, the SHACL specification does not define the semantics of
recursively-defined constraints, which led to several alternative recursive
semantics being proposed in the literature. The interaction between these
different semantics and important decision problems has not been investigated
yet. In this article we provide a comprehensive study of the different features
of SHACL, by providing a translation to a new first-order language, called SCL,
that precisely captures the semantics of SHACL. We also present MSCL, a
second-order extension of SCL, which allows us to define, in a single formal
logic framework, the main recursive semantics of SHACL. Within this language we
also provide an effective treatment of filter constraints which are often
neglected in the related literature. Using this logic we provide a detailed map
of (un)decidability and complexity results for the satisfiability and
containment decision problems for different SHACL fragments. Notably, we prove
that both problems are undecidable for the full language, but we present
decidable combinations of interesting features, even in the face of recursion.
- Abstract(参考訳): シェープ制約言語(Shapes Constraint Language, SHACL)は、グラフ上の特定の形状を検証することでRDFデータの検証を行うW3C勧告言語である。
従来,SHACLの簡易版に対してのみ検討されてきた,満足度と包含性の基準決定問題や設計と最適化の目的に欠かせない課題に主に焦点が当てられていた。
さらに、shacl仕様は再帰的制約のセマンティクスを定義していないため、文献で提案されたいくつかの別の再帰的セマンティクスにつながった。
これらの異なる意味論と重要な決定問題との相互作用はまだ研究されていない。
本稿では、SHACLのセマンティクスを正確に把握するSCLと呼ばれる新しい一階言語への翻訳を提供することにより、SHACLの異なる特徴を包括的に研究する。
また、SCLの2階拡張であるMSCLを提案し、SHACLの主要な再帰的意味論である1つの形式論理フレームワークで定義することができる。
この言語内では、関連する文献でしばしば無視されるフィルタ制約の効果的な処理も提供します。
この論理を用いて、異なるSHACLフラグメントに対する満足度および包含性決定問題に対する(不)決定性および複雑性結果の詳細なマップを提供する。
特に、両問題が完全な言語では決定不能であることを示すが、再帰に直面しても興味深い特徴の組み合わせが決定可能である。
関連論文リスト
- SHACL2FOL: An FOL Toolkit for SHACL Decision Problems [0.4895118383237099]
我々は、SHACL文書をFOL文に変換する最初の自動ツールであるSHACL2FOLを紹介する。
このツールは、満足度と包含性の2つの静的解析問題に対する解を計算する。
また、一連の制約に関してグラフの有効性をテストすることもできる。
論文 参考訳(メタデータ) (2024-06-12T09:20:25Z) - LaSagnA: Language-based Segmentation Assistant for Complex Queries [39.620806493454616]
視覚のための大規模言語モデル(vLLM)は、バウンディングボックスやマスクを含む知覚結果を生成する。
本研究では,これらの問題の主な原因が,学習クエリの複雑さの不足であることを認めた。
本稿では,提案フォーマットの直接統合による課題を効果的に解決するための3つの新しい戦略を提案する。
論文 参考訳(メタデータ) (2024-04-12T14:40:45Z) - Spurious Feature Eraser: Stabilizing Test-Time Adaptation for Vision-Language Foundation Model [86.9619638550683]
視覚言語基礎モデルは、画像とテキストのペアデータに拡張性があるため、多数の下流タスクで顕著な成功を収めている。
しかし、これらのモデルは、決定ショートカットの結果、きめ細かな画像分類などの下流タスクに適用した場合に重大な制限を呈する」。
論文 参考訳(メタデータ) (2024-03-01T09:01:53Z) - Open-Vocabulary Segmentation with Semantic-Assisted Calibration [73.39366775301382]
オープンボキャブラリセグメンテーション(OVS)は,CLIPの文脈に先行して,語彙内およびドメインバイアスの埋め込み空間を校正することで研究される。
オープン語彙セグメンテーションベンチマークにおける最先端性能を実現するために,セマンティック・アシブ・キャリブレーション・ネットワーク(SCAN)を提案する。
論文 参考訳(メタデータ) (2023-12-07T07:00:09Z) - Triplet Contrastive Learning for Unsupervised Vehicle Re-identification [55.445358749042384]
部分的特徴学習は、車両の再識別におけるセマンティック理解にとって重要な技術である。
本稿では,クラスタ機能を活用したTCL(Triplet Contrastive Learning framework)を提案する。
論文 参考訳(メタデータ) (2023-01-23T15:52:12Z) - A Review of SHACL: From Data Validation to Schema Reasoning for RDF
Graphs [3.274290296343038]
本稿では,RDFデータ検証のためのW3Cレコメンデーション言語であるShapes Constraint Language (SHACL)の紹介とレビューを行う。
SHACL文書はRDFノード上の一連の制約を記述しており、ノードがこれらの制約を満たす場合、グラフは文書に対して有効である。
論文 参考訳(メタデータ) (2021-12-02T17:28:45Z) - Fixpoint Semantics for Recursive SHACL [10.896533521085784]
SHACLは、RDFグラフの構造的制約を表現するためのW3C提案言語である。
本稿では,SHACLのセマンティクスを定義し,研究するために,非単調推論における長年の研究から教訓を学ぶことができることを論じる。
論文 参考訳(メタデータ) (2021-09-17T01:46:09Z) - Anti-aliasing Semantic Reconstruction for Few-Shot Semantic Segmentation [66.85202434812942]
セグメンテーションを意味的再構成問題として再検討する。
基本クラスの特徴を,新しいクラス再構築のためのクラスレベルのセマンティック空間にまたがる一連の基底ベクトルに変換する。
提案手法はアンチエイリアス・セマンティック・リストラクション (ASR) と呼ばれ, 数発の学習問題に対して, 体系的かつ解釈可能な解法を提供する。
論文 参考訳(メタデータ) (2021-06-01T02:17:36Z) - An Efficient Diagnosis Algorithm for Inconsistent Constraint Sets [68.8204255655161]
過制約問題における最小限の障害制約を識別する分割・分散型診断アルゴリズム(FastDiag)を提案する。
ヒットセットの競合指向計算とfastdiagを比較し,詳細な性能解析を行う。
論文 参考訳(メタデータ) (2021-02-17T19:55:42Z) - Joint Contrastive Learning with Infinite Possibilities [114.45811348666898]
本稿では,新しい確率論的モデリングによるコントラスト学習における最近の発展の有用性について考察する。
コントラスト学習(Joint Contrastive Learning, JCL)という,コントラスト学習の特定の形態を導出する。
論文 参考訳(メタデータ) (2020-09-30T16:24:21Z) - SHACL Satisfiability and Containment (Extended Paper) [6.308539010172308]
Shapes Constraint Language (SHACL)は、RDFデータを検証するための最近のW3C勧告言語である。
本稿では、SCLと呼ばれる新しい一階述語言語への翻訳を提供することにより、再帰的でないSHACLの異なる特徴を徹底的に研究する。
この論理学におけるSHACLの特徴の相互作用について検討し、上記のSHACLサブ言語に対する決定問題の決定可能性と複雑性の詳細なマップを提供する。
論文 参考訳(メタデータ) (2020-08-31T14:52:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。