2007 | OriginalPaper | Chapter
A Lower Bound on Web Services Composition
Authors : Anca Muscholl, Igor Walukiewicz
Published in: Foundations of Software Science and Computational Structures
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.
Keywords:
Automata simulation, complexity, web services composition.