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 が演算子とのクエリでは決定不可能であることを示す。

関連論文リスト

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)
Towards Characterizing the First-order Query Complexity of Learning (Approximate) Nash Equilibria in Zero-sum Matrix Games [0.0]
正確な平衡は$O(fracln Kepsilon)$クエリの代わりに$O(fracln Kepsilon)$から効率的に計算できることを示す。我々は下界に対する新しい手法を導入し、任意の$epsilon leq 1 / (cK4)$に対して$tildeOmega(frac1Kepsilon)$の下位境界を得ることができる。
論文参考訳（メタデータ） (2023-04-25T12:42:59Z)
Spacetime-Efficient Low-Depth Quantum State Preparation with Applications [93.56766264306764]
任意の量子状態を作成するための新しい決定論的手法は、以前の方法よりも少ない量子資源を必要とすることを示す。我々は、量子機械学習、ハミルトンシミュレーション、方程式の線形系を解くことなど、この能力が役立ついくつかのアプリケーションを強調した。
論文参考訳（メタデータ） (2023-03-03T18:23:20Z)
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)

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

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