Dominance constraints: algorithms and complexity

DOI10.1007/3-540-45738-0_7MaRDI QIDQ2762872zbMATH OpenFDO

Authors Alexander Koller, Joachim Niehren, Ralf Treinen

Publication date 13 January 2002

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2014/20140106

zbMATH Keywords

complexitycomputational linguisticsconstraint programmingDominance constraintsunderspecification

Mathematics Subject Classification ID

Logic of natural languages (03B65) Natural language processing (68T50)

Review text

Dominance constraints for finite tree structures are widely used in several areas of computational linguistics including syntax, semantics, and discourse. In this paper, we investigate algorithmic and complexity questions for dominance constraints and their first-order theory. The main result of this paper is that the satisfiability problem of dominance constraints is NP-complete. We present two NP algorithms for solving dominance constraints, which have been implemented in the concurrent constraint programming language Oz. Despite the intractability result, the more sophisticated of our algorithms performs well in an application to scope underspecification. We also show that the positive existential fragment of the first-order theory of dominance constraints is NP-complete and that the full first-order theory has non-elementary complexity. For the entire collection see [Zbl 0967.00057].

Recommendations

• An efficient graph algorithm for dominance constraints
• An efficient algorithm for the configuration problem of dominance graphs
• scientific article; zbMATH DE number 2086393
• A new algorithm for normal dominance constraints
• Dominance constraints with set operators

Cited in

(16)

• Algorithmic aspects of majority domination
• Dominance constraints with Boolean connectives: A model-eliminative treatment
• Dominance constraints in context unification
• Dominance constraints with set operators
• An efficient algorithm for the configuration problem of dominance graphs
• Efficient Computation of Dominance in Component Systems (Short Paper)
• The Complexity of Eliminating Dominated Strategies
• Reference-set constraints as linear tree transductions via controlled optimality systems
• An efficient graph algorithm for dominance constraints
• scientific article; zbMATH DE number 2086393 (Why is no real title available?)
• Automata for unordered trees
• scientific article; zbMATH DE number 975414 (Why is no real title available?)
• A new algorithm for normal dominance constraints
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
• The constraint language for lambda structures
• Dominance constraints in stratified context unification

This page was built for publication: Dominance constraints: algorithms and complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2762872)