近年来,随着互联网技术与网络应用程序的迅速发展,基于Web服务的分布式计算模式正在成为技术发展的新趋势。Web服务是一种基于网络的、分布式的、自描述的、模块化的组件,它按照一定的规范,实现特定的功能,提供了面向Internet应用程序的统一的服务注册、发现、绑定和集成的机制。而Web服务组合可以使多个服务合作协调工作,以实现更加复杂的功能,成为广域环境下实现互操作的一种主要机制。Web服务组合是Web服务的研究重点。为了确保多个服务之间可以协调工作,实现特定的功能,需要参与合成的各个服务的行为满足一定的条件,从而达到各服务之间行为兼容的目的。另外为了保证服务组合的灵活性,需要考虑服务之间的替换性关系,即在服务组合的过程中,用一个新的服务替换一个参与合成的服务,并且替换后的服务不会引起服务组合中出现不相容的关系。本文提出了两个Web服务协调工作时相容性的判定标准,并且根据这一判定标准,设计了一种基于进程代数和自动机的形式化的判定方法,并结合实例加以说明。另外一方面,根据服务替换性的要求,通过逐步精化,提炼出服务替换性的充分必要条件,并且加以证明；然后根据这些条件,得到一些有用的推论,应用这些推论可以简化服务替换性的判定；最后讨论了服务相容性与服务替换性的关系。