Manipulating derivation forests by scheduling techniques

arbitrary grammars generalization of context-free rewriting k-parallel rewriting membership complexity membership problems nonpropagating grammars NP polynomial dynamic programming membership algorithm pumping

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Review text

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.

Recommendations

Cites work

Cited in

(5)

This page was built for publication: Manipulating derivation forests by scheduling techniques

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1820586)