Derivation Complexity in Context-Free Grammar Forms
Seymour Ginsburg, Nancy Ann Lynch · SIAM Journal on Computing · 1977
Let F be an arbitrary context-free grammar form and $\mathcal{G}(F)$ the family of grammars defined by F. For each grammar G in $\mathcal{G}(F)$, the derivation complexity function $\Phi _G$, on the language of G, is defined for each word x as the number of steps in a minimal G-derivation of x. It is shown that derivations may always be speeded up by any constant factor n, in the sense that for each positive integer n, an equivalent grammar $G'$ in $\mathcal{G}(F)$ can be found so that $\Phi _{G'} (x) \leqq | x | / n$ for all large words $x,| x |$ denoting the length of x.