論文の概要: Model-Checking PCTL properties of Stateless Probabilistic Pushdown
Systems with Various Extensions
- arxiv url: http://arxiv.org/abs/2209.10517v7
- Date: Tue, 8 Aug 2023 00:42:01 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-27 05:32:15.944543
- Title: Model-Checking PCTL properties of Stateless Probabilistic Pushdown
Systems with Various Extensions
- Title(参考訳): 各種拡張を有する無定常確率型プッシュダウンシステムのモデルチェッキングPCTL特性
- Authors: Tianrong Lin
- Abstract要約: まず、無限状態系の確率的検証(具体的には、エム状態のない確率的プッシュダウンシステム)における開問題を解決する。
モデル検査は,pBPA (Stateless Probabilistic Pushdown System) とPCTL (Em Probabilistic Computing Tree logic) の併用が一般的ではないことを示す。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: In this paper, we first resolve an open question in the probabilistic
verification of infinite-state systems (specifically, the {\em stateless
probabilistic pushdown systems}). We show that model checking {\em stateless
probabilistic pushdown systems (pBPA)} against {\em probabilistic computational
tree logic (PCTL)} is generally undecidable. We define the quantum analogues of
the {\em probabilistic pushdown systems} and {\em Markov chains}, and further
investigate whether it is necessary to define a quantum analogue of {\em
probabilistic computational tree logic} to describe the branching-time
properties of the {\em quantum Markov chain} defined in this paper. We study
its model-checking question and show that the model-checking of {\em stateless
quantum pushdown systems (qBPA)} against {\em probabilistic computational tree
logic (PCTL)} is generally undecidable, with the immediate corollaries
summarized. We define the notion of {\em probabilistic $\omega$-pushdown
automaton} for the first time and study the model-checking question of {\em
stateless probabilistic $\omega$-pushdown system ($\omega$-pBPA)} against
$\omega$-PCTL (defined by Chatterjee et al. in \cite{CSH08}) and show that the
model-checking of {\em stateless probabilistic $\omega$-pushdown systems
($\omega$-pBPA)} against $\omega$-PCTL is generally undecidable, with immediate
consequences summarized. Our approach is to construct formulas of $\omega$-PCTL
encoding the {\em Post Correspondence Problem} indirectly.
- Abstract(参考訳): 本稿では、まず、無限状態系の確率的検証(具体的には、状態のない確率的プッシュダウン系)における開問題を解決する。
我々は、モデルチェック {\em stateless probabilistic pushdown system (pBPA) が一般には決定不可能であることを示す。
我々は「em確率的プッシュダウンシステム」と「emマルコフ連鎖」の量子アナログを定義し、本論文で定義された「em量子マルコフ連鎖」の分岐時間特性を記述するために「em確率的計算木論理」の量子アナログを定義する必要があるかどうかをさらに検討する。
モデルチェック問題について検討し,計算木論理 (PCTL) に対する状態のない量子プッシュダウンシステム (qBPA) のモデルチェックが概ね決定不可能であることを示す。
我々は「em確率的$\omega$-pushdown automaton」の概念を初めて定義し、"em stateless probabilistic $\omega$-pushdown system (\omega$-pbpa)} と$\omega$-pctl (chatterjee et al. in \cite{csh08}) とのモデルチェック問題を調べ、"em stateless probabilistic $\omega$-pushdown system (\omega$-pbpa)} と$\omega$-pctl のモデルチェックが一般に決定不能であることを示し、その結果を要約する。
我々のアプローチは間接的に$\omega$-PCTLを符号化する公式を構築することである。
関連論文リスト
- First detection probability in quantum resetting via random projective
measurements [0.0]
一般量子系における「興味のある状態」の最初の検出時間の確率分布を$F_r(t)$で計算する。
F_r(t)sim t2$ が$p(0)ne 0$ であることを示す。
論文 参考訳(メタデータ) (2023-05-24T13:15:01Z) - Causal Temporal Reasoning for Markov Decision Processes [4.040829575021796]
マルコフ決定過程(MDP)の検証のための新しい時間論理である $textitPCFTL (Probabilistic CounterFactual Temporal Logic)$ を導入する。
PCFTLは因果推論の演算子を初めて含み、介入的および反事実的クエリを表現できる。
グリッドワールドモデルのベンチマークを用いて,PCFTLを安全な強化学習の文脈で評価する。
論文 参考訳(メタデータ) (2022-12-16T21:11:44Z) - A Quantum Algorithm Framework for Discrete Probability Distributions with Applications to Rényi Entropy Estimation [13.810917492304565]
離散確率分布の特性を推定するための統一量子アルゴリズムフレームワークを提案する。
我々のフレームワークは、$alpha$-R'enyi entropy $H_alpha(p)$を、少なくとも2/3$の確率で加算エラー$epsilon$内で推定する。
論文 参考訳(メタデータ) (2022-12-03T08:01:55Z) - Sublinear quantum algorithms for estimating von Neumann entropy [18.30551855632791]
我々は、確率分布のシャノンエントロピーと混合量子状態のフォン・ノイマンエントロピーの乗法係数$gamma>1$における推定値を得る問題を研究する。
我々は古典的確率分布と混合量子状態の両方を扱える量子純粋クエリーアクセスモデルに取り組んでおり、文献の中では最も一般的な入力モデルである。
論文 参考訳(メタデータ) (2021-11-22T12:00:45Z) - Logical Credal Networks [87.25387518070411]
本稿では,論理と確率を組み合わせた先行モデルの多くを一般化した表現的確率論的論理である論理的クレダルネットワークを紹介する。
本稿では,不確実性のあるマスターミンドゲームを解くこと,クレジットカード詐欺を検出することを含む,最大後部推論タスクの性能について検討する。
論文 参考訳(メタデータ) (2021-09-25T00:00:47Z) - Complex Event Forecasting with Prediction Suffix Trees: Extended
Technical Report [70.7321040534471]
複合イベント認識(CER)システムは、イベントのリアルタイムストリーム上のパターンを"即時"検出する能力によって、過去20年間に人気が高まっている。
このような現象が実際にCERエンジンによって検出される前に、パターンがいつ発生するかを予測する方法が不足している。
複雑なイベント予測の問題に対処しようとする形式的なフレームワークを提案する。
論文 参考訳(メタデータ) (2021-09-01T09:52:31Z) - Predictability as a quantum resource [0.0]
状態$rho$,$P$ of $rho$で作成されたシステムに対して、観測可能な$X$を参照して、$C$と等しいことを示す。
また、予測可能性に関するリソース理論を提案し、その自由量子状態と自由量子演算を同定する。
論文 参考訳(メタデータ) (2021-07-28T16:27:17Z) - Probabilistic Generating Circuits [50.98473654244851]
効率的な表現のための確率的生成回路(PGC)を提案する。
PGCは、非常に異なる既存モデルを統一する理論的なフレームワークであるだけでなく、現実的なデータをモデル化する大きな可能性も示している。
我々はPCとDPPの単純な組み合わせによって簡単に仮定されない単純なPGCのクラスを示し、一連の密度推定ベンチマークで競合性能を得る。
論文 参考訳(メタデータ) (2021-02-19T07:06:53Z) - Random quantum circuits anti-concentrate in log depth [118.18170052022323]
本研究では,典型的な回路インスタンスにおける測定結果の分布に要するゲート数について検討する。
我々の反集中の定義は、予測衝突確率が分布が均一である場合よりも大きい定数因子に過ぎないということである。
ゲートが1D環上で最寄りである場合と、ゲートが長距離である場合の両方において、$O(n log(n))ゲートも十分であることを示す。
論文 参考訳(メタデータ) (2020-11-24T18:44:57Z) - Tractable Inference in Credal Sentential Decision Diagrams [116.6516175350871]
確率感性決定図は、解離ゲートの入力が確率値によってアノテートされる論理回路である。
我々は、局所確率を質量関数のクレーダル集合に置き換えることができる確率の一般化である、クレーダル感性決定図を開発する。
まず,ノイズの多い7セグメント表示画像に基づく簡単なアプリケーションについて検討する。
論文 参考訳(メタデータ) (2020-08-19T16:04:34Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳(メタデータ) (2020-06-04T17:51:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。