]. D. Angluin, Learning regular sets from queries and counterexamples. Information and Computation, pp.87-106, 1987.
DOI : 10.1016/0890-5401(87)90052-6
URL : http://doi.org/10.1016/0890-5401(87)90052-6

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.
DOI : 10.1109/lics.2003.1210058
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.127.5196

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.
DOI : 10.1145/568438.568455

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
URL : http://doi.org/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.

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.

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.
DOI : 10.1142/9789812797902_0004

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