Recently, the temporal constraint satisfiability is regarded as an important criterion in Web service composition to guarantee its timely completion. This leads to a new challenge in analyzing the compatibility of Web services under temporal constraints. The existing methods either do not consider message mismatches between services in a composition or suffer from state-space explosion by verif…