Parsing time is then exponential in the input grammar size, since |G| depends on both f and r. In the development of efficient algorithms for parsing based on LCFRS the crucial goal is therefore to optimize the term f • (r + 1).
it seems unlikely that this can still be done in linear time, since the problem of binarization for LCFRS in general, i.e., without any bound on the fan-out, might not be solvable in polynomial time.