Web services are form of middleware to exchange information between systems over a network. With the advent of the age of mobile devices and their diversity, the importance of web services became all the more apparent. Every web service grants certain functionality and can utilize other web services to gain more functionality and more robustness. Such a service that combines the functionality of other services is called a composite service and the process of designing such a service is called a composition. This thesis studies an on-the-fly algorithm that efficiently checks for the possibility ...