Tree descriptions are widely used in computational linguistics for talking and reasoning about trees. For practical applications,
it is essential to be able to decide satisfiability and enumerate
solutions efficiently. This challenge cannot realistically be met by
brute force enumeration. However it can be addressed very effectively
by constraint propagation as provided by modern constraint technology.
Previously, we studied the conjunctive fragment of tree descriptions and showed how the problem of finding minimal models of a conjunctive tree description could be transformed into a constraint satisfaction problem (CSP) on finite set variables.
In this paper, we extend our account to the fragment that admits both negation and disjunction, but still leaves out quantification. Again we provide a reduction to a CSP. While our previous encoding introduced the reader to set constraints and disjunctive propagators, we now extend our arsenal with selection propagators.
Download PDF Show BibTeX
Login to edit
Wed Sep 16 10:47:00 2009