論文の概要: PDL on Steroids: on Expressive Extensions of PDL with Intersection and Converse

• arxiv url: http://arxiv.org/abs/2304.10381v1
• Date: Thu, 20 Apr 2023 15:21:01 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-21 12:44:43.152531
• Title: PDL on Steroids: on Expressive Extensions of PDL with Intersection and Converse
• Title（参考訳）: ステロイドのpdl : 交叉と逆を伴うpdlの表現的拡張について
• Authors: Diego Figueira, Santiago Figueira, Edwin Pin
• Abstract要約: 代用動的論理(PDL)に根ざした表現論理群CPDL+を紹介する。 CPDL+の表現力,biCRPの特性,満足度,モデル検査について検討した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce CPDL+, a family of expressive logics rooted in Propositional Dynamic Logic (PDL). In terms of expressive power, CPDL+ strictly contains PDL extended with intersection and converse (a.k.a. ICPDL) as well as Conjunctive Queries (CQ), Conjunctive Regular Path Queries (CRPQ), or some known extensions thereof (Regular Queries and CQPDL). We investigate the expressive power, characterization of bisimulation, satisfiability, and model checking for CPDL+. We argue that natural subclasses of CPDL+ can be defined in terms of the tree-width of the underlying graphs of the formulas. We show that the class of CPDL+ formulas of tree-width 2 is equivalent to ICPDL, and that it also coincides with CPDL+ formulas of tree-width 1. However, beyond tree-width 2, incrementing the tree-width strictly increases the expressive power. We characterize the expressive power for every class of fixed tree-width formulas in terms of a bisimulation game with pebbles. Based on this characterization, we show that CPDL+ has a tree-like model property. We prove that the satisfiability problem is decidable in 2ExpTime on fixed tree-width formulas, coinciding with the complexity of ICPDL. We also exhibit classes for which satisfiability is reduced to ExpTime. Finally, we establish that the model checking problem for fixed tree-width formulas is in \ptime, contrary to the full class CPDL+.
• Abstract（参考訳）: 本稿では,PDL(Propositional Dynamic Logic)に根ざした表現論理群であるCPDL+を紹介する。 表現力の面では、CPDL+ は交叉と逆(ICPDL)で拡張された PDL を厳密に含み、また Conjunctive Queries (CQ)、 Conjunctive Regular Path Queries (CRPQ)、あるいはその既知の拡張 (Regular Queries と CQPDL) も含む。 CPDL+の表現力, バイシミュレーション特性, 満足度, モデル検査について検討した。 我々は、cpdl+ の自然な部分クラスは、式の基礎となるグラフのツリー幅によって定義できると主張する。 その結果,木幅2のcpdl+式はicpdlと同値であり,木幅1のcpdl+式とも一致することがわかった。 しかし、木幅2を超えると、木幅の増加は表現力を増加させる。 固定木幅公式のクラスごとの表現力は小石を用いたバイシミュレートゲームで特徴づける。 この特徴から,CPDL+は木のようなモデル特性を持つことを示す。 固定木幅式上での2ExpTimeでは,ICPDLの複雑さと一致して満足度が決定可能であることを示す。 また、満足度をExpTimeに下げるクラスも示します。 最後に、固定木幅式に対するモデルチェック問題は、フルクラスCPDL+とは対照的に \ptime であることを示す。

関連論文リスト

• Extended Version of: On the Structural Hardness of Answer Set Programming: Can Structure Efficiently Confine the Power of Disjunctions? [21.10339925217772]
  プログラムのルール構造上での解離的ASPの構造パラメータの分類に対処する。 我々は、その範囲で最も顕著なパラメータに対して、二重指数下界を提供する。 本研究は, 通常のプログラムから解離プログラムへの新規な縮小に頼って, 深部硬度調査を行う。
  論文  参考訳（メタデータ） (2024-02-05T21:51:36Z)
• CLIP-AD: A Language-Guided Staged Dual-Path Model for Zero-shot Anomaly Detection [49.510604614688745]
  大規模視覚言語モデルCLIPのゼロショット機能を活用するために,CLIP-ADというフレームワークを提案する。 異常写像の直接計算における逆の予測と無関係なハイライトについて述べる。
  論文  参考訳（メタデータ） (2023-11-01T11:39:22Z)
