With T being the seed matrix, we define where T (i) is defined recursively as: Under Condition 4.1, one can show that given an LCFRS derivation tree t over the input string, each node in t must appear in the transitive closure matrix T + .
as such, the total complexity is O(tn ωd ), where t is the number of iterations required to converge.