V. Benzaken, G. Castagna, and A. Frisch, CDuce: an XML-centric general-purpose language, Proceedings of the eighth ACM SIGPLAN international conference on Functional programming, ICFP '03, pp.51-63, 2003.
URL : https://hal.archives-ouvertes.fr/hal-00152619

S. Boag, D. Chamberlin, M. Fernández, D. Florescu, J. Robie et al., XQuery 1.0: An XML query language, W3C WDt, 2005.

D. Colazzo and C. Sartiani, Precision and complexity of XQuery type inference, Proceedings of the 13th international ACM SIGPLAN symposium on Principles and practices of declarative programming, PPDP '11, pp.89-100, 2011.
DOI : 10.1145/2003476.2003490
URL : https://hal.archives-ouvertes.fr/inria-00537161

D. Draper, M. Dyck, P. Fankhauser, M. Fernández, A. Malhotra et al., XQuery 1.0 and XPath 2.0 formal semantics, W3C recommendation, 2010.

M. F. Fernández and J. Siméon, Building an Extensible XQuery Engine: Experiences with Galax (Extended Abstract), Database and XML Technologies, Second International XML Database Symposium, pp.1-4, 2004.
DOI : 10.1007/978-3-540-30081-6_1

A. Fokoue, K. Rose, J. Siméon, and L. Villard, Compiling XSLT 2.0 into XQuery 1.0, Proceedings of the 14th international conference on World Wide Web , WWW '05, pp.682-691, 2005.
DOI : 10.1145/1060745.1060844
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.59.6188

P. Genevès, N. Layaïda, and V. Quint, Impact of XML Schema Evolution, ACM Transactions on Internet Technology, vol.11, issue.1, pp.1-4, 2011.
DOI : 10.1145/1993083.1993087

P. Genevès, N. Layaïda, and A. Schmitt, Efficient static analysis of XML paths and types, PLDI '07, pp.342-351, 2007.

H. Hosoya and B. C. Pierce, XDuce, ACM Transactions on Internet Technology, vol.3, issue.2, pp.117-148, 2003.
DOI : 10.1145/767193.767195

H. Hosoya, J. Vouillon, and B. C. Pierce, Regular expression types for XML, ACM Transactions on Programming Languages and Systems, vol.27, issue.1, pp.46-90, 2005.
DOI : 10.1145/1053468.1053470
URL : https://hal.archives-ouvertes.fr/hal-00009271

K. Inaba, H. Hosoya, and S. Maneth, Multi-Return Macro Tree Transducers, Implementation and Applications of Automata, 13th International Conference, CIAA, pp.102-111, 2008.
DOI : 10.1007/978-3-540-70844-5_11

C. Kirkegaard, A. Møller, and M. I. Schwartzbach, Static analysis of XML transformations in java, IEEE Transactions on Software Engineering, vol.30, issue.3, pp.181-192, 2004.
DOI : 10.1109/TSE.2004.1271173

S. Maneth, A. Berlea, T. Perst, and H. Seidl, XML type checking with macro tree transducers, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems , PODS '05, pp.283-294, 2005.
DOI : 10.1145/1065167.1065203

S. Maneth, T. Perst, and H. Seidl, Exact XML Type Checking in Polynomial Time, Lecture Notes in Computer Science, vol.4353, pp.254-268, 2007.
DOI : 10.1007/11965893_18

T. Milo, D. Suciu, and V. Vianu, Typechecking for XML transformers, Journal of Computer and System Sciences, vol.66, issue.1, pp.66-97, 2003.
DOI : 10.1016/S0022-0000(02)00030-2

A. Tozawa, Towards static type checking for XSLT, Proceedings of the 2001 ACM Symposium on Document engineering , DocEng '01, pp.18-27, 2001.
DOI : 10.1145/502187.502191

. Inferring-input-type, 1>T) root_empty returns: false expr_union returns:(~<-2>T & ~<-1>T) elem_elem element r {child::* } , r($1, $Epsilon) expr_union child::* , EPSILON | b($Epsilon, $Epsilon) | b($Epsilon, $2) child_empty: $v child::* , EPSILON child_empty returns (X1 & ~<1>T) expr_union child, Epsilon)|b($Epsilon,$2) child_elem: $v child::* , b($Epsilon, $Epsilon) child_elem returns:(b & ~<1>T & <-1>X1 & ~<2>T) child_elem: $v child::* , b($Epsilon, $2) child_elem returns:(b & ~<1>T & <-1>X1 & <2>(mu X2.((~<1>T & b & <2>X2) | (~<1>T & b & ~<2>T)))) expr_union returns:((b & ~<1>T & <-1>X1 & ~<2>T) | (b & ~<1>T & <-1>X1 & <2>(mu X2.((~<1>T & b & <2>X2) | (~<1>T & b & ~<2>T)))))

R. N°-8149 and R. Centre-grenoble-?-rhône-alpes, Inovallée 655 avenue de l'Europe Montbonnot 38334 Saint Ismier Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria, pp.249-6399