Computational Complexity of Web Service Composition Based on Behavioral Descriptions
Authors:
- Hyunyoung KilHKHyunyoung Kil
- Wonhong NamWNWonhong Nam
- Dongwon LeeDLDongwon Lee
- 1 November 2008
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 1, 359-363
Abstract
The Web service composition (WSC) problem on behavioral descriptions deals with the automatic construction of a coordinator web service to control a set of web services to reach the goal states. As such, WSC is one of the fundamental techniques to enable the Service Oriented Architecture on the Web. Despite its importance and implications, however, very few studies exist on the computational complexities of the WSC problem. In this paper, we present two novel theoretical findings on WSC problems: (1) Solving the WSC problem with "complete" information is EXP-hard, and (2) Solving the WSC problem with "incomplete" information is 2-EXP-hard. These findings imply that more efforts to devise efficient approximate solutions to the WSC problem be needed.Keywords
This publication has 3 references indexed in Scilit:
- Type-Aware Web Service Composition Using Boolean Satisfiability Solver2008 10th IEEE Conference on E-Commerce Technology and the Fifth IEEE Conference on Enterprise Computing, E-Commerce and E-Services, 2008
- Tools for composite web servicesACM SIGMOD Record, 2005
- AlternationJournal of the ACM, 1981