In the following we present an upper bound on the reduced cost, r gp g,p,c ≥ r gp g,p,c , which decomposes in a way that allows for more efficient search.
using this bound, we find all new grandparent edgesN for which this upper bound is positive: Next we prune away all but the grandparent edges for which the exact reduced cost is positive:  we maximize over all possible attribute values v any token g could have, and any possible relation e a token g can have to p and c. Notice that these bounds can be calculated offline, and hence amortize after deployment of the parser.