概率与非确定性的结合问题的理论计算机科学电子笔记

理论计算机科学电子笔记162（2006）261-265www.elsevier.com/locate/entcs论概率与非确定性的结合1M. W. Mislove杜兰大学New Orleans，LA摘要在指称模型中结合非确定性和概率的问题一直是许多研究的主题。早期的工作使用决策者来模拟概率选择，将其执行与非确定性选择的执行交织在一起，这一主题在今天的一些操作模型中仍然存在。最近的工作集中在提供一个原则性的帐户，这些运营商的相互作用，设计的模型，支持这两个运营商，使两者都不相关的目的。在本文中，我们沿着这条线叙述的结果，并指出一些地方，进一步的研究是值得的。关键词：概率选择，赋值，域理论，分配律，CCS1引言非确定性一直是一个主食的进程代数自成立以来，但最近的概率选择已经包括在内。虽然早期的工作取代概率选择的非决定论，最近的趋势，包括非决定论和概率选择在同一代数。这样做的一个基本原理是，非确定性代表了用户选择采取哪种操作的方法，而概率选择可以捕获环境的变幻莫测，因为在流程运行期间发生随机事件。在同一代数中包含这两种操作符的问题是找到一个模型，该模型可以捕捉两种类型的选择，但其中任何一种都不影响另一种。 例如，如果概率性选择取决于之前的非决定性选择，或者如果非决定性选择是由概率性选择的解决方式决定的，那么模型就不能令人满意。确保这种情况不会发生的最简单方法1 这项工作得到了美国国家科学基金会和美国海军研究办公室的支持。1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2005.12.113262M.W. Mislove/Electronic Notes in Theoretical Computer Science 162（2006）261并且在两个过程的概率选择和它们的非确定性选择之间没有关系。事实证明，找到这样一个模型是非常困难的。事实上，有结果表明，这样的模型可能不存在。首先，我们回顾一下，非确定性选择的定律是半格的定律--在一个有限的无序状态空间上，一个合适的模型是幂集，但是如果底层模型是一个域，那么Hennessy和Plotkin [5]现在熟悉的结果表明有三个模型可供选择：下幂域，上幂域和凸幂域。[3]每一个都形成了不同范畴的域上单子的对象层，并且在每一种情况下，单子的代数都是相应类型的域半格概率幂域是从D 的Scott 开集族到单位区间的Scott连续的取值族φ：（σ（D），σ（D））→（[0，1]，≤），取空集为0，满足包含-排除原理：φ（UV）+ φ（U V）= φ（U）+ φ（V）. 他们生成了一个模型，满足格雷厄姆[4]首先阐述的概率选择定律：如果对于λ∈[0， 1]，我们让p<$λq表示像p一样行动的概率为λ和像q一样行动的概率为1−λ的过程，那么对于λ，<$∈[0， 1]和过程p，q，r：·p<$λp=p;·p<$λq=q<$1 −λp;·p1q=p;⎧• （p<$λq）r=p<$λ<$（q<$1−λ1−λξr) ，假设λ1，别说了。概率幂域是域上的单子，但除了保持连续性和相干性之外，我们不知道它是否是任何一个范畴上的闭函子。要创建一个既支持非决定论又支持概率选择的模型，一个显而易见的方法就是一个接一个地应用单子。例如，Morgan等人[12]通过将概率幂域应用于故障发散模型，采用CSP的这种方法其结果是一个模型，其中概率选择服从预期的法律（因为它的单子是最后应用但非决定论不再是幂等的。为了理解原因，让H表示非决定性选择，并注意，H以逐点方式从失败发散模型提升到其概率幂域，对于所有λ，H分布通过λλ;使用上面的概率选择定律，可以得出：（P<$1Q）H（P<$1Q）=（P<$1（PHQ））<$1（（QHP）<$1Q）2 2 2 2 2=P<$1（（PHQ）<$2Q），4 3所以我们看到非决定论和概率选择已经混合在一起了。[2]定义域指的是一个有向完全偏序，其中每个元素都是位于它之下的元素的有向上;参见。[1]详情。3它们是基础整环上的初始超半格整环、初始下半格整环和初始序半格整环4.一个整环是凝聚的，如果它的Lawson拓扑是紧的。这些域经常出现在应用中;例如，边界域和FS域的收缩都是一致的。然而，相干域M.W. Mislove/Electronic Notes in Theoretical Computer Science 162（2006）261263对于刚才看到的选择操作符的混合的解释是，monad的组合并不总是另一个monad。Beck [2]探索了这个问题，并证明了单子组成当且仅当存在一个分配律5。不幸的事实是，Plotkin和Varacca [14，15]已经证明，在概率幂域上没有任何非确定性单子的分配律，反之亦然，因此将任何非确定性单子与概率幂域组合不会导致另一个解决这个问题的一种方法是由Tix [13]描述的（后来在[7]中进行了修订和阐述），并由作者独立描述[9]。它首先应用概率幂域，然后应用非确定性的一个幂域这导致类似于三个幂域，其中每一个都被实现为通常的幂域到其几何凸6元的子族上的收缩;例如，在上幂域的情况下，结果是几何凸的幂域，底层域的斯科特紧上集由此产生的域模型的非确定性选择和概率选择，使每一个法律都遵守，但有一个例如，在上幂域的模拟中，这是一个下半格，不等式pHq±p<$λq对每个p，q和每个λ∈[0， 1]成立这些模型表明，可以调整标准幂域单子，以考虑几何凸结构，并且在每种情况下，几何凸元素的子域是原始幂域的收缩此外，它可以表明，在较低和较高的功率域的情况下，这些结构应用于相干域D产生一个有界的完整域。Tix/Mislove（[13，9]）设计的模型之一的操作证明在[11]中提出，其中使用标记马尔可夫过程的理论，表明该构造给出了CCS的简单子语言的概率扩展的指称模型，该模型对于CCS的概念是完全抽象的。部分概率互模拟：过程P和Q满足模型中的[P]]±[[Q]]i如果P满足一个特定的域逻辑L的公式，那么Q也满足这个公式。此外，这种概率扩展是保守的，CCS，这意味着纯CCS过程在模型中被识别，如果它们被识别为CCS过程。它仍然是扩大这条线的研究，包括一个更有代表性的子代数CCS的概率选择附加。另一个寻找非决定论和概率选择模型的解决方案是由Varacca [14]设计的，他意识到改变定义单子的定律将允许这样一个分配定律。Varraca从Gautem [3]的一个结果中得到了启示，该结果断言，以集合为模型的代数理论逐点提升到幂集合i，该理论中的每个方程最多只提到每个变量一次。[5]一个简单的方法是将一个Soveramo n on ondTisan auraltrans formond：Sott−→。令人满意其他法律。这些推广了通常的概念，一个代数运算分布在另一个。6.一个集合X是几何凸的，如果x，y∈X且λ∈[0， 1]蕴涵x<$λy∈X。7 所谓域逻辑，我们指的是一种描述感兴趣的域上的顺序的逻辑。264M.W. Mislove/Electronic Notes in Theoretical Computer Science 162（2006）261在等式的两边。在概率选择的情况下，问题在于定律p<$λp=p，因此他消除了这个定律。 其结果是一个理论，在这个理论中，这种平等以三种方式之一被取代或另一个，或在组件之间没有关系。Varacca设计了一种称为指数赋值的模型--p∈λp和p之间的三种可能关系中的每一种都有一个--它定义了单子，每个单子都享有关于以下的分配律：至少有一个非决定论单子瓦拉卡还通过证明他的构造作为指称模型的充分性定理，为他的构造提供了一个操作上的正当性（至少在状态空间是一个集合的情况下）。然而，由于操作模型记录了每个概率选择是如何解决的，因此它比通常的模型做出了更精细的区分。使用Varacca思想的进一步工作和（连续）域8的FS都不变。 这提供了第一个模型，具有这种性质的概率计算。[8]中的工作依赖于关于整环上袋整环结构的一些有趣结果[10]。例如，一个构造展示了如何在初始域么半群上精化偏序，使得给定的引用[1] Abramsky，S.和A.Jung，Abramsky和D.M. Gabbay和T.S. E. Maibaum，editors，Clarendon Press，1994，pp.1-168[2] 贝克，J.，分配律，在：研讨会上的三元组和范畴同调理论，1969年，页。119比140[3] 去吧，N。 J.， The vealidity ofeq uati onsoffcomplexalgebras，A rchivfuürMmatissch eLogikundGrundlagenforschung 3（1957），pp. 117-124[4] 格雷厄姆，S。K.（1985），概率域构造的闭包性质，计算机科学讲义298，pp. 213-233[5] Hennessy，M.和G. D. Plotkin，Full abstraction for a simple parallel programming language，LectureNotes in Computer Science74（1979）. 108-120[6] 琼斯角，澳-地[7] Keimel，K.，G. Plotkin和R. Tix，结合概率和非确定性的语义域，电子笔记理论计算机科学129（2005），104页。[8] Mislove，M.，Discrete random variables over domains，ICALP 2005，LNCS3580（2005），pp.1006-1017..[9] Mislove，M. 非决定论和概率选择：遵守法律，计算机科学讲义1877（2000），页。350-364.[10] Mislove，M. Monoids over domains，Mathematical Structures in Computer Science16（2006），pp.255- 277[11]Mislove，M.，J. Ouaknine和J.B. 陈文，概率论与非决定论，《理论计算机科学电子笔记》，2003年出版，第91卷，第3期 。8RB是双有限域的收缩范畴，FS是单位元是与单位元有限分离的映射的上确界的域范畴;每个都是ccc，后者是极大的。M.W. Mislove/Electronic Notes in Theoretical Computer Science 162（2006）261265[12] 摩根，C.，等，CSP的Refinement-oriented probability，技术报告PRG-TR-12-94，牛津大学计算实验室，1994年。[13] 蒂克斯河，“连续D-锥：凸性和幂域构造”，博士论文，TechnischeUniversitéatDarmstadt，1999年。[14] Varacca，D.，索引赋值的幂域，Proceedings 17th IEEE Symposium on Logic in Computer Science（LICS2002），IEEE Press，2002。[15] Varacca，D.，“Probability, Nondeterminism and Concurrency: Two Denotational Models forProbabilistic Computation,” PhD Dissertation, Aarhus University, Aarhus, Denmark,