W. M. Van-der-aalst, THE APPLICATION OF PETRI NETS TO WORKFLOW MANAGEMENT, Journal of Circuits, Systems and Computers, vol.08, issue.01, pp.21-66, 1998.
DOI : 10.1142/S0218126698000043

R. Alur and D. L. Dill, A theory of timed automata, Theoretical Computer Science, vol.126, issue.2, pp.183-235, 1994.
DOI : 10.1016/0304-3975(94)90010-8

R. Alur, L. Fix, and T. A. Henzinger, Event-clock automata: a determinizable class of timed automata, Theoretical Computer Science, vol.211, issue.1-2, pp.253-273, 1999.
DOI : 10.1016/S0304-3975(97)00173-4

R. Alur and P. Madhusudan, Decision Problems for Timed Automata: A Survey, In SFM, pp.1-24, 2004.
DOI : 10.1007/978-3-540-30080-9_1

K. Ba¨?naba¨?na, B. Benatallah, F. Casati, and F. Toumani, Model-driven web service development, CAiSE, pp.290-306, 2004.

G. Behrmann, A. David, and K. Larsen, A Tutorial on Uppaal, SFM, pp.200-236, 2004.
DOI : 10.1007/978-3-540-30080-9_7

B. Benatallah, F. Casati, D. Grigori, H. R. Nezhad, and F. Toumani, Developing Adapters for Web Services Integration, CAiSE, pp.415-429, 2005.
DOI : 10.1007/11431855_29
URL : https://hal.archives-ouvertes.fr/hal-00130695

B. Benatallah, F. Casati, J. Ponge, and F. Toumani, Compatibility and replaceability analysis for timed web service protocols, BDA, 2005.

B. Benatallah, F. Casati, J. Ponge, and F. Toumani, On temporal abstractions of web service protocols, CAiSE Short Paper Proceedings, 2005.

B. Benatallah, F. Casati, and F. Toumani, Analysis and Management of Web Service Protocols, Proceedings of ER 2004, 2004.
DOI : 10.1007/978-3-540-30464-7_40
URL : https://hal.archives-ouvertes.fr/hal-00108735

B. Benatallah, F. Casati, and F. Toumani, Web service conversation modeling: a cornerstone for e-business automation, IEEE Internet Computing, vol.8, issue.1, pp.46-54, 2004.
DOI : 10.1109/MIC.2004.1260703
URL : https://hal.archives-ouvertes.fr/hal-00108317

B. Benatallah, F. Casati, and F. Toumani, Representing, analysing and managing Web service protocols, Data & Knowledge Engineering, vol.58, issue.3, pp.327-357, 2006.
DOI : 10.1016/j.datak.2005.07.006
URL : https://hal.archives-ouvertes.fr/hal-00107196

B. Benatallah, F. Casati, F. Toumani, and R. Hamadi, Conceptual Modeling of Web Service Conversations, CAiSE, pp.449-467, 2003.
DOI : 10.1007/3-540-45017-3_31
URL : https://hal.archives-ouvertes.fr/hal-00108740

B. Benatallah, F. Casati, F. Toumani, J. Ponge, and H. Nezhad, Service Mosaic: A Model-Driven Framework for Web Services Life-Cycle Management, IEEE Internet Computing, vol.10, issue.4, pp.55-63, 2006.
DOI : 10.1109/MIC.2006.87

B. Bérard and C. Dufourd, Timed automata and additive clock constraints, Information Processing Letters, vol.75, issue.1-2, pp.1-7, 2000.
DOI : 10.1016/S0020-0190(00)00075-2

B. Bérard, A. Petit, V. Diekert, and P. Gastin, Characterization of the expressive power of silent transitions in timed automata, Fundam. Inform, vol.36, issue.2-3, pp.145-182, 1998.

D. Berardi, Automatic composition services: models, techniques and tools, phd thesis, 2002.

D. Berardi, F. D. Rosa, L. De-santis, and M. Mecella, Finite state automata as conceptual model for e-services, J. Integr. Des. Process Sci, vol.8, issue.2, pp.105-121, 2004.

P. A. Bernstein and S. Melnik, Industrial-strength schema matching, ACM SIGMOD Record, vol.33, issue.4, pp.38-43, 2004.
DOI : 10.1145/1041410.1041417
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.60.2699

C. Bettini, X. S. Wang, and S. Jajodia, Temporal reasoning in workflow systems, Distributed and Parallel Databases, vol.11, issue.3, pp.269-306, 2002.
DOI : 10.1023/A:1014048800604

D. Beyer, A. Chakrabarti, and T. A. Henzinger, Web service interfaces, Proceedings of the 14th international conference on World Wide Web , WWW '05, pp.148-159, 2005.
DOI : 10.1145/1060745.1060770

P. Bouyer, C. Dufourd, E. Fleury, and A. Petit, Updatable timed automata, Theoretical Computer Science, vol.321, issue.2-3, pp.291-345, 2004.
DOI : 10.1016/j.tcs.2004.04.003
URL : https://hal.archives-ouvertes.fr/hal-00350196

P. Bouyer, S. Haddad, and P. Reynier, Undecidability results for timed automata with silent transitions, 2007.

P. Bouyer, F. Laroussinie, and P. Reynier, Diagonal Constraints in Timed Automata: Forward Analysis of Timed Systems, In FORMATS, pp.112-126, 2005.
DOI : 10.1007/11603009_10

T. Bultan, Modeling interactions of web software (invited paper), 2006.

T. Bultan, J. Su, and X. Fu, Analyzing conversations of Web services, IEEE Internet Computing, vol.10, issue.1, pp.18-25, 2006.
DOI : 10.1109/MIC.2006.1

