Fugu-MT 論文翻訳(概要): On Deciding the Data Complexity of Answering Linear Monadic Datalog Queries with LTL Operators(Extended Version)

論文の概要: On Deciding the Data Complexity of Answering Linear Monadic Datalog Queries with LTL Operators(Extended Version)

arxiv url: http://arxiv.org/abs/2501.13762v1
Date: Thu, 23 Jan 2025 15:41:48 GMT
ステータス: 翻訳完了
システム内更新日: 2025-01-24 15:55:42.111251
Title: On Deciding the Data Complexity of Answering Linear Monadic Datalog Queries with LTL Operators(Extended Version)
Title（参考訳）: LTL演算子による線形モナディックなデータログクエリのデータの複雑度決定について(拡張バージョン)
Authors: Alessandro Artale, Anton Gnatenko, Vladislav Ryzhikov, Michael Zakharyaschev,
Abstract要約: このようなクエリに応答するLogSpace-hardnessを決定する問題は、PSpace-completeであることを示す。我々は、演算子$Diamond_f/Diamond_p$のクエリに対してAC0またはACC0、$NC1$-completeness、およびLogSpace-hardnessが決定不可能であることを証明する。
参考スコア（独自算出の注目度）: 45.52009397811254
License:
Abstract: Our concern is the data complexity of answering linear monadic datalog queries whose atoms in the rule bodies can be prefixed by operators of linear temporal logic LTL. We first observe that, for data complexity, answering any connected query with operators $\bigcirc/\bigcirc^-$ (at the next/previous moment) is either in AC0, or in $ACC0\!\setminus\!AC0$, or $NC^1$-complete, or LogSpace-hard and in NLogSpace. Then we show that the problem of deciding LogSpace-hardness of answering such queries is PSpace-complete, while checking membership in the classes AC0 and ACC0 as well as $NC^1$-completeness can be done in ExpSpace. Finally, we prove that membership in AC0 or in ACC0, $NC^1$-completeness, and LogSpace-hardness are undecidable for queries with operators $\Diamond_f/\Diamond_p$ (sometime in the future/past) provided that $NC^1 \ne NLogSpace$, and $LogSpace \ne NLogSpace$.
Abstract（参考訳）: 我々の懸念は、規則体内の原子が線形時間論理LTLの演算子によってプレフィックスできる線形モナディックなデータログクエリに応答するデータの複雑さである。データ複雑性については、演算子との接続クエリに$\bigcirc/\bigcirc^-$(次の/前の瞬間に)がAC0か$ACC0\! \setminus\! AC0$、または$NC^1$-complete、またはLogSpace-hardとNLogSpace。次に、このようなクエリに応答するLogSpace-hardnessを決定する問題はPSpace完全であり、AC0とACC0のクラスのメンバーシップと$NC^1$-completenessはExpSpaceで実行可能であることを示す。最後に、$NC^1 \ne NLogSpace$ および $LogSpace \ne NLogSpace$ を条件として、AC0 または ACC0 におけるメンバシップ、$NC^1$-completeness および LogSpace-hardness が演算子とのクエリでは決定不可能であることを示す。

関連論文リスト

PREM: Privately Answering Statistical Queries with Relative Error [91.98332694700046]
合成データを生成する新しいフレームワークである$mathsfPREM$(Private Relative Error Multiplicative weight update)を紹介します。我々はアルゴリズムをほぼ一致する下界で補完する。
論文参考訳（メタデータ） (2025-02-20T18:32:02Z)
Active Learning of General Halfspaces: Label Queries vs Membership Queries [35.41111301965335]
アクティブな学習者は、$tildeOmega(d/(log(m)epsilon)$というラベルの複雑さを必要とする。クエリ複雑性が$tildeO(min1/p, 1/epsilon + dcdot polylog (1/epsilon))$$O(opt)+epsilon$のエラー保証を実現する。
論文参考訳（メタデータ） (2024-12-31T15:40:48Z)
Adding Circumscription to Decidable Fragments of First-Order Logic: A Complexity Rollercoaster [9.516475567386767]
単項述語のみを円周的に最小化(あるいは固定化)した場合、論理オントロジーの決定可能性を証明する。 FO$2$の場合、複雑さは$textrmcoNexp$から$textrmTower$-complete、GFでは$textrm2Exp$から$textrmTower$-completeに増加します。
論文参考訳（メタデータ） (2024-07-30T13:39:38Z)
On the Communication Complexity of Approximate Pattern Matching [2.4167127333650202]
上界が$O(n/m cdot k log2 m)$ bitsであることを証明する。また、$O(n/m cdot k log2 m)$ bits は、$k$-error 発生毎に$P$ in $T$ のエンコードを可能にする。
論文参考訳（メタデータ） (2024-03-27T17:57:16Z)
On polynomially many queries to NP or QMA oracles [0.0]
本稿では,NPやQuantum Merlin-Arthur-oracle(QMA)にアクセスして,決定論的時間で解ける問題の複雑性について検討する。まず、検証クラス$CinNP,MA,QMA,QMA(2),NEXP,QMA_exp$に対して、「セパレータ番号」$s$のクエリグラフを持つ任意の$PC$マシンをシミュレートできることを示す。次に、Gottlobの"許容重み付け関数"フレームワークと"フラグキュービット"フレームワークを組み合わせる方法について説明する。
論文参考訳（メタデータ） (2021-11-03T15:29:01Z)
Learning low-degree functions from a logarithmic number of random queries [77.34726150561087]
任意の整数 $ninmathbbN$, $din1,ldots,n$ および任意の $varepsilon,deltain(0,1)$ に対して、有界関数 $f:-1,1nto[-1,1]$ に対して、少なくとも$d$ の次数を学ぶことができる。
論文参考訳（メタデータ） (2021-09-21T13:19:04Z)
Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
論文参考訳（メタデータ） (2021-05-17T16:40:48Z)
An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文参考訳（メタデータ） (2020-08-24T06:50:57Z)
On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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