论文标题
部分可观测时空混沌系统的无模型预测
On Probabilistic $ω$-Pushdown Systems, and $ω$-Probabilistic Computational Tree Logic
论文作者
论文摘要
在本文中，我们获得以下同等重要的新结果： 我们首先首次将{\ em概率的下降自动机}的概念扩展到{\ em概率$ω$ -PUSHDOWN automaton}，然后研究{\ em em eNcorelectilesscombilistic $ω$ω$ -PUSHDOWN SYSTEM的模型检查问题（$ -PBPA $ -PBPA $ -PBPA $ -PCTL） \ cite {csh08}），表明{\ em无状态概率$ω$ -PUSHDOWN SYSTEMS（$ω$ -PBPA）}的模型检查对$ω$ -PCTL通常是不可证实的。我们的方法是构造编码{\ em发布对应问题}的$ω$ -PCTL公式。 然后，我们研究了一种算法，用于检查模型检查{\ it无状态概率$ω$ -PUSHDOWN SYSTEMS}，并表明模型检查{\ IT无状态的概率$ω$ -PUSHDOWN SYSTEMS}对$ω$ - {\ IT bounded Pibabilistic countical Tree is Cocution Tree Tree cocticational copticational contrication-coptication coptication-copticational coptication contrication-coct（$）证明此问题在$ NP $ -HARD中。
In this paper, we obtain the following equally important new results: We first extend the notion of {\em probabilistic pushdown automaton} to {\em probabilistic $ω$-pushdown automaton} for the first time and study the model-checking question of {\em stateless probabilistic $ω$-pushdown system ($ω$-pBPA)} against $ω$-PCTL (defined by Chatterjee, Sen, and Henzinger in \cite{CSH08}), showing that model-checking of {\em stateless probabilistic $ω$-pushdown systems ($ω$-pBPA)} against $ω$-PCTL is generally undecidable. Our approach is to construct $ω$-PCTL formulas encoding the {\em Post Correspondence Problem}. We then study in which case there exists an algorithm for model-checking {\it stateless probabilistic $ω$-pushdown systems} and show that the problem of model-checking {\it stateless probabilistic $ω$-pushdown systems} against $ω$-{\it bounded probabilistic computational tree logic} ($ω$-bPCTL) is decidable, and further show that this problem is in $NP$-hard.
