Manipulating derivation forests by scheduling techniques (Q1820586): Difference between revisions

This paper continues the investigation into k-parallel rewriting begun by the first author and \textit{E. Shamir} [J. Comput. Syst. Sci. 30, 249-273 (1985; Zbl 0601.68057)] and by the authors [Theor. Comput. Sci. 37, 217- 243 (1985; Zbl 0602.68058)]. This rewriting mechanism is a generalization of context-free rewriting; instead of applying a single production (or, alternatively, arbitrarily many productions) at each derivation step, exactly k productions are applied. In the works mentioned above, polynomial dynamic programming algorithms were presented which require constant k and propagating grammars. We solve the various membership problems left open in the authors' earlier paper, for arbitrary grammars, using Scheduling Theory. We develop various kinds of pumping, obtaining bounds on the sizes of k-derivations and k-derivation forests. A polynomial dynamic programming membership algorithm is presented for arbitrary (i.e., possibly nonpropagating) grammars, for fixed k. If k is a variable of the problem, then membership is in NP and, hence, by the authors' earlier paper, NP-complete. For unary alphabets, the latter problem is polynomial. Similarly, membership is polynomial in the size of k if only k is variable.