We briefly summarize in the following how this is achieved through the computation of marginal probabilities.
we can define the probability of a prefix as: computing transition probabilities can be simply performed as: The naive computation of marginal probabilities stated in (5) requires to process a set Y(x i ) growing exponentially in size with the length of the input sequence.