A. Boiret, V. Hugot, J. Niehren, and R. Treinen, Deterministic automata for unordered trees Automata, Logics and Formal Verification, Proceedings of the Fifth International Symposium on Games, 2014.

N. Nurseitov, M. Paulson, R. Reynolds, and C. Izurieta, Comparison of JSON and XML data interchange formats: A case study, pp.157-162, 2009.

K. S. Beyer, V. Ercegovac, R. Gemulla, A. Balmin, M. Y. Eltabakh et al., Jaql: A scripting language for large scale semistructured data analysis, PVLDB, vol.4, issue.12, pp.1272-1283, 2011.

H. Seidl, T. Schwentick, and A. , 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

I. Boneva and J. Talbot, Automata and Logics for Unranked and Unordered Trees, Lecture Notes in Computer Science, vol.3467, pp.500-515, 2005.
DOI : 10.1007/978-3-540-32033-3_36
URL : https://hal.archives-ouvertes.fr/inria-00536694

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

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

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

M. Müller, J. Niehren, and R. Treinen, The first-order theory of ordering constraints over feature trees, 13th annual IEEE Symposium on Logic in Computer Science, pp.432-443, 1998.

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

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

J. Carme, J. Niehren, and M. Tommasi, Querying Unranked Trees with Stepwise Tree Automata, 19th International Conference on Rewriting Techniques and Applications, pp.105-118, 2004.
DOI : 10.1007/978-3-540-25979-4_8
URL : https://hal.archives-ouvertes.fr/inria-00536529

J. E. Hopcroft, R. Motwani, and J. D. Ullman, Automata theory, languages, and computation

R. Parikh, On Context-Free Languages, Journal of the ACM, vol.13, issue.4, pp.570-581, 1966.
DOI : 10.1145/321356.321364

S. Ginsburg and E. H. , Semigroups, Presburger formulas, and languages, Pacific Journal of Mathematics, vol.16, issue.2, pp.285-296, 1966.
DOI : 10.2140/pjm.1966.16.285

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-82, 1968.
DOI : 10.1007/BF01691346

G. Gottlob and C. Koch, Monadic queries over tree-structured data, Proceedings 17th Annual IEEE Symposium on Logic in Computer Science, p.17, 2002.
DOI : 10.1109/LICS.2002.1029828

G. Gottlob and C. Koch, Monadic datalog and the expressive power of languages for Web information extraction, Journal of the ACM, vol.51, issue.1, pp.74-113, 2004.
DOI : 10.1145/962446.962450

H. Hosoya, Foundations of XML processing: the tree-automata approach, 2010.
DOI : 10.1017/CBO9780511762093

A. Koller, J. Niehren, R. Treinen, and D. Constraints, Dominance Constraints: Algorithms and Complexity, Third International Conference on Logical Aspects of Computational Linguistics, pp.106-125, 1998.
DOI : 10.1007/3-540-45738-0_7
URL : https://hal.archives-ouvertes.fr/inria-00536812

L. J. Stockmeyer, A. R. Meyer, A. V. Aho, A. Borodin, R. L. Constable et al., Word problems requiring exponential time(Preliminary Report), Proceedings of the fifth annual ACM symposium on Theory of computing , STOC '73, pp.1-9, 1973.
DOI : 10.1145/800125.804029

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

A. Bruggemann-klein, M. Murata, and D. Wood, Regular tree and regular hedge languages over unranked alphabets, Tech. rep., HKUST Theoretical Computer Science Center Research Report, 2001.

W. Martens and F. Neven, Typechecking Top-Down Uniform Unranked Tree Transducers, ICDT, pp.64-78, 2003.
DOI : 10.1007/3-540-36285-1_5

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

W. Martens and J. Niehren, Minimizing Tree Automata for Unranked Trees, DBPL, pp.232-246, 2005.
DOI : 10.1007/11601524_15
URL : https://hal.archives-ouvertes.fr/inria-00536521

D. Lugiez, Multitree automata that count, Theoretical Computer Science, vol.333, issue.1-2, pp.225-263, 2005.
DOI : 10.1016/j.tcs.2004.10.023

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

S. Maneth and K. Nguyen, XPath whole query optimization, Proceedings of the VLDB Endowment, vol.3, issue.1-2, pp.882-893, 2010.
DOI : 10.14778/1920841.1920954

A. Boiret, V. Hugot, J. Niehren, and R. Treinen, Logics for Unordered Trees with Data Constraints on Siblings, Language and Automata Theory and Applications -9th International Conference, LATA 2015 Proceedings, pp.175-187, 2015.
DOI : 10.1007/978-3-319-15579-1_13
URL : https://hal.archives-ouvertes.fr/hal-01088761

H. Seidl, T. Schwentick, A. Muscholl, and P. Habermehl, Counting in Trees for Free, International Colloquium on Automata, Languages and Programming (ICALP), pp.1136-1149, 2004.
DOI : 10.1007/978-3-540-27836-8_94
URL : https://hal.archives-ouvertes.fr/hal-00159525

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

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

E. Kopczynski, Complexity of Problems of Commutative Grammars, Logical Methods in Computer Science, vol.11, issue.1
DOI : 10.2168/LMCS-11(1:9)2015

C. Haase and S. Halfon, Integer Vector Addition Systems with States, Proceedings Lecture Notes in Computer Science, vol.8762, pp.112-124, 2014.
DOI : 10.1007/978-3-319-11439-2_9

P. Gawrychowski, Chrobak Normal Form Revisited, with Applications, pp.142-153, 2011.
DOI : 10.1016/j.ipl.2009.06.005