M. Bodirsky, D. Duchier, S. Miele, and J. Niehren, A new algorithm for normal dominance constraints, ACM-SIAM Symposium on Discrete Algorithms, pp.54-78, 2004.
URL : https://hal.archives-ouvertes.fr/inria-00536536

H. Comon, Completion of rewrite systems with membership constraints, International Colloquium on Automata, Languages and Programming, pp.392-403, 1992.
DOI : 10.1007/3-540-55719-9_91

D. Duchier and C. Gardent, Tree Descriptions, Constraints and Incrementality, Computing Meaning 2, pp.205-227, 2001.
DOI : 10.1007/978-94-010-0572-2_12
URL : https://hal.archives-ouvertes.fr/inria-00100450

M. Egg, A. Koller, and J. Niehren, The constraint language for lambda structures, Journal of Logic, Language and Information, vol.10, issue.4, pp.457-485, 2001.
DOI : 10.1023/A:1017964622902
URL : https://hal.archives-ouvertes.fr/inria-00536795

E. Filiot, J. Niehren, J. Talbot, and S. Tison, On XPath dialects with variables, 2006.

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

G. Gottlob, C. Koch, and K. U. Schulz, Conjunctive queries over trees, 23rd ACM Symposium on Principles of Database Systems, pp.189-200, 2004.

A. Koller, J. Niehren, and R. Treinen, Dominance Constraints: Algorithms and Complexity, 3rd 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

J. Levy, Linear second-order unification, 7th Int. Conference on Rewriting Techniques and Applications, pp.332-346, 1996.
DOI : 10.1007/3-540-61464-8_63
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.418.1987

L. Libkin, Logics over unranked trees: an overview, Logical Methods in Computer Science, vol.3, issue.2, pp.1-31, 2006.

J. Levy, J. Niehren, and M. Villaret, Well-Nested Context Unification, 20th Intern. Conference on Automated Deduction, pp.149-163, 2005.
DOI : 10.1007/11532231_11
URL : https://hal.archives-ouvertes.fr/inria-00536525

J. Levy, M. Schmidt-schauss, and M. Villaret, Stratified context unification is NPcomplete, 3rd International Joint Conference on Automated Reasoning, pp.82-96, 2006.
DOI : 10.1007/11814771_8
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.158.865

G. Makanin, The problem of solvability of equations in a free semigroup. Soviet Akad, Nauk SSSR, vol.223, issue.2, 1977.

M. P. Marcus, D. Hindle, and M. M. Fleck, D-theory, Proceedings of the 21st annual meeting on Association for Computational Linguistics -, pp.129-136, 1983.
DOI : 10.3115/981311.981337

M. Marx, Conditional XPath, ACM Transactions on Database Systems, vol.30, issue.4, pp.929-959, 2005.
DOI : 10.1145/1114244.1114247

J. Niehren and A. Koller, Dominance Constraints in Context Unification, 3rd International Conferernce on Logical Aspects of Computational Linguistics, pp.199-218, 1998.
DOI : 10.1007/3-540-45738-0_12
URL : https://hal.archives-ouvertes.fr/inria-00536820

J. Niehren, R. Treinen, and S. Tison, On rewrite constraints and context unification, Information Processing Letters, vol.74, issue.1-2, pp.35-40, 2000.
DOI : 10.1016/S0020-0190(00)00036-3
URL : https://hal.archives-ouvertes.fr/inria-00536802

J. Rogers and K. Vijay-shanker, OBTAINING TREES FROM THEIR DESCRIPTIONS: AN APPLICATION TO TREE-ADJOINING GRAMMARS, Computational Intelligence, vol.18, issue.4, pp.401-421, 1994.
DOI : 10.1111/j.1467-8640.1994.tb00005.x

M. Schmidt-schauss, A Decision Algorithm for Stratified Context Unification, Journal of Logic and Computation, vol.12, issue.6, pp.929-953, 2002.
DOI : 10.1093/logcom/12.6.929

M. Schmidt-schauss and K. U. Schulz, Solvability of Context Equations with Two Context Variables is Decidable, Journal of Symbolic Computation, vol.33, issue.1, pp.77-122, 2002.
DOI : 10.1006/jsco.2001.0438

M. Schmidt-schauß and K. U. Schulz, On the exponent of periodicity of minimal solutions of context equations, 9th RTA, pp.61-75, 1998.
DOI : 10.1007/BFb0052361

J. W. Thatcher and J. B. Wright, Generalized finite automata theory with an application to a decision problem of second-order logic, Mathematical System Theory, pp.57-82, 1968.
DOI : 10.1007/BF01691346