Abstract
The web service composition problem can be stated as follows: given a finite state machine M, representing a service business protocol, and a set of finite state machines \(\mathcal {R}\), representing the business protocols of existing services, the question is to check whether there is a simulation relation between M and the shuffle product closure of \(\mathcal {R}\).
This paper studies the impact of several parameters on the complexity of this problem. We show that the problem is Exptime-complete if we bound either: (i) the number of instances of services in \(\mathcal {R}\) that can be used in a composition, or(ii) the number of instances of services in \(\mathcal {R}\) that can be used in parallel, or (iii) the number of the so-called hybrid states in the finite state machines of \(\mathcal {R}\) by 0, 1 or 2. The problem is still open for 3 hybrid states.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Abramowitz, M., Stegun, I.A.: Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables. Dover, ninth dover printing, tenth gpo printing edition (1964)
Alonso, G., Casati, F., Kuno, H., Machiraju, V.: Web Services: Concepts, Architectures and Applications. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-662-10876-5
Benatallah, B., Casati, F., Toumani, F.: Web service conversation modeling: a cornerstone for e-business automation. IEEE Internet Comput. 08(1), 46–54 (2004)
Benatallah, B., Casati, F., Toumani, F.: Representing, analysing and managing web service protocols. Data Knowl. Eng. 58(3), 327–357 (2006)
Berardi, D., Calvanese, D., De Giacomo, G., Hull, R., Mecella, M.: Automatic composition of transition-based semantic web services with messaging. In: VLDB, pp. 613–624 (2005)
Berardi, D., Calvanese, D., De Giacomo, G., Hull, R., Mecella, M.: Automatic composition of web services in colombo (2005)
Brázdil, T., Jančar, P., Kučera, A.: Reachability games on extended vector addition systems with states. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6199, pp. 478–489. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14162-1_40
Bultan, T., Fu, X., Hull, R., Su, J.: Conversation specification: a new approach to design and analysis of e-service composition. In: WWW 2003. ACM (2003)
Chaloupka, J.: Z-reachability problem for games on 2-dimensional vector addition systems with states is in P. In: Kučera, A., Potapov, I. (eds.) RP 2010. LNCS, vol. 6227, pp. 104–119. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15349-5_7
Courtois, J.-B., Schmitz, S.: Alternating vector addition systems with states. In: Csuhaj-Varjú, E., Dietzfelbinger, M., Ésik, Z. (eds.) MFCS 2014. LNCS, vol. 8634, pp. 220–231. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44522-8_19
Ragab Hassen, R., Nourine, L., Toumani, F.: Protocol-based web service composition. In: Bouguettaya, A., Krueger, I., Margaria, T. (eds.) ICSOC 2008. LNCS, vol. 5364, pp. 38–53. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-89652-4_7
Henzinger, M.R., Henzinger, T.A., Kopke, P.W.: Computing simulations on finite and infinite graphs. In: Proceedings of 36th Annual Symposium on Foundations of Computer Science, pp. 453–462. IEEE (1995)
Jedrzejowicz, J., Szepietowski, A.: Shuffle languages are in p. Theor. Comput. Sci. 250(1–2), 31–53 (2001)
Lasota, S.: Expspace lower bounds for the simulation preorder between a communication-free petri net and a finite-state system. Inf. Process. Lett. 109(15), 850–855 (2009)
Muscholl, A., Walukiewicz, I.: A lower bound on web services composition. Logical Methods Comput. Sci. 4(2), 1–14 (2008)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer-Verlag GmbH Germany, part of Springer Nature
About this chapter
Cite this chapter
Ennaoui, K., Nourine, L., Toumani, F. (2018). Complexity Aspects of Web Services Composition. In: Koutny, M., Kristensen, L., Penczek, W. (eds) Transactions on Petri Nets and Other Models of Concurrency XIII. Lecture Notes in Computer Science(), vol 11090. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-58381-4_6
Download citation
DOI: https://doi.org/10.1007/978-3-662-58381-4_6
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-58380-7
Online ISBN: 978-3-662-58381-4
eBook Packages: Computer ScienceComputer Science (R0)