TY - GEN
T1 - Computational complexity of web service composition based on behavioral descriptions
AU - Kil, Hyunyoung
AU - Nam, Wonhong
AU - Lee, Dongwon
PY - 2008
Y1 - 2008
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=57649219787&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=57649219787&partnerID=8YFLogxK
U2 - 10.1109/ICTAI.2008.47
DO - 10.1109/ICTAI.2008.47
M3 - Conference contribution
AN - SCOPUS:57649219787
SN - 9780769534404
T3 - Proceedings - International Conference on Tools with Artificial Intelligence, ICTAI
SP - 359
EP - 363
BT - Proceedings - 20th IEEE International Conference on Tools with Artificial Intelligence, ICTAI'08
T2 - 20th IEEE International Conference on Tools with Artificial Intelligence, ICTAI'08
Y2 - 3 November 2008 through 5 November 2008
ER -