A. Boiret, V. Hugot, J. Niehren, and R. Treinen, Language and Automata Theory and Applications9th International Conference, vol.8977, pp.175-187, 2015.

B. Courcelle and J. Engelfriet, Graph Structure and Monadic Second-Order Logic-A Language-Theoretic Approach, vol.138, 2012.
URL : https://hal.archives-ouvertes.fr/hal-00646514

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

H. Seidl, T. Schwentick, and A. Muscholl, Numerical document queries, Proceedings of the Symposium on Principles Of Database Systems, pp.155-166, 2003.

I. Boneva and J. Talbot, Automata and logics for unranked and unordered trees, LNCS, vol.3467, pp.500-515, 2005.
URL : https://hal.archives-ouvertes.fr/inria-00536694

S. D. Zilio and D. Lugiez, tree logic and sheaves automata, Proc. of RTA, vol.2706, pp.246-263, 2003.
URL : https://hal.archives-ouvertes.fr/inria-00071954

G. Smolka, Feature constraint logics for unification grammars, Journal of Logic Programming, vol.12, pp.90039-90045, 1992.

G. Smolka and R. Treinen, Records for logic programming, J. Log. Program, vol.18, issue.3, pp.229-258, 1994.

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, LNCS, vol.668, pp.356-375, 1993.
URL : https://hal.archives-ouvertes.fr/inria-00536823

R. Backofen and G. Smolka, A complete and recursive feature theory, Theor. Comput. Sci, vol.146, issue.1-2, pp.243-268, 1995.

P. Blackburn, Structures, languages and translations: the structural approach to feature logic, pp.1-27, 1994.

P. Weil, Algebraic recognizability of languages, Mathematical Foundations of Computer Science, pp.149-175, 2004.
URL : https://hal.archives-ouvertes.fr/hal-00096619

B. Bollig, A. Cyriac, P. Gastin, and K. N. Kumar, Model checking languages of data words, Foundations of Software Science and Computational Structures, pp.391-405, 2012.
URL : https://hal.archives-ouvertes.fr/hal-00658333

H. Lauchli and C. Savioz, Monadic second order definable relations on the binary tree, J. Symb. Log, vol.52, issue.1, pp.219-226, 1987.

M. Bojanczyk, C. David, A. Muscholl, T. Schwentick, and L. Segoufin, Twovariable logic on data words, ACM Trans. Comput. Log, vol.12, issue.4, p.27, 2011.
URL : https://hal.archives-ouvertes.fr/hal-00151749

A. Boiret, V. Hugot, J. Niehren, and R. Treinen, Automata for unordered trees, Inf. Comput, vol.253, pp.304-335, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01179493

B. Courcelle, The monadic second-order logic of graphs. i. recognizable sets of finite graphs, Information and computation, vol.85, issue.1, 1990.
URL : https://hal.archives-ouvertes.fr/hal-00353765

D. Figueira, On XPath with transitive axes and data tests, PODS, ACM, pp.249-260, 2013.
URL : https://hal.archives-ouvertes.fr/hal-01795148

J. R. Büchi, Weak second-order arithmetic and finite automata, Mathematical Logic Quarterly, vol.6, issue.1-6, pp.66-92, 1960.

J. W. Thatcher and J. B. Wright, Generalized finite automata theory with an application to a decision problem of second-order logic, MST, vol.2, issue.1, pp.57-81, 1968.

L. Stockmeyer and A. Meyer, Word problems requiring exponential time, Symposium on the Theory of Computing, pp.1-9, 1973.

M. Müller and J. Niehren, Ordering constraints over feature trees expressed in second-order monadic logic, Inf. Comput, vol.159, issue.1-2, pp.22-58, 2000.

H. Comon, M. Dauchet, R. Gilleron, C. Löding, F. Jacquemard et al., Tree automata techniques and applications, 2007.

M. Rabin, Automata on Infinite Objects and Church's Problem, 1972.

H. Läuchli and C. Savioz, Monadic second order definable relations on the binary tree, Journal of Symbol Logic, vol.52, issue.1, pp.219-226, 1987.

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

B. Bogaert and S. Tison, Equality and disequality constraints on direct subterms in tree automata, Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science, STACS '92, pp.161-171, 1992.

S. Abiteboul, P. Bourhis, A. Muscholl, and Z. Wu, Recursive queries on trees and data trees, pp.93-104, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00809297