1. Introduction
Web services and service-oriented architecture (SOA) in general have emerged in recent years as a major technology for deploying automated interactions between distributed and heterogeneous applications and have motivated a great deal of research on many topics such as service foundations, composition, management and monitoring as well as service design and development [1]. An inherent issue in all these topics is how to devise a formal specification of a Web service.