We tackle the problem of establishing the soundness of approximate bisimilarity with respect to PCTL and its relaxed semantics. To this purpose, we consider a notion of bisimilarity inspired by the one introduced by Desharnais, Laviolette, and Tracol, and parametric with respect to an approximation error $\delta$, and to the depth $n$ of the observation along traces. Essentially, our soundness theorem establishes that, when a state $q$ satisfies a given formula up-to error $\delta$ and steps $n$, and $q$ is bisimilar to $q'$ up-to error $\delta'$ and enough steps, we prove that $q'$ also satisfies the formula up-to a suitable error $\delta"$ and steps $n$. The new error $\delta"$ is computed from $\delta$, $\delta'$ and the formula, and only depends linearly on $n$. We provide a detailed overview of our soundness proof. We extend our bisimilarity notion to families of states, thus obtaining an asymptotic equivalence on such families. We then consider an asymptotic satisfaction relation for PCTL formulae, and prove that asymptotically equivalent families of states asymptotically satisfy the same formulae.
翻译:我们解决了在PCTL及其宽松语义方面大约两样性是否合理的问题。 为此,我们考虑了由Desharnais, Laviolette, Tracol提出的一种两样性概念,以及近似差错的参数,$delta$, 以及按痕迹计算的观测深度。 基本上, 我们的“ 稳健理论” 确定, 当一州美元满足一个给定的公式时, 差错为$\delta$, 步骤为$, 美元为$, 美元为美元, 最高差错为$, 步骤为美元。 为此, 我们把我们的“ 美元” 概念推广到各州家庭, 从而将“ 美元” 和“ 适当差错” 和“ 步骤” 美元。 新的差错是用$delta$, 美元和公式来计算, 并且仅以美元为直线线。 我们详细介绍了我们的“ 稳健度证据 ” 。 我们把我们的两样性概念扩展为“ ” 家庭,, 也作为“ 等同的公式” 。