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

H. Seidl, Haskell overloading is DEXPTIME-complete, Information Processing Letters, vol.52, issue.2, pp.57-60, 1994.
DOI : 10.1016/0020-0190(94)00130-8
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.119.8086

A. Neumann and H. Seidl, Locating Matches of Tree Patterns in Forests, International Conference on Foundations of Software Technology and Theoretical Computer Science (FCTTCS), pp.134-145, 1998.
DOI : 10.1007/978-3-540-49382-2_12

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

S. Maneth, A. Berlea, T. Perst, and H. Seidl, XML type checking with macro tree transducers, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems , PODS '05, pp.283-294, 2005.
DOI : 10.1145/1065167.1065203
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.112.549

T. Schwentick, Automata for XML???A survey, Journal of Computer and System Sciences, vol.73, issue.3, pp.289-315, 2007.
DOI : 10.1016/j.jcss.2006.10.003

T. Milo, D. Suciu, and V. Vianu, Type checking XML transformers, Journal of Computer and System Science, vol.1, issue.66, pp.66-97, 2003.

J. Champavère, R. Gilleron, A. Lemay, and J. Niehren, Schema-Guided Induction of Monadic Queries, International Colloquium on Grammatical Inference (ICGI), pp.15-28, 2008.
DOI : 10.1007/978-3-540-88009-7_2

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

G. J. Bex, F. Neven, and J. V. Bussche, DTDs versus XML schema, Proceedings of the 7th International Workshop on the Web and Databases colocated with ACM SIGMOD/PODS 2004, WebDB '04, pp.79-84, 2004.
DOI : 10.1145/1017074.1017095

A. Brüggemann-klein and D. Wood, One-Unambiguous Regular Languages, Information and Computation, vol.142, issue.2, pp.182-206, 1998.
DOI : 10.1006/inco.1997.2695

W. Martens and J. Niehren, On the minimization of XML Schemas and tree automata for unranked trees, Journal of Computer and System Sciences, vol.73, issue.4, pp.550-583, 2007.
DOI : 10.1016/j.jcss.2006.10.021
URL : https://hal.archives-ouvertes.fr/inria-00088406

S. Raeymaekers, Information extraction from web pages based on tree automata induction, 2008.

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. Brüggemann-klein, D. Wood, and M. Murata, Regular tree and regular hedge languages over unranked alphabets: Version 1, 2001.

W. Martens, F. Neven, and T. Schwentick, Which XML Schemas Admit 1-Pass Preorder Typing?, International Conference on Database Theory, pp.68-82, 2005.
DOI : 10.1007/978-3-540-30570-5_5

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, pp.770-813, 2006.
DOI : 10.1145/1166074.1166076

J. Champavère, R. Gilleron, A. Lemay, and J. Niehren, Efficient Inclusion Checking for Deterministic Tree Automata and DTDs, International Conference on Language and Automata Theory and Applications (LATA), pp.184-195, 2008.
DOI : 10.1007/978-3-540-88282-4_18

W. Martens, F. Neven, and T. Schwentick, Complexity of Decision Problems for Simple Regular Expressions, International Symposium on Mathematical Foundations of Computer Science (MFCS), pp.889-900, 2004.
DOI : 10.1007/978-3-540-28629-5_70

A. Tozawa and M. Hagiya, XML Schema Containment Checking Based on Semi-implicit Techniques, International Conference on Implementation and Application of Automata (CIAA), pp.51-61, 2003.
DOI : 10.1007/3-540-45089-0_20
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.14.7483

S. Ceri, G. Gottlob, and L. Tanca, What you always wanted to know about Datalog (and never dared to ask), IEEE Transactions on Knowledge and Data Engineering, vol.1, issue.1, pp.146-166, 1989.
DOI : 10.1109/69.43410
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.210.1118

E. Dantsin, T. Eiter, G. Gottlob, and A. Voronkov, Complexity and expressive power of logic programming, ACM Computing Surveys, vol.33, issue.3, pp.374-425, 2001.
DOI : 10.1145/502807.502810

G. Gottlob, E. Grädel, and H. Veith, Datalog LITE: a deductive query language with linear time model checking, ACM Transactions on Computational Logic, vol.3, issue.1, pp.42-79, 2002.
DOI : 10.1145/504077.504079

M. Minoux, LTUR: a simplified linear-time unit resolution algorithm for horn formulae and computer implementation, Information Processing Letters, vol.29, issue.1, pp.1-12, 1988.
DOI : 10.1016/0020-0190(88)90124-X

A. Brüggemann-klein, Regular expressions into finite automata, Theoretical Computer Science, vol.120, issue.2, pp.197-213, 1993.
DOI : 10.1016/0304-3975(93)90287-4

G. Gottlob and C. Koch, Monadic queries over tree-structured data, Proceedings 17th Annual IEEE Symposium on Logic in Computer Science, pp.189-202, 2002.
DOI : 10.1109/LICS.2002.1029828
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.989

J. Viràgh, Deterministic ascending tree automata I, Acta Cybernetica, vol.5, issue.1, pp.33-42, 1980.

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

O. Gauwin, J. Niehren, and Y. Roos, Streaming tree automata, Information Processing Letters, vol.109, issue.1, pp.13-17, 2008.
DOI : 10.1016/j.ipl.2008.08.002
URL : https://hal.archives-ouvertes.fr/inria-00288445

R. Alur, Marrying words and trees, Symposium on Principles of Database Systems (PODS), pp.233-242, 2007.