To `repair' this utterance we simply alter the word `bank' into the word `river side' and we obtain an unambiguous result. Similar examples can be constructed for structural ambiguities. Consider the German sentence:
which is ambiguous (in German) between `withdraw [the army of Croatia]' and `[withdraw [the army] away from Croatia]'. In German this ambiguity can be repaired locally simply by changing the order of `aus Kroatien' and `die Armee', which forces the second reading. Thus again we only need to change only a small part of the utterance in order for it to be un-ambiguous.
Given a derivation tree t of a generated sentence s, we can now mark the places where the ambiguity occurs as follows. If s is ambiguous it can be parsed in several ways, giving rise to a set of derivation trees T = t1...tn. We can now compare t with the set of trees T in a top-down fashion. If for a given node label in t there are several possible labels at the corresponding nodes in T then we have found an ambiguous spot, and the corresponding node in t is marked. Thus, in the previous example of structural ambiguity we may first generate sentence (6) above. After checking whether this sentence is ambiguous we obtain, as a result, the marked derivation tree of that sentence. A marked node in such a tree relates to an ambiguity. The relevant part of the resulting derivation tree of the example above may be the tree in figure 3.
mark_ds(,). mark_ds([H|T],[Hs|Ts]):- mark(H,Hs), mark_ds(T,Ts).
get_f(,,). get_f([t(_,[H3|B],_)|T], [t(_,B,_)|T2],[H3|T3]):- get_f(T,T2,T3).
The following definition assumes that grammar rules are represented simply as rule(Name, Mother, Ds) where Name is the rule name, Mother is the mother sign and Ds is a list of daughter signs. The predicate mgen is used to generate an utterance, using a marked derivation tree as an extra guide. mgen(sign(Lf,Str,S,D),t(Name,Ds,n)):- rule(Name,sign(Lf,Str,S,D),Kids), mgen_ds(Kids,Ds).
mgen_ds(,_). mgen_ds([S|T],[Stree,Ttree]):- mgen(S,Stree), mgen_ds(T,Ttree).
It is possible that by successively moving markers upwards in a marked derivation tree the root node of the tree will be marked. If also in that case no unambiguous alternative will be possible then this means that the generator is not able to compute a grammatical unambiguous alternative. In this case the whole monitored generation process terminates and the strategic component has to decide whether to utter the ambiguous structure or to provide an alternative logical form.
The following definition of the predicate mark_l_g(Tree, Set, Guide) will (procedurally speaking) first construct the `guide' Guide given a derivation tree Tree and a set of derivation trees Set; upon backtracking it will push the markers in the tree one level upward at the time. l_g(Tree,Tree). l_g(Tree,Guide):- one_up(Tree,Tree2), l_g(Tree2,Guide).
one_up_ds(,). one_up_ds([H|T],[H2|T2]):- one_up(H,H2), one_up_ds(T,T2).
Now, the whole algorithm can be completed as follows. 6
revision(sign(LF,Str1,Syn1,D1),TreeSet,sign(LF,Str,Syn,D)):- mark_l_g(D1,TreeSet,Guide), mgen(sign(LF,Str,Syn,D),Guide), unambiguous(sign(_,Str,_,_)).
find_all_parse(Sign,SignSet,TreeSet) :- setof(Sign,parse(Sign),SignSet), extract_trees(SignSet,TreeSet).
Summarising, the generator first generates a possible utterance. This utterance is then given as input to the monitor. The monitor calls the parser to find which parts of that utterance are ambiguous. These parts are marked in the derivation tree associated with the utterance. Finally the monitor tries to generate an utterance which uses alternative derivation trees for the marked, i.e., ambiguous parts, eventually pushing the markers successively upwards.
Suppose indeed that the generator, as a first possibility, constructs this sentence in order to realize the (simplified) semantic representation:
The monitored generation will then try to find alternative possibilities at these marked nodes. However, no such alternatives exist. Therefore, the markers are pushed up one level, obtaining the derivation tree given in figure 6.
At this point the monitored generator again tries to find alternatives for the marked nodes, this time successfully yielding:
At this point we may stop. However, note that if we ask for further possibilities we will eventually obtain all possible results. For example, if the markers are pushed to the root node of the derivation tree we will also obtain
The strategy is sound and complete in the sense that no ambiguous utterances will be produced, and all un-ambiguous utterances are produced. If for a given semantic structure no un-ambiguous utterance is possible, the current strategy will not deliver a solution (it is foreseen that in such cases the planner decides what should happen).
The strategy is completely independent on the grammars that are being used (except for the reliance on derivation trees). Even more interestingly, the nature of the underlying parsing and generation strategy is not important either. The strategy can thus be used with any parsing- or generation strategy.
During the monitored generation previously generated structures are re-used, because only the ambiguous partial structures have to be re-generated.
Finally, for the proposed strategy to be meaningful, it must be the case that reversible grammars are being used. If this were not the case then it would not make sense to compare the derivation tree of a generation result with the derivation trees which the parser produces.