C. Bussler, Process Inheritance, Proceedings of CAiSE'02, pp.701-705, 2002.
DOI : 10.1007/3-540-47961-9_49

C. Canal, L. Fuentes, E. Pimentel, J. M. Troya, and A. Vallecillo, Adding roles to CORBA objects, IEEE Transactions on Software Engineering, vol.29, issue.3, pp.242-260, 2003.
DOI : 10.1109/TSE.2003.1183935
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.219.3798

E. De-maria, A. Montanari, and M. Zantoni, An automaton-based approach to the verification of timed workflow schemas, Thirteenth International Symposium on Temporal Representation and Reasoning (TIME'06), pp.87-94, 2006.
DOI : 10.1109/TIME.2006.6

G. Díaz, M. Cambronero, J. Pardo, V. Valero, and F. Cuartero, Automatic generation of Correct Web Services Choreographies and Orchestrations with Model Checking Techniques, Advanced Int'l Conference on Telecommunications and Int'l Conference on Internet and Web Applications and Services (AICT-ICIW'06), p.186, 2006.
DOI : 10.1109/AICT-ICIW.2006.53

P. Volker-diekert, A. Gastin, and . Petit, Removing epsilon-transitions in timed automata, STACS, pp.583-594, 1997.

H. Foster, S. Uchitel, J. Magee, and J. Kramer, Leveraging Eclipse for integrated model-based engineering of web service compositions, Proceedings of the 2005 OOPSLA workshop on Eclipse technology eXchange , eclipse '05, pp.95-99, 2005.
DOI : 10.1145/1117696.1117716

X. Fu, T. Bultan, and J. Su, Analysis of interacting BPEL web services, Proceedings of the 13th conference on World Wide Web , WWW '04, pp.621-630, 2004.
DOI : 10.1145/988672.988756

C. Girault and R. Valk, Petri Nets for System Engineering: A Guide to Modeling, Verification, and Applications, 2001.
DOI : 10.1007/978-3-662-05324-9

J. E. Hopcroft, R. Motwani, and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, 2000.
DOI : 10.1145/568438.568455

R. Kazhamiakin, P. K. Pandya, and M. Pistore, Timed modelling and analysis in Web service compositions, First International Conference on Availability, Reliability and Security (ARES'06), pp.840-846, 2006.
DOI : 10.1109/ARES.2006.134

W. Kongdenfha, R. Saint-paul, B. Benatallah, and F. Casati, An Aspect-Oriented Framework for Service Adaptation, ICSOC, pp.15-26, 2006.
DOI : 10.1007/11948148_2

M. Mecella, B. Pernici, and P. Craca, Compatibility of e -services in a cooperative multi-platform environment, Procs. of TES '01, pp.44-57, 2001.

R. Hamid, R. Nezhad-motahari, B. Saint-paul, F. Benatallah, J. Casati et al., Servicemosaic: Interactive analysis and manipulation of service conversations, ICDE, pp.1497-1498, 2007.

S. Nejati, M. Sabetzadeh, M. Chechik, S. M. Easterbrook, and P. Zave, Matching and Merging of Statecharts Specifications, 29th International Conference on Software Engineering (ICSE'07), pp.54-64, 2007.
DOI : 10.1109/ICSE.2007.50

R. Hamid, R. Motahari-nezhad, B. Saint-paul, F. Benatallah, and . Casati, Protocol discovery from imperfect service interaction logs, ICDE, pp.1405-1409, 2007.

H. R. , M. Nezhad, B. Benatallah, A. Martens, F. Curbera et al., Semi-automated adaptation of service interactions, WWW '07: Proceedings of the 16th international conference on World Wide Web, pp.993-1002, 2007.

M. P. Papazoglou and D. Georgakopoulos, Introduction, Communications of the ACM, vol.46, issue.10, pp.24-28, 2003.
DOI : 10.1145/944217.944233

J. Ponge, B. Benatallah, F. Casati, and F. Toumani, Fine-Grained Compatibility and Replaceability Analysis of Timed Web Service Protocols, ER, pp.599-614, 2007.
DOI : 10.1007/978-3-540-75563-0_40

Z. Qiu, X. Zhao, C. Cai, and H. Yang, Towards the theoretical foundation of choreography, Proceedings of the 16th international conference on World Wide Web , WWW '07, pp.973-982, 2007.
DOI : 10.1145/1242572.1242704

E. Rahm and P. A. Bernstein, A survey of approaches to automatic schema matching, The VLDB Journal, vol.10, issue.4, pp.334-350, 2001.
DOI : 10.1007/s007780100057

F. Laurentiu, T. , and G. Macovei, E-timed workflow nets, SYNASC, pp.423-429, 2006.

W. Van-der-aalst, Inheritance of Business Processes: A Journey Visiting Four Notorious Problems, 2003.
DOI : 10.1007/978-3-540-40022-6_19

D. M. Yellin and R. E. Storm, Protocol specifications and component adaptors, ACM Transactions on Programming Languages and Systems, vol.19, issue.2, pp.292-333, 1997.
DOI : 10.1145/244795.244801

. Proof, We need to show that ?-transitions in protocol timed automata cannot always be removed, i.e., there are protocol timed automata for which there doesn't exist equivalent automata without ?-transitions. To do that, we exhibit the protocol timed automaton A depicted on Figure 13 and use the notions of precise time and precise actions that were introduced in the Theorem 24 of [16] as a tool to identify timed languages that can only be recognized by timed automata featuring ?-transitions. The proof is virtually the same as the one of Corollary 29 in