  Recently, the well-known dependency pair (DP) framework was adapted to a
dependency tuple framework in order to prove almost-sure innermost termination
(iAST) of probabilistic term rewrite systems. While this approach was
incomplete, in this paper, we improve it into a complete criterion for iAST by
presenting a new, more elegant definition of DPs for probabilistic term
rewriting. Based on this, we extend the probabilistic DP framework by new
transformations. Our implementation in the tool AProVE shows that they increase
its power considerably.
