概率并发理论

项目名称： 概率并发理论

项目编号： No.61173033

项目类型： 面上项目

立项/批准年度： 2012

项目学科： 计算机科学学科

项目作者： 邓玉欣

作者单位： 上海交通大学

项目金额： 56万元

中文摘要： 与经典并发理论相比，概率并发进程的语义理论还不成熟，在形式化语义方面还有许多公开问题未被解决。其中一个基本问题是如何在特定概率模型上比较各种常见的语义如互模拟语义、测试语义和trace 语义。在本项目中我们将对这一问题进行全面探索，力图澄清一般无限状态无限分支、无限状态有限分支、有限状态无限分支、有限状态有限分支模型、以及一般完全概率模型上互模拟语义、模拟语义、测试语义、trace 语义等之间的相互关系，建立关于概率并发进程比较完整的语义理论。另外，目前在有限状态有限分支模型上对概率行为等价和前序关系的判定仅限于划分求精算法，这要求预先生成被考虑系统的整个状态空间，且只适用于等价关系的判定，在实际应用中往往表现不佳。因此，在本项目中我们考虑设计局部算法以判定行为等价和前序关系。这类算法可动态生成所需的状态空间，对等价关系和前序关系的判定均适用，且在验证否定结论时通等常效率较高而具应用前景。

中文关键词： 并发理论；概率进程；模拟语义；测试语义；量子程序

英文摘要：

英文关键词： Concurrency theory；Probabilistic processes；Simulation semantics；Testing semantics；Quantum programs