I was reading the following paper (http://aclweb.org/anthology/W/W13/W13-1801.pdf) and they state that, given a Probabilistic Finite Automata $A$ and a string $w$, finding the probability $Pr_A(w\Sigma^*)$ is simple (section 3, property 3. Just before the start of section 4). However, this isn't immediately clear to me since, even using some dynamic programming approach, you may have to compute the probability of an infinite number of paths (since it is not acyclic) starting at all of the states that are the last state reached in a path, $\Theta$, that generates $w$.
I was not able to find an answer in the references of that paper or any relevant papers on the subject.
To summarize, I am looking for an algorithm that, given a PFA $A$ and a string $w \in \Sigma^*$, returns the probability $Pr_A(w\Sigma^*)$. in other words, the probability of any string having $w$ as a prefix.
Thanks in advance.