Publication details

Saarland University Computer Science

A Model-Eliminative Treatment of Quantifier-free Tree Descriptions

Denys Duchier

Algebraic Methods in Language Processing, AMILP~2000, TWLT~16, pp. 55--66, Universiteit Twente, Faculteit Informatica, May 2000

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


Webmaster, Wed Sep 16 10:47:00 2009