At stage k of the state elimination procedure on D, state q 0 is only connected to states up to label k − 1, thus α k−1 0,k+1 = ∅.
since we can simplify the expression as In addition, we recall and Algorithm 2 is for the offline setting-we know the entire string ahead of time and compute the infix probabilities of each of its prefixes incrementally.