16.3.9 Exercises

Better Propagation: Modify the dominance constraint solver such that more information is propagated. The idea is to use another treeness condition based on propagators for the following disjunctions:
$\begin{array}{l} N_i\gleich N_j \vee N_i{\not=} Nj \\ N_i\domplus N_j \vee N_i\neg\domplus N_j \\ N_j \domplus N_i \vee N_j\neg\domplus N_i \\ N_j \disj N_i \vee N_i\neg\disj N_j \end{array}$
Symbolic Input: the solver's interface is not very user friendly: it takes some effort to convert a dominance constraint problem into a procedure that posts these constraints on the node representations used in the solver. A better idea would be to accept a symbolic description of a dominance constraint and automatically convert it into solver constraints. We would like a dominance constraint to be specified as a list (representing a conjunction) of ground terms; where each ground term C follows the abstract syntax below:
C ::= label(x f(y1 ... yn)) | dom(x y) | ndom(x y) | neq(x y)
where x, y and yi are atoms representing variables of the dominance constraint. dom(x y) indicates that x dominates y. ndom(x y) is its negation, and neq(x y) represents non-equality.
You should modify the solver, to accept such a list as argument and return a search predicate to solve the problem. A solution should be a record whose features are the atoms representing variables of the dominance constraint problem, and whose values are the corresponding node representations in the solver.
Graphical Output: Write a dominance constraint solver which output the solutions it computes graphically. The idea is to combine the Oz-DaVinci-Interface with the DC.ozf functor.
Configure the Explorer such that when you click at a solution node then it displays the solution tree with DaVinci.
Evaluate the dominance solver from the script and your own solver with better propagation and graphical output (previous exercises). A list of test constraints is given below. How much time is required, how many solutions are there, and how many failure nodes occur?
- Here come the typical genitive construction where one of the alternations of all quantifiers is not possible.
  Two researcher of every company work on a program
  An underspecified description of the semantics of this sentence could be given by the following dominance constraint:
  [label(x1 every_company(x)) dom(x u) label(u 'of') label(y two_resercher(y1 y2)) dom(y1 u) dom(y2 v) label(z a_program(z1)) dom(z1 v) label(v work)]
  The graph of this constraint looks as follows:
  A similar but larger constraint to the above can be produced when considering a sentence with 5 Quanitifies and two genitive constructions
  Some researcher of every departement of most companies see most samples of every product.
  An underspecified description of the semantics of this sentence could be given by the following dominance constraint:
  [label(x5 most_company(y5)) dom(y5 u4) label(u4 'of') dom(y5 u4) label(x4 a_department(y4 z4)) dom(y4 u3) dom(z4 u4) label(u3 'of') dom(y4 u3) label(x3 some_researcher(y3 z3)) dom(y3 u2) dom(z3 u3) label(u2 see) dom(y3 u2) label(x2 most_samples(y2 z2)) dom(y2 u1) dom(z2 u2) label(u1 'of') label(x1 every_product(z1)) dom(z1 u1)]
  The graph of this constraint looks as follows:
- The following is a variant of a famous sentence of Hobbs and Shieber.
  Every mother says most researchers of a company do not see every sample of a professor.
  An underspecified description of the semantics of this sentence could be given by the following dominance constraint (given in Oz notation):
  [dom(top y1) label(y1 a_professor(x1)) dom(x1 x3) label(x3 'of') dom(top y2) label(y2 every_mother(x2)) dom(x2 x13) label(x13 say(x4)) dom(x4 x5) label(x5 'not'(x9)) dom(x9 x12) label(x12 see) dom(x4 x6) label(x6 every_sample(x10 x11)) dom(x10 x3) dom(x11 x12) dom(x4 x12) dom(x4 x8) label(x8 most_researcher(x20 x15)) dom(x20 x14) dom(x15 x12) label(x14 'of') dom(top y3) label(y3 a_company(x16)) dom(x16 x14)]
  The graph of this constraint looks as follows:
- In which solver and why can the following constraint be solved by pure propagation?
  [label(y f(y1 y2) dom(y1 u) dom(y2 v) dom(x u) dom(x v)]
  The graph of this constraint looks as follows: