E. Althaus, D. Duchier, A. Koller, K. Mehlhorn, J. Niehren et al., An efficient algorithm for the configuration problem of dominance graphs, Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms, pp.815-824, 2001.
URL : https://hal.archives-ouvertes.fr/inria-00536803

A. Koller, K. Mehlhorn, and J. Niehren, A polynomial-time fragment of dominance constraints, Proceedings of the 38th Annual Meeting on Association for Computational Linguistics , ACL '00, pp.368-375, 2000.
DOI : 10.3115/1075218.1075265
URL : https://hal.archives-ouvertes.fr/inria-00536809

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, 1967.
DOI : 10.1007/BF01691346

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

R. Backofen, J. Rogers, and K. Vijay-shanker, A first-order axiomatization of the theory of finite trees, Journal of Logic, Language and Information, vol.18, issue.4, pp.5-39, 1995.
DOI : 10.1007/BF01048403

K. Vijay-shanker, Using descriptions of trees in a tree adjoining grammar, Computational Linguistics, vol.18, pp.481-518, 1992.

D. Duchier and S. Thater, Parsing with tree descriptions: a constraintbased approach, Sixth International Workshop on Natural Language Understanding and Logic Programming, pp.17-32, 1999.

G. Perrier, From intuitionistic proof nets to interaction grammars, Proceedings of the 5th TAG+ Workshop, 2000.
URL : https://hal.archives-ouvertes.fr/inria-00098793

R. Muskens, Order-independence and underspecification, Ellipsis, Underspecification, Events and More in Dynamic Semantics, DYANA Deliverable R.2.2.C, 1995.

M. Egg, J. Niehren, P. Ruhrberg, and F. Xu, Constraints over lambda-structures in semantic underspecification, Proceedings of the Joint 17th International Conference on Computational Linguistics and 36th Annual Meeting of the Association of Computational Linguistics, pp.353-359, 1998.
URL : https://hal.archives-ouvertes.fr/inria-00536807

C. Gardent and B. Webber, Describing discourse semantics, Proceedings of the 4th TAG+ Workshop, 1998.

A. Koller, J. Niehren, and R. Treinen, Dominance Constraints: Algorithms and Complexity, Proceedings of the Third 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

T. Cornell, On determining the consistency of partial descriptions of trees, Proceedings of the 32nd annual meeting on Association for Computational Linguistics -, pp.163-170, 1994.
DOI : 10.3115/981732.981755

D. Duchier and J. Niehren, Dominance Constraints with Set Operators, Proceedings of the First International Conference on Computational Logic, no. 1861 in Lecture Notes in Computer Science, pp.326-341, 2000.
DOI : 10.1007/3-540-44957-4_22
URL : https://hal.archives-ouvertes.fr/inria-00536806

K. Mehlhorn and S. Näher, LEDA: A platform for combinatorial and geometric computing, 1999.

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

K. Erk, A. Koller, and J. Niehren, Processing underspecified semantic representations in the constraint language for lambda structures, Research on Language and Computation, vol.1, issue.1
URL : https://hal.archives-ouvertes.fr/inria-00536796

J. Bos, Predicate logic unplugged, Proceedings of the 10th Amsterdam Colloquium, pp.133-143, 1996.

A. Copestake, D. Flickinger, and I. Sag, Minimal Recursion Semantics. An Introduction, manuscript, 1997.
DOI : 10.1007/s11168-006-6327-9

H. Alshawi and R. Crouch, Monotonic semantic interpretation, Proceedings of the 30th annual meeting on Association for Computational Linguistics -, pp.32-39, 1992.
DOI : 10.3115/981967.981972

U. Reyle, Dealing with Ambiguities by Underspecification: Construction, Representation and Deduction, Journal of Semantics, vol.10, issue.2, pp.123-179, 1993.
DOI : 10.1093/jos/10.2.123

J. Hobbs, An improper treatment of quantification in ordinary English, Proceedings of the 21st annual meeting on Association for Computational Linguistics -, pp.57-63, 1983.
DOI : 10.3115/981311.981322

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

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

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

H. Gabow, H. Kaplan, and R. Tarjan, Unique maximum matching algorithms, Proceedings of the thirty-first annual ACM symposium on Theory of computing , STOC '99, pp.159-183, 2001.
DOI : 10.1145/301250.301273

A. Goralcikova and V. Koubek, A reduct-and-closure algorithm for graphs, Proceedings of the 8th Symposium on Mathematical Foundations of Computer Science, pp.301-307, 1979.

K. Simon, An improved algorithm for transitive closure on acyclic digraphs, Theoretical Computer Science, vol.58, pp.1-3, 1988.

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

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

A. Willis and S. Manandhar, Two accounts of scope availability and semantic underspecification, Proceedings of the 37th annual meeting of the Association for Computational Linguistics on Computational Linguistics -, pp.293-300, 1999.
DOI : 10.3115/1034678.1034727