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

Secondary volumes: Selected Papers of the 10th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS 2007)

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, 2018, Complexity Aspects of Web Services Composition, Lecture notes in computer science, pp. 116-135, 10.1007/978-3-662-58381-4_6.

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

Tushant Jha;Walid Belkhir;Yannick Chevalier;Michael Rusinowitch, 2016, Expressive Equivalence and Succinctness of Parametrized Automata with Respect to Finite Memory Automata, Lecture notes in computer science, pp. 145-156, 10.1007/978-3-662-50539-7_12.

Hikmat Farhat;Guillaume Feuillade, 2015, On-the-fly algorithm for the service composition problem, pp. 1-6, 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.

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

Hikmat Farhat;Guillaume Feuillade, 2012, A symbolic method for the web service composition problem, ePrints Soton (University of Southampton), pp. 182-185, 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, 2012, A Comparison of Succinctly Represented Finite-State Systems, Lecture notes in computer science, pp. 147-161, 10.1007/978-3-642-32940-1_12.

Fabio Patrizi, 2009, An Introduction to Simulation-Based Techniques for Automated Service Composition, Electronic Proceedings in Theoretical Computer Science, 2, pp. 37-49, 10.4204/eptcs.2.4, https://doi.org/10.4204/eptcs.2.4.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 3138 times.

This article's PDF has been downloaded 561 times.