A lower bound on web services composition

Anca Muscholl; Igor Walukiewicz

doi:10.2168/LMCS-4(2:5)2008

Anca Muscholl ; Igor Walukiewicz - A lower bound on web services composition

lmcs:824 - Logical Methods in Computer Science, May 15, 2008, Volume 4, Issue 2 - https://doi.org/10.2168/LMCS-4(2:5)2008

A lower bound on web services compositionArticle

Authors: Anca Muscholl ; Igor Walukiewicz

A web service is modeled here as a finite state machine. A composition problem for web services is to decide if a given web service can be constructed from a given set of web services; where the construction is understood as a simulation of the specification by a fully asynchronous product of the given services. We show an EXPTIME-lower bound for this problem, thus matching the known upper bound. Our result also applies to richer models of web services, such as the Roman model.

https://doi.org/10.2168/LMCS-4(2:5)2008

Source: arXiv.org:0804.3105

Volume: Volume 4, Issue 2

Published on: May 15, 2008

Imported on: September 21, 2007

Keywords: Computer Science - Logic in Computer Science,F.1.2,F.3.1

Licence: arXiv.org - Non-exclusive license to distribute

Classifications

Mathematics Subject Classification 2020¹

68M10 - Network design and communication in computer systems

Sources:

[1] zbMATH Open.

Bibliographic References

11 Documents citing this article

Hikmat Farhat, 2018, Composition of Partially-Observable Services, IEEE Access, 7, pp. 2281-2290, 10.1109/access.2018.2885948, https://doi.org/10.1109/access.2018.2885948.

Karima Ennaoui;Lhouari Nourine;Farouk Toumani, Complexity Aspects of Web Services Composition, pp. 116-135, 2018, 10.1007/978-3-662-58381-4_6, https://hal.archives-ouvertes.fr/hal-01179719.

Ronen I. Brafman;Giuseppe De Giacomo;Massimo Mecella;Sebastian Sardina, IRIS Research product catalog (Sapienza University of Rome), Service Composition in Stochastic Settings, pp. 159-171, 2017, 10.1007/978-3-319-70169-1_12, http://hdl.handle.net/11573/1073204.

Tushant Jha;Walid Belkhir;Yannick Chevalier;Michael Rusinowitch, Expressive Equivalence and Succinctness of Parametrized Automata with Respect to Finite Memory Automata, pp. 145-156, 2016, 10.1007/978-3-662-50539-7_12, https://hal.inria.fr/hal-01224144.

Hikmat Farhat;Guillaume Feuillade, On-the-fly algorithm for the service composition problem, pp. 1-6, 2015, Paris, France, 10.1109/ntms.2015.7266511, https://hal.science/hal-03198232.

Giuseppe De Giacomo;Fabio Patrizi;Sebastian Sardiña, 2013, Automatic behavior composition synthesis, Artificial Intelligence, 196, pp. 106-142, 10.1016/j.artint.2012.12.001, https://doi.org/10.1016/j.artint.2012.12.001.

Walid Belkhir;Yannick Chevalier;Michael Rusinowitch, 2013 15th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, Fresh-Variable Automata: Application to Service Composition, 229, pp. 153-160, 2013, Timisoara, Romania, 10.1109/synasc.2013.28.

Hikmat Farhat;Guillaume Feuillade, 2012 2nd International Conference on Advances in Computational Tools for Engineering Applications (ACTEA), A symbolic method for the web service composition problem, pp. 182-185, 2012, Beirut, Lebanon, 10.1109/ictea.2012.6462862.

Mu Li;Bo Li;JinPeng Huai, 2012, Reliability-aware automatic composition approach for web services, Science China Information Sciences, 55, 4, pp. 921-937, 10.1007/s11432-011-4545-8.

Romain Brenguier;Stefan Göller;Ocan Sankur, CiteSeer X (The Pennsylvania State University), A Comparison of Succinctly Represented Finite-State Systems, pp. 147-161, 2012, 10.1007/978-3-642-32940-1_12, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.396.9684.

Fabio Patrizi, 2009, An Introduction to Simulation-Based Techniques for Automated Service Composition, arXiv (Cornell University), 2, pp. 37-49, 10.4204/eptcs.2.4.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 1581 times.

This article's PDF has been downloaded 424 times.