论文部分内容阅读
不确定性现象广泛存在于纷繁芜杂的现实生活里,因而计算机程序中的非确定性计算是计算机科学的主要研究课题之一.非确定性计算和可能性计算是两种重要的计算模型,两者的语义研究已经取得了一些进展.但是可能性计算理论属于新兴领域,其很多方面仍需进一步发展与完善.非确定性计算和可能性计算的模块化语义不能很好地结合就是当前并行计算中亟待解决的问题.本文在现有的研究成果之上继续讨论非确定性monad和可能性估值幂domain的monad的结合问题,主要内容包含以下几个方面: 第一章中,介绍了计算的实质以及非确定性计算的广泛应用,简述了非确定性计算从初始地体现在设备中到后来上升至用幂domain来刻画的发展史.随后,初步介绍了可能性理论的理解和意义以及其作为前沿研究领域所获得的关注和探索.在此基础上,提出了本文的核心内容和思想并且给出了一些预备知识. 第二章中,我们展开了对非确定性monad和可能性估值幂domain的monad之间分配律的探索.首先定义了有限可能性估值monad,举例说明了有限可能性估值monad和非确定性monad之间的分配律在集合范畴,DCPO范畴以及Domain范畴上都不存在.进而证明了在这三种范畴上,可能性估值幂domain的monad和非确定性monad之间分配律也不存在. 第三章中,在集合范畴上,我们定义了表征有限可能性估值,并证明了表征有限可能性估值monad对非确定性monad的分配律是存在的,这为解决非确定性和可能性计算的模块化语义的结合问题,提供了思路. 第四章中,在Domain范畴上,我们提出了表征可能性估值幂domain,借助抽象基的性质通过过渡映射证明了表征可能性估值幂domain的monad对Hoare非确定性monad存在分配律,进一步完善了指称语义的研究.