N. Alon, T. Milo, F. Neven, D. Suciu, and V. Vianu, XML with data values, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems , PODS '01, pp.688-727, 2003.
DOI : 10.1145/375551.375570

M. Arenas, W. Fan, and L. Libkin, On the Complexity of Verifying Consistency of XML Specifications, SIAM Journal on Computing, vol.38, issue.3, pp.841-880, 2008.
DOI : 10.1137/050646895

M. Arenas and L. Libkin, XML data exchange: consistency and query answering, J. ACM, vol.55, issue.2, 2008.

H. Björklund and M. Bojanczyk, Bounded Depth Data Trees, ICALP'07, pp.862-874
DOI : 10.1007/978-3-540-73420-8_74

H. Björklund, W. Martens, and T. Schwentick, Optimizing Conjunctive Queries over Trees Using Schema Information, MFCS'08, pp.132-143
DOI : 10.1007/978-3-540-85238-4_10

M. Bojanczyk, A. Muscholl, T. Schwentick, and L. Segoufin, Two-variable logic on data trees and XML reasoning, J. ACM, vol.56, issue.3, 2009.
URL : https://hal.archives-ouvertes.fr/hal-00151833

M. Bojanczyk, C. David, A. Muscholl, T. Schwentick, and L. Segoufin, Two-Variable Logic on Words with Data, 21st Annual IEEE Symposium on Logic in Computer Science (LICS'06), pp.7-16
DOI : 10.1109/LICS.2006.51
URL : https://hal.archives-ouvertes.fr/hal-00151749

P. Bouyer, A. Petit, and D. Thérien, An Algebraic Characterization of Data and Timed Languages, pp.248-261
DOI : 10.1007/3-540-44685-0_17

D. Calvanese, G. De-giacomo, M. Lenzerini, and M. Y. Vardi, Regular XPath: constraints, query containment and view-based answering for XML documents, LID'08, 2008.

H. Comon, Tree Automata: Techniques and Applications, 2007.

S. Dal-zilio, D. Lugiez, and C. Meyssonnier, A logic you can count on, pp.135-146, 2004.
URL : https://hal.archives-ouvertes.fr/inria-00071562

S. Demri and R. Lazic, LTL with the freeze quantifier and register automata, ACM TOCL, vol.10, issue.3, 2009.

W. Fan and L. Libkin, On XML integrity constraints in the presence of DTDs, Journal of the ACM, vol.49, issue.3, pp.368-406, 2002.
DOI : 10.1145/567112.567117

D. Figueira, Satisfiability of downward XPath with data equality tests, Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, PODS '09, pp.197-206
DOI : 10.1145/1559795.1559827

R. Givan, D. A. Mcallester, C. Witty, and D. Kozen, Tarskian Set Constraints, Information and Computation, vol.174, issue.2, pp.105-131, 2002.
DOI : 10.1006/inco.2001.2973
URL : http://doi.org/10.1006/inco.2001.2973

M. Jurdzinski and R. Lazic, Alternation-free modal mu-calculus for data trees, 22nd Annual IEEE Symposium on Logic in Computer Science (LICS 2007), pp.131-140
DOI : 10.1109/LICS.2007.11

M. Kaminski and T. Tan, Tree Automata over Infinite Alphabets, In Pillars of Computer Science, pp.386-423, 2008.
DOI : 10.1007/978-3-540-78127-1_21

E. Kopczynski and A. W. To, Parikh Images of Grammars: Complexity and Applications, 2010 25th Annual IEEE Symposium on Logic in Computer Science, 2010.
DOI : 10.1109/LICS.2010.21

L. Libkin and C. Sirangelo, Reasoning about XML with temporal logics and automata, Journal of Applied Logic, vol.8, issue.2, pp.210-232, 2010.
DOI : 10.1016/j.jal.2009.09.005
URL : http://doi.org/10.1016/j.jal.2009.09.005

S. Malik and L. Zhang, Boolean satisfiability from theoretical hardness to practical success, Communications of the ACM, vol.52, issue.8, pp.76-82, 2009.
DOI : 10.1145/1536616.1536637

W. Martens, F. Neven, and T. Schwentick, Simple off the shelf abstractions for XML schema, ACM SIGMOD Record, vol.36, issue.3, pp.15-22, 2007.
DOI : 10.1145/1324185.1324188

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

F. Neven, Automata, Logic, and XML, CSL 2002, pp.2-26
DOI : 10.1007/3-540-45793-3_2

F. Neven, . Th, and . Schwentick, Query automata over finite trees, Theoretical Computer Science, vol.275, issue.1-2, pp.633-674, 2002.
DOI : 10.1016/S0304-3975(01)00301-2

F. Neven, . Th, V. Schwentick, and . Vianu, Towards Regular Languages over Infinite Alphabets, MFCS, pp.560-572, 2001.
DOI : 10.1007/3-540-44683-4_49
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.26.2304

L. Pacholski and A. Podelski, Set constraints: A pearl in research on constraints, CP'97, pp.549-562
DOI : 10.1007/BFb0017466

C. Papadimitriou, On the complexity of integer programming, Journal of the ACM, vol.28, issue.4, pp.765-768, 1981.
DOI : 10.1145/322276.322287

. Th and . Schwentick, XPath query containment, SIGMOD Record, vol.33, issue.1, pp.101-109, 2004.

H. Seidl, . Th, A. Schwentick, P. Muscholl, and . Habermehl, Counting in Trees for Free, pp.1136-1149, 2004.
DOI : 10.1007/978-3-540-27836-8_94
URL : https://hal.archives-ouvertes.fr/hal-00159525

J. W. Thatcher, Characterizing derivation trees of context-free grammars through a generalization of finite automata theory, Journal of Computer and System Sciences, vol.1, issue.4, pp.317-322, 1967.
DOI : 10.1016/S0022-0000(67)80022-9

K. N. Verma, H. Seidl, and T. , Schwentick On the Complexity of Equational Horn Clauses, CADE 2005, pp.337-352

V. Vianu, A web Odyssey: from Codd to XML, PODS'01, pp.1-15

D. West, Introduction to Graph Theory, 2001.