  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.
