Dominance constraints: algorithms and complexity (Q2762872)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1689581
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Dominance constraints: algorithms and complexity |
scientific article; zbMATH DE number 1689581 |
Statements
13 January 2002
0 references
Dominance constraints
0 references
complexity
0 references
computational linguistics
0 references
underspecification
0 references
constraint programming
0 references
0.8861979842185974
0 references
0.8738111257553101
0 references
0.8658592104911804
0 references
0.8418248891830444
0 references
0.839393138885498
0 references
Dominance constraints: algorithms and complexity (English)
0 references
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].
0 references
