进程演算的比较语义研究

《进程演算的比较语义研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要摘要随着计算机技术和网络通信技术的高速发展，以并发性、分布性、实时性、异构性和互操作性等为主要特征的并发分布式系统已成为计算机技术的主流方向。并发现象以其固有的复杂性，对计算机科学家提出了挑战。与顺序计算不同，我们对并行与并发计算实质的认识尚处于初级阶段。并行与并发计算模型仍是计算机科学研究的重要问题。从Milner提出CCS以来，各种从不同侧面反映并发本质的模型被相继提出。在这些模型中，进程代数(如CCS)因概念简洁，可用的数学工具丰富，得到了广泛的研究。-演算是通信系统中可以用来表示含有变换的结构的进程的一种演算。不仅是系统中的组成部分可以任意的互连，相邻部分

2、的通信也可以包含能够改变连接情况的信息。-演算是对CCS的扩展，Engberg和Nielsen向CCS中加入了移动性，同时保持了其的代数性质。-演算消息了变量和常量间的区别，通信通道用名来表示，而计算则通过名的交互来表示。在理论计算科学领域，互模拟(bisimulation)是状态迁移系统间的一种二元关系，两个相互关联的系统，其中一个系统可以以相同的方式来模拟另外一个系统的动作。当两个系统能够互相模拟对方的动作时，就把这两系统称为互模拟的(bisimilar)。也就是说，观察者无法区分开这两个系统。在本文中，我们学习了-演算及spi-演算中的多种互模拟关系。给出了

3、多种互模拟之间的包含、等价关系等，同时，给出了一些反例来揭示严格包含关系。此外，本文中还提到了移动进程演算中的测试等价关系，给出了一些测试先序的定义。关键词：进程演算，互模拟，-演算，spi-演算IAbstractAbstractWiththerapiddevelopmentofcomputertechnologyandnetworkcommunication,concurrentanddistributedsystemsthatfeatureconcurrency,distribution,realtime,heterogeneityandinteroperabil

4、ityhavebecomethemaindirectionofcurrentcomputertechnology.Thephenomenonofconcurrencychallengescomputerscientistsbyitsintrinsiccomplexity.Dieredfromthatofsequentiality,itsstudyisjustbeginning.SinceMilnerputforthCCS,manyconcurrentcomputationmodelshavebeenstudied.Amongthesemodels,processalge

5、bra,suchasCCS,arewidelystudiedbecauseofitsconciseconceptsandrichavailablemathematicaltools.The-calculus,isacalculusofcommunicatingsystemsinwhichonecannaturallyexpressprocesswithhavechangingstructure.Notonlymaythecomponentagentsofasystembearbitrarilylinked,butacommunicationbetweenneighbo

6、rsmaycarryinformationwhichchangesthelinkage.ThecalculusisanextensionoftheprocessalgebraCCS,followingworkbyEngbergandNielsenwhoaddedmobilitytoCCSwhilepreservingitsalgebraicproperties.The-calculusgainssimplicitybyremovingalldistinctionbetweenvariablesandconstants;communicationlinksareiden

7、tifiedbynames,andcomputationisrepresentedpurelyasthecommunicationofnamesacrosslinks.Intheoreticalcomputerscience,abisimulationisabinaryrelationbetweenstatetransitionsystem,associatingsystemswhichbehaveinthesamewayinthesensethatonesystemsimulatestheotherandvice-versa.Intuit