zbMATH — the first resource for mathematics

Algorithms and complexity of automata synthesis by asynchronous orchestration with applications to web services composition. (English) Zbl 1291.68277
Bonchi, Filippo (ed.) et al., Proceedings of the 1st interaction and concurrency experiences workshop (ICE 2008), Reykjavik, Iceland, July 6, 2008. Amsterdam: Elsevier. Electronic Notes in Theoretical Computer Science 229, No. 3, 3-18 (2009).
Summary: Composition of services is necessary for realizing complex tasks on the web. It has been characterized either as a plan synthesis problem or as a software synthesis problem: given a goal and a set of web services, generate a composition of the web services that satisfies the goal. We propose algorithms for performing automated web service composition. We also examine the composition of services from the perspective of computational complexity.
For the entire collection see [Zbl 1279.68006].
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
68M11 Internet topics
68Q45 Formal languages and automata
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Full Text: DOI
[1] Alvarez, C.; Balcázar, J.; Gabarró, J.; Sántha, M., Parallel complexity in the design and analysis of concurrent systems, (), 288-303
[2] Andrews, T.; Curbera, F.; Dholakia, H.; Goland, Y.; Klein, J.; Leymann, F.; Liu, K.; Roller, D.; Smith, D.; Thatte, S.; Trickovic, I.; Weerawarana, S., Business process execution language for web services (BPEL4WS), (2004)
[3] Ariba, Microsoft, IBM, ‘Web Services Description Language (WSDL)’. www.w3.org/TR/2001/ NOTE-wsdl-20010315, (2001).
[4] Arnold, A.; Vincent, A.; Walukiewicz, I., Games for synthesis of controllers with partial observation, Theoretical computer science, 303, 7-34, (2003) · Zbl 1175.93148
[5] Berardi, D.; Calvanese, D.; De Giacomo, G.; Hull, R.; Mecella, M., Automated composition of transition-based semantic web services with messaging, (), 613-624
[6] Berardi, D.; Calvanese, D.; De Giacomo, G.; Lenzerini, M.; Mecella, M., Automatic composition of e-services that export their behavior, (), 43-58
[7] Berardi, D.; Cheikh, F.; De Giacomo, G.; Patrizi, F., Automatic service composition via simulation, International journal of foundations of computer science, 19, 429-451, (2008), World Scientific Publishing · Zbl 1155.68014
[8] Berwanger, D.; Grädel, E.; Lenzi, G., The variable hierarchy of the μ-calculus is strict, Theory of computing systems, 40, 437-466, (2007) · Zbl 1121.68072
[9] Cheikh, F.; De Giacomo, G.; Mecella, M., Automatic web services composition in trust-aware communities, (), 43-52
[10] De Giacomo, G., M. De Leoni, M. Mecella, F. Patrizi, ‘Automatic workflows composition of mobile services’. In: ‘Proceedings of the IEEE International Conference on Web Services’. International Conference on Web Services (2007) 823-830
[11] Fitting, M., Proof methods for modal and intuitionistic logic, (1983), Reidel · Zbl 0523.03013
[12] Huhns, M., Agents as web services, IEEE Internet computing, 6, 93-95, (2002)
[13] Jategaonkar, L.; Meyer, A., Deciding true concurrency equivalences on safe, finite nets, Theoretical computer science, 154, 107-143, (1996) · Zbl 0877.68056
[14] Kavantzas, N.; Burdett, D., Web services choreography description language (WS-CDL), (2004)
[15] König, D.; Lohmann, N.; Moser, S.; Stahl, C.; Wolf, K., Extending the compatibility notion for abstract WS-BPEL processes, (), 785-794
[16] Melliti, T.; Haddad, S.; Suna, A.; El Fallah Seghrouchni, A., Web - MASI: multi-agent systems interoperability using a web services based approach, (), 739-742
[17] Milanovic, N.; Malek, M., Current solutions for web service composition, IEEE Internet computing, 8, 51-59, (2004)
[18] Müller, I.; Kowalczyk, R.; Braun, P., Towards agent-based coalition formation for service composition, (), 73-80
[19] Murata, T., Petri nets: properties, analyses and applications, Proceedings of the IEEE, 17, 541-574, (1989)
[20] Papadimitriou, C., Computational complexity, (1994), Addison-Wesley · Zbl 0833.68049
[21] Pistore, M.; Barbon, F.; Bertoli, P.; Shaparau, D.; Traverso, P., (), 106-115
[22] Pistore, M., A. Marconi, P. Bertoli, P. Traverso, ‘Automated composition of Web services by planning at the knowledge level’. In: ‘Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence’. International Joint Conferences on Artificial Intelligence (2005) 1252-1259
[23] Ross-Talbot, S., Web services choreography and process algebra, (2004)
[24] Sardiña, S., F. Patrizi, G. De Giacomo, ‘Automatic synthesis of global behavior from multiple distributed behaviors’. In: ‘Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence’. Conference on Artificial Intelligence (2007) 1063-1069
[25] Traverso, P.; Pistore, M., Automated composition of semantic web services into executable processes, (), 380-394
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.