However, it can be shown that if the rules in R have at most depth two and G D is deterministic, then the entire above construction can be computed in time O(|G D | • |R|) (Koller and Thater, 2010).
we have shown how to compute the weakest readings of a hypernormally connected dominance graph D, as approximated by a weakening rewrite system R, in time linear in the size of G D and linear in the size of R. This is a dramatic improvement over the best previous algorithm, which was quadratic in |conf(D)|.