• Polynomial Width is Sufficient for Set Representation with High-dimensional Features [69.65698500919869]
  DeepSetsは集合表現のための最も広く使われているニューラルネットワークアーキテクチャである。 a) 線形 + パワーアクティベーション (LP) と (b) 線形 + 指数的アクティベーション (LE) の2つの集合要素埋め込み層を示す。
  論文  参考訳（メタデータ） (2023-07-08T16:00:59Z)
• Structure-Unified M-Tree Coding Solver for MathWord Problem [57.825176412485504]
  従来,数式表現の2次木構造を考慮に入れたモデルでは,性能が向上した。 本稿では、出力構造を統一するために、任意のM枝(M-tree)を持つ木を適用した構造統一M-Tree符号化(S-UMCr)を提案する。 広く使われているMAWPSとMath23Kデータセットの実験結果は、SUMC-rが複数の最先端モデルを上回るだけでなく、低リソース条件下でもはるかに優れた性能を発揮することを示した。
  論文  参考訳（メタデータ） (2022-10-22T12:20:36Z)
• DPO: Dynamic-Programming Optimization on Hybrid Constraints [26.704502486686128]
  ベイズ推定において、最も可能性の高い説明(MPE)問題は、いくつかの証拠から最も高い確率で変数のインスタンス化を要求する。 ブール MPE は (部分重み付き) MaxSAT への還元によって解けることが知られている。 我々はDPMC上に構築し,MPEを正確に解く動的プログラミングであるDPOを導入する。
  論文  参考訳（メタデータ） (2022-05-17T21:18:54Z)
• Hierarchical Dependency Constrained Tree Augmented Naive Bayes Classifiers for Hierarchical Feature Spaces [0.0]
  階層的依存性に基づく2つの新しいツリー拡張ネイブベイズアルゴリズム,すなわちHie-TANとHie-TAN-Liteを提案する。 Hie-TANは、他の階層的依存制約分類アルゴリズムよりも優れた予測性能を得た。
  論文  参考訳（メタデータ） (2022-02-08T19:16:51Z)
• Convex Polytope Trees [57.56078843831244]
  コンベックスポリトープ木(CPT)は、決定境界の解釈可能な一般化によって決定木の系統を拡張するために提案される。 木構造が与えられたとき,木パラメータに対するCPTおよび拡張性のあるエンドツーエンドトレーニングアルゴリズムを効率的に構築する。
  論文  参考訳（メタデータ） (2020-10-21T19:38:57Z)
• Please Mind the Root: Decoding Arborescences for Dependency Parsing [67.71280539312536]
  我々はUniversal Dependency Treebankから多くの言語における最先端の出力を分析する。 最悪の制約違反率は24%です。
  論文  参考訳（メタデータ） (2020-10-06T08:31:14Z)
• Span-based Semantic Parsing for Compositional Generalization [53.24255235340056]
  SpanBasedSPは入力発話上のスパンツリーを予測し、部分的なプログラムが入力内のスパンをどのように構成するかを明示的に符号化する。 GeoQuery、SCAN、CLOSUREでは、SpanBasedSPはランダムスプリットの強いseq2seqベースラインと似ているが、構成一般化を必要とするスプリットのベースラインに比べて劇的に性能が向上する。
  論文  参考訳（メタデータ） (2020-09-13T16:42:18Z)
• When is Ontology-Mediated Querying Efficient? [10.971122842236024]
  関係データベース上でのオントロジーによるクエリの評価について検討する。 OMQ のクラスの特徴として,複雑な組み合わせによるトラクタブルなクラスを提供しています。 また、与えられた OMQ が有界木幅の OMQ に等しいかどうかを決定する複雑さについても検討する。
  論文  参考訳（メタデータ） (2020-03-17T16:32:00Z)
• Structural Decompositions of Epistemic Logic Programs [29.23726484912091]
  認識論理プログラム(ELP)は標準解集合プログラミング(ASP)の一般的な一般化である 本研究では, 木幅境界で構造特性を示すELPに対して, 線形時間で中心的な問題を解くことができることを示す。 また、これらの境界に従属する完全な動的プログラミングアルゴリズムも提供します。
  論文  参考訳（メタデータ） (2020-01-13T13:16:13Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。