A. Culotta and J. Sorensen, Dependency tree kernels for relation extraction, Proceedings of the 42nd Annual Meeting on Association for Computational Linguistics , ACL '04, pp.423-429, 2004.
DOI : 10.3115/1218955.1219009
URL : http://acl.ldc.upenn.edu/acl2004/main/pdf/244_pdf_2-col.pdf

C. Quirk, A. Menezes, and C. Cherry, Dependency treelet translation, Proceedings of the 43rd Annual Meeting on Association for Computational Linguistics , ACL '05, pp.271-279, 2005.
DOI : 10.3115/1219840.1219874

J. Nivre, J. Hall, S. Kübler, R. Mcdonald, J. Nilsson et al., The CoNLL 2007 shared task on dependency parsing, Joint Conference on Empirical Methods in NLP and Computational Natural Language Learning, pp.915-932, 2007.

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

B. Courcelle, Handbook of graph grammars and computing by graph transformations, Foundations. Handbook of Graph Grammars, vol.1, 1997.

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

B. Courcelle, Graph Grammars and Logic, Book in preparation, 2008.

M. Rabin, Decidability of Second-Order Theories and Automata on Infinite Trees, Transactions of the American Mathematical Society, vol.141, pp.1-35, 1969.

G. Gottlob and C. Koch, Monadic datalog and the expressive power of languages for web information extraction, pp.21-38, 2002.

M. Plátek, T. Holan, and V. Kubo?, On relaxability of word order by D-Grammars, 3rd Int. Conf. on Combinatorics, Computability and Logic, pp.159-174, 2001.

M. Kuhlmann, Dependency Structures and Lexicalized Grammars Doctoral dissertation, 2007.
DOI : 10.1007/978-3-642-14568-1

A. Koller and K. Striegnitz, Generation as dependency parsing, Proceedings of the 40th Annual Meeting on Association for Computational Linguistics , ACL '02, pp.17-24, 2002.
DOI : 10.3115/1073083.1073088
URL : http://acl.ldc.upenn.edu/P/P02/P02-1003.pdf

T. Holan, V. Kubo?, K. Oliva, and M. Plátek, Two useful measures of word order complexity, Work. on Processing of Dependency-Based Grammars, pp.21-29, 1998.

M. Kuhlmann and J. Nivre, Mildly non-projective dependency structures, Proceedings of the COLING/ACL on Main conference poster sessions -, pp.507-514, 2006.
DOI : 10.3115/1273073.1273139
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.107.6635

J. Mezei and J. B. Wright, Algebraic automata and context-free sets, Information and Control, vol.11, issue.1-2, pp.3-29, 1967.
DOI : 10.1016/S0019-9958(67)90353-1
URL : http://doi.org/10.1016/s0019-9958(67)90353-1

B. Courcelle, Recognizable sets of unrooted trees, Tree Automata and Languages, 1992.

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