H. Aït-kaci and A. Podelski, Towards a meaning of life, The Journal of Logic Programming, vol.16, issue.3-4, pp.195-234, 1993.
DOI : 10.1016/0743-1066(93)90043-G

H. Aït-kaci, A. Podelski, and G. Smolka, A feature constraint system for logic programming with entailment, Theoretical Computer Science, vol.122, issue.1-2, pp.263-283, 1994.
DOI : 10.1016/0304-3975(94)90209-7

R. Backofen, A complete axiomatization of a theory with feature and arity constraints, The Journal of Logic Programming, vol.24, issue.1-2, pp.37-71, 1995.
DOI : 10.1016/0743-1066(95)00033-G

R. Backofen and G. Smolka, A complete and recursive feature theory, Theoretical Computer Science, vol.146, issue.1-2, pp.243-268, 1995.
DOI : 10.1016/0304-3975(94)00188-O

F. Bourdoncle and S. Merz, Type checking higher-order polymorphic multi-methods, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages , POPL '97, pp.302-315, 1997.
DOI : 10.1145/263699.263743

B. Carpenter, The Logic of Typed Feature Structures -with Applications to Unification Grammars, Logic Programs and Constraint Resolution. Number 32 in Cambridge Tracts in Theoretical Computer Science, 1992.

J. Dörre, Feature logics with weak subsumption constraints, Annual Meeting of the Association of Computational Linguistics, pp.256-263, 1991.

J. Dörre and W. C. Rounds, On subsumption and semiunification in feature algebras, 5 th IEEE Symposium on Logic in Computer Science, pp.300-310, 1990.

M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, 1979.

F. Henglein and J. Rehof, The complexity of subtype entailment for simple types, Proceedings of Twelfth Annual IEEE Symposium on Logic in Computer Science, 1997.
DOI : 10.1109/LICS.1997.614961

F. Henglein and J. Rehof, Constraint automata and the complexity of recursive subtype entailment, 25 th International Conference on Automata, Languages, and Programming, 1998.
DOI : 10.1007/BFb0055089

R. M. Kaplan and J. Bresnan, Lexical-functional grammar: A formal system for grammatical representation The Mental Representation of Grammatical Relations, pp.173-281, 1982.

R. T. Kasper and W. C. Rounds, A logical semantics for feature structures, Proceedings of the 24th annual meeting on Association for Computational Linguistics -, pp.257-265, 1986.
DOI : 10.3115/981131.981166

M. Kay, Functional Grammar, Proceedings of the 5 th Annual Meeting of the Berkeley Linguistics Society, pp.142-158, 1979.
DOI : 10.3765/bls.v5i0.3262

M. J. Maher, Logic semantics for a class of committed-choice programs, International Conference on Logic Programming, pp.858-876, 1987.

S. Marlow and P. Wadler, A practical subtyping system for Erlang, Proceedings2 nd ACM SIGPLAN International Conference on Functional Programming, pp.136-149, 1997.

M. Müller and J. Niehren, Ordering constraints over feature trees expressed in secondorder monadic logic. Information and Computation, 2000.

M. Müller, J. Niehren, and A. Podelski, Ordering constraints over feature trees, Constraints , an International Journal, vol.5, issue.12, pp.7-42, 2000.
DOI : 10.1007/BFb0017447

M. Müller, Ordering constraints over feature trees with ordered sorts, 1997.

M. Müller, Set-based Failure Diagnosis for Concurrent Constraint Programming, 1998.

M. Müller, J. Niehren, and R. Treinen, The first-order theory of ordering constraints over feature trees, 13 th Annual IEEE Symposium on Logic in Computer Science, pp.432-443, 1998.

J. Palsberg, Efficient inference of object types, th IEEE Symposium on Logic in Computer Science, pp.186-185, 1994.

C. Pollard and I. Sag, Head-Driven Phrase Structure Grammar. Studies in Contemporary Linguistics, 1994.

F. Pottier, Simplifying subtyping constraints, ACM SIGPLAN International Conference on Functional Programming, pp.122-133, 1996.
DOI : 10.1145/232627.232642
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.7032

M. O. Rabin, Decidability of second-order theories and automata on infinite trees. Transactions of the, pp.1-35, 1969.

W. C. Rounds, Feature Logics, Handbook of Logic and Language, 1997.
DOI : 10.1016/B978-044481714-3/50012-6

V. A. Saraswat, Concurrent constraint programming, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages , POPL '90, 1993.
DOI : 10.1145/96709.96733

S. Shieber, An Introduction to Unification-based Approaches to Grammar. CSLI Lecture Notes No. 4. Center for the Study of Language and Information, 1986.

G. Smolka, Feature-constraint logics for unification grammars, The Journal of Logic Programming, vol.12, issue.1-2, pp.51-87, 1992.
DOI : 10.1016/0743-1066(92)90039-6
URL : http://doi.org/10.1016/0743-1066(92)90039-6

G. Smolka, The Oz Programming Model, Computer Science Today, Lecture Notes in Computer Science, vol.1000, pp.324-343, 1995.
DOI : 10.1007/BFb0015252

G. Smolka and R. Treinen, Records for logic programming, The Journal of Logic Programming, vol.18, issue.3, pp.229-258, 1994.
DOI : 10.1016/0743-1066(94)90044-2

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

R. Treinen, A new method for undecidability proofs of first order theories, Journal of Symbolic Computation, vol.14, issue.5, pp.437-457, 1992.
DOI : 10.1016/0747-7171(92)90016-W

R. Treinen, Feature trees over arbitrary structures, Specifying Syntactic Structures, pp.185-211, 1997.

V. Trifonov and S. Smith, Subtyping constrained types, Proceedings3 rd International Static Analysis Symposium, pp.349-365, 1996.
DOI : 10.1007/3-540-61739-6_52

P. Van-roy, M. Mehl, and R. Scheidhauer, Integrating efficient records into concurrent constraint programming, International Symposium on Programming Language Implementation and Logic Programming, 1996.

S. Vorobyov, An improved lower bound for the elementary theories of trees, Procedings of the International Conference on Automated Deduction, pp.275-287, 1996.
DOI : 10.1007/3-540-61511-3_91