关于并发系统分支互模拟关系发散性保持的研究

带发散性说明的分支互模拟是van Glabbeek和Weijland提出的一个概念,并被用来定义等价关系.该等价关系应该是最弱的一个发散性保持的并且满足分支互模拟性质的等价关系.然而在概念提出时并没有提供这些重要性质的证明,并且我们认为在原定义的基础上这个证明是不显然的.本文通过co-induction的手段利用染色迹的概念定义了着色完全迹等价,并证明该等价关系是最弱的一个保持发散的并且满足分支互模拟性质的等价关系.然后我们证明了着色完全迹等价关系和≈_b^△是相同的,因而补充了van Glabbeek和Weijland的工作,即证明了≈_b^△是最弱的一个保持发散的并且是满足分支互模拟性质的等价关系.     

传名调用演算的二值传递CPS变换

为Plotkin带常数传名调用λ演算定义了一个新的CPS(continuation-passing-style)变换方法.方法基于求值上下文变换,新颖之处在于,每次传递二值给继续而不是常规的一值.先给出二值CPS变换编码,再在此基础上定义CPS语言,最后建立源语言和CPS语言的一一映射关系并证明Plotkin的模拟定理.与Plotkin的工作比较,工作特点在于,给出了一个CPS归约闭语言,该语言中所有继续都可以用函数形式表达,且模拟定理的可靠性和完备性方向证明更为简单.