进程代数是关于通信并发系统的代数理论的统称。 20世纪70年代后期，英国学者RMnner和C. A.R，分别提出了通信系统演算和通信顺序进程，开创了用代数方法研究通信并发系统的先河。 此后这一研究方向兴盛不衰，出现了众多类似而又 相互区别的演算系统，如ACP(提出者J.A.Ber郎tra 和J.W.K10p)，ATp(提出者M.H即n樱y)，Meije(提出者G.Eudol，R.desi~)，LOTC6等，统称为进程代数。

简介

中国的研究者(林惠民)

简介

英文：Process Algebra

这些代数理论都使用通信，而不是共享存储，作为进程之间相互作用的基本手段，表现出面向分布式系统的特征。 在语法上，进程代数用一组算子作为进程的构件。算子的语义通常用结构化操作语义方法定义， 这样进程就可看成是带标号的变迁系统。进程代数 的一个显著特征是把并发性归结为非确定性，将并 发执行的进程的行为看成是各单个进程的行为的所 有可能的交错合成，即所谓交错语义。 进程代数研究的核心问题是进程的等价性，即在什么意义下两个进程的行为相同?在进程代数领域使用的最为广泛的等价关系有互模拟、测试等价、 失败等价(参见通信顺序进程)等。对这些语义等价 关系均建立了相应的公理系统。关于公理系统的研 究不仅加深了对语义理论的理解，而且使得有可能 对语义等价关系进行形式推理。 为了将进程代数的理论成果应用于解决实际问题，20世纪80年代后期出现了许多计算机支持工具。用这些工具可对进程的行为进行推理或模拟。

中国的研究者

林惠民

林惠民院士主要从事软件的基础性研究。计算机是一种工具，大部分的人是在进行应用研究，即如何利用现有的理论和模型来开发出更有用的东西。而基础性研究与应用研究不同，它不仅要关心怎么样，还要知道为什么这样，要能够提出新的模型和方法。计算机软件科学的特点是基础研究和应用研究是紧密结合的，而且时效性非常强，基础研究的最新成果很快就会应用到工程中去。林惠民院士从事的一项工作是关于并发程序的形式语义学及形式化方法的研究。他和他的同事设计并实现了世界上第一个通用的进程代数验证工具。进程代数的实际应用离不开计算机辅助工具的支持。八十年代后期，一批进程代数验证工具应运而生（如CWB, PSF, LOTOSphere等），其共同局限性是每一工具只适用于某一特定的进程演算。这种局限性妨碍了验证工具的推广应用。如何克服这种局限性是当时国际进程代数界面临的一个重大挑战。这些验证工具无法做到通用，根本原因在于缺乏既能描述不同进程演算的语义，又能为计算机所理解的通用语言。经过对不同演算的反复比较，并考虑到在计算机上实现的可能性，他提炼出了一个元语言，用它可以描述各种进程演算的公理化语义，并且具有良好的可读性。在此基础上实现了通用的交互式进程代数验证工具PAM，只要将这个元语言描述的进程演算定义输入PAM，就得到该演算的证明器。PAM可同时接受多个不同的演算，对每个演算又可生成多个证明窗口。这是世界上第一个通用的进程代数证明工具。1993年他又利用当时刚刚取得的关于消息传送进程证明系统的理论结果，对PAM加以扩充，研制成迄今世界上唯一能对付消息传送进程的验证工具VPAM。PAM和VPAM都是通过ftp在Internet上公开发行的，其用户遍布各大洲，包括美国、加拿大、英、法、德、意、荷兰、丹麦、瑞典、斯洛伐克、巴西、印度、新西兰、南非等十几个国家，其中既有来自大学的，也有来自菲利普、惠普和贝尔等著名公司实验室的。