]. D. Angluin, Learning regular sets from queries and counterexamples. Information and Computation, pp.87-106, 1987.

A. Balmin, Y. Papakonstantinou, and V. Vianu, Incremental validation of XML documents, ACM Transactions on Database Systems, vol.29, issue.4, pp.710-751, 2004.
DOI : 10.1145/1042046.1042050

A. Brüggemann-klein, M. Murata, and D. Wood, Regular tree and regular hedge languages over unranked alphabets: Version 1, april 3, 2001.

J. Carme, A. Lemay, and J. Niehren, Learning Node Selecting Tree Transducer from Completely Annotated Examples, International Colloquium on Grammatical Inference, pp.91-102, 2004.
DOI : 10.1007/978-3-540-30195-0_9
URL : https://hal.archives-ouvertes.fr/inria-00536528

J. Carme, J. Niehren, and M. Tommasi, Querying Unranked Trees with Stepwise Tree Automata, 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

S. A. Cook, An observation on time-storage trade off, Journal of Computer and System Sciences, vol.9, issue.3, pp.308-316, 1974.
DOI : 10.1016/S0022-0000(74)80046-2

B. Courcelle, On Recognizable Sets and Tree Automata, Resolution of equations in algebraic structures, pp.93-126, 1989.
DOI : 10.1016/B978-0-12-046370-1.50009-7

J. Cristau, C. Löding, and W. Thomas, Deterministic Automata on Unranked Trees, Proceedings 15th International Symposium on Fundamentals of Computation Theory (FCT 2005), pp.68-72, 2005.
DOI : 10.1007/11537311_7

M. Frick, M. Grohe, and C. Koch, Query evaluation on compressed trees (extended abstract), 18th IEEE Symposium on Logic in Computer Science (LICS 2003), pp.188-197, 2003.

E. M. Gold, Complexity of automaton identification from given data, Information and Control, vol.37, issue.3, pp.302-320, 1978.
DOI : 10.1016/S0019-9958(78)90562-4

G. Gottlob, C. Koch, R. Pichler, and L. Segoufin, The complexity of XPath query evaluation and XML typing, Journal of the ACM, vol.52, issue.2, pp.284-335, 2005.
DOI : 10.1145/1059513.1059520

J. E. Hopcroft, R. Motwani, and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, 2001.

T. Jiang and B. Ravikumar, Minimal NFA Problems are Hard, SIAM Journal on Computing, vol.22, issue.6, pp.1117-1141, 1993.
DOI : 10.1137/0222067

D. Kozen, On the Myhill-Nerode theorem for trees. Bulletin of the European Association for Theoretical Computer Science, pp.170-173, 1992.

A. Malcher, Minimizing finite automata is computationally hard, Theoretical Computer Science, vol.327, issue.3, pp.375-390, 2004.
DOI : 10.1016/j.tcs.2004.03.070

W. Martens and F. Neven, On the complexity of typechecking top-down XML transformations, Theoretical Computer Science, vol.336, issue.1, pp.153-180, 2005.
DOI : 10.1016/j.tcs.2004.10.035

W. Martens, F. Neven, T. Schwentick, and G. J. Bex, Expressiveness and complexity of XML Schema, ACM Transactions on Database Systems, vol.31, issue.3, p.31, 2006.
DOI : 10.1145/1166074.1166076

W. Martens and J. Niehren, Minimizing tree automata for unranked trees [extended abstract], Proceedings of the Tenth International Symposium on Database Programming Languages (DBPL 2005), pp.233-247, 2005.
DOI : 10.1007/11601524_15
URL : https://hal.inria.fr/inria-00536521/file/mini.pdf

M. Murata, D. Lee, M. Mani, and K. Kawaguchi, Taxonomy of XML schema languages using formal language theory, ACM Transactions on Internet Technology, vol.5, issue.4, pp.1-45, 2005.
DOI : 10.1145/1111627.1111631

F. Neven, Automata theory for XML researchers, ACM SIGMOD Record, vol.31, issue.3, 2002.
DOI : 10.1145/601858.601869
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.12.907

F. Neven and T. Schwentick, Expressive and efficient pattern languages for tree-structured data, Proceedings of the 19th Symposium on Principles of Database Systems, pp.145-156, 2000.
DOI : 10.1145/335168.335217
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.125.2988

F. Neven and T. 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
URL : http://doi.org/10.1016/s0304-3975(01)00301-2

J. Oncina and P. Garcia, Inferring regular languages in polynomial update time, Pattern Recognition and Image Analysis, pp.49-61, 1992.

Y. Papakonstantinou and V. Vianu, DTD inference for views of XML data, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems , PODS '00, pp.35-46, 2000.
DOI : 10.1145/335168.335173

G. Pighizzini and J. Shallit, UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION, International Journal of Foundations of Computer Science, vol.13, issue.01, pp.145-159, 2002.
DOI : 10.1142/S012905410200100X

S. Raeymaekers and M. Bruynooghe, Minimization of finite unranked tree automata, 2004.

T. Schwentick, XPath query containment, ACM SIGMOD Record, vol.33, issue.1, pp.101-109, 2004.
DOI : 10.1145/974121.974140
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.364.7281

H. Seidl, Deciding Equivalence of Finite Tree Automata, SIAM Journal on Computing, vol.19, issue.3, pp.424-437, 1990.
DOI : 10.1137/0219027

R. E. Stearns, H. B. Hunt, and I. , On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata, SIAM Journal on Computing, vol.14, issue.3, pp.598-611, 1985.
DOI : 10.1137/0214044

L. J. Stockmeyer and A. R. Meyer, 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

D. Suciu, Typechecking for Semistructured Data, Proceedings of the 8th Workshop on Data Bases and Programming Languages, pp.1-20, 2001.
DOI : 10.1007/3-540-46093-4_1

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

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