S. Abiteboul, P. Bourhis, A. Muscholl, and Z. Wu, Recursive queries on trees and data trees, Proceedings of the 16th International Conference on Database Theory, ICDT '13, pp.93-104, 2013.
DOI : 10.1145/2448496.2448509
URL : https://hal.archives-ouvertes.fr/hal-00809297

V. Benzaken, G. Castagna, K. Nguyen, and J. Siméon, Static and dynamic semantics of NoSQL languages, pp.101-114, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00797956

A. Boiret, V. Hugot, J. Niehren, and R. Treinen, Deterministic Automata for Unordered Trees, Electronic Proceedings in Theoretical Computer Science, vol.161, 2014.
DOI : 10.4204/EPTCS.161.17
URL : https://hal.archives-ouvertes.fr/hal-01020236

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), p.27, 2011.
DOI : 10.1109/LICS.2006.51
URL : https://hal.archives-ouvertes.fr/hal-00151749

I. Boneva and J. M. Talbot, Automata and Logics for Unranked and Unordered Trees, RTA. LNCS, pp.500-515, 2005.
DOI : 10.1007/978-3-540-32033-3_36
URL : https://hal.archives-ouvertes.fr/inria-00536694

J. R. Büchi, Weak Second-Order Arithmetic and Finite Automata, Zeitschrift f??r Mathematische Logik und Grundlagen der Mathematik, vol.9, issue.1-6, pp.66-92, 1960.
DOI : 10.1002/malq.19600060105

B. Courcelle, The monadic second-order logic of graphs. I. Recognizable sets of finite graphs, Information and Computation, vol.85, issue.1, pp.12-75, 1990.
DOI : 10.1016/0890-5401(90)90043-H
URL : https://hal.archives-ouvertes.fr/hal-00353765

D. Figueira, On XPath with transitive axes and data tests, Proceedings of the 32nd symposium on Principles of database systems, PODS '13, pp.249-260, 2013.
DOI : 10.1145/2463664.2463675

H. Läuchli and C. Savioz, Abstract, The Journal of Symbolic Logic, vol.45, issue.01, pp.219-226, 1987.
DOI : 10.1090/S0002-9939-1958-0093479-4

M. Müller, J. Niehren, and R. Treinen, The First-Order theory of ordering constraints over feature trees, pp.432-443, 1998.

J. Niehren and A. Podelski, Feature automata and recognizable sets of feature trees, TAPSOFT. LNCS, pp.356-375, 1993.
DOI : 10.1007/3-540-56610-4_76
URL : https://hal.archives-ouvertes.fr/inria-00536823

M. Rabin, Automata on Infinite Objects and Church's Problem, CBMS Regional Conference Series in Mathematics, 1972.
DOI : 10.1090/cbms/013

H. Seidl, T. Schwentick, and A. Muscholl, Numerical document queries, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems , PODS '03, pp.155-166, 2003.
DOI : 10.1145/773153.773169
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.109.4976

H. Seidl, T. Schwentick, and A. Muscholl, Counting in trees, Logic and Automata. Texts in Logic and Games, pp.575-612, 2008.
URL : https://hal.archives-ouvertes.fr/hal-00358327

G. Smolka, Feature-constraint logics for unification grammars, The Journal of Logic Programming, vol.12, issue.1-2, pp.51-87, 1992.
DOI : 10.1016/0743-1066(92)90039-6

G. Smolka and R. Treinen, Records for logic programming, The Journal of Logic Programming, vol.18, issue.3, pp.229-258, 1994.
DOI : 10.1016/0743-1066(94)90044-2

L. Stockmeyer and A. Meyer, Word problems requiring exponential time, Symposium on the Theory of Computing, pp.1-9, 1973.
DOI : 10.1145/800125.804029
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.116.4618

J. W. Thatcher and J. B. Wright, Generalized finite automata theory with an application to a decision problem of second-order logic, Mathematical Systems Theory, vol.12, issue.1, pp.57-81, 1968.
DOI : 10.1007/BF01691346

S. D. Zilio and D. Lugiez, XML schema, tree logic and sheaves automata, Proc. of RTA, pp.246-263, 2003.
DOI : 10.1007/s00200-006-0016-7
URL : https://hal.archives-ouvertes.fr/hal-00109288