next up previous
Next: Parsing bracketed inputs Up: Computing outer probabilities Previous: Reverse completion

Reverse completion (transitive)

displaymath8833

for all pairs of states tex2html_wrap_inline8657 and tex2html_wrap_inline8273 in the chart, such that the unit-production relation tex2html_wrap_inline8395 is non-zero. Then

eqnarray6415

The first summation is carried out once for each state tex2html_wrap_inline8841 , whereas the second summation is applied for each choice of Z, but only if tex2html_wrap_inline8845 is not itself a unit production, i.e., tex2html_wrap_inline8847 .

Rationale. This increments tex2html_wrap_inline8817 the equivalent of tex2html_wrap_inline8395 times, accounting for the infinity of surroundings in which Y can occur if it can be derived through cyclic productions. Note that the computation of tex2html_wrap_inline8809 is unchanged, since tex2html_wrap_inline8187 already includes an infinity of cyclically generated subtrees for Y, where appropriate.



Andreas Stolcke
Sat Jun 29 21:49:02 PDT 1996