Applications of scheduling theory to formal language theory (Q1082085)

Context-free grammars are extended to the case where it is required that at each derivation step, a fixed number k of nonterminals must be rewritten in parallel. This way of rewriting constitutes a ''missing link'' between context-free rewriting, where only one nonterminal is rewritten in each step \((k=1)\), and E0L rewriting, where always all nonterminals are rewritten. We approach the study of these families by investigating their computational complexity. In both the E0L and CF case, as well as for the case \(k=2\), simple dynamic programming membership algorithms exist. We solve the general problem using results from scheduling theory. Rewriting k symbols at each derivation step corresponds to scheduling the corresponding derivation forest on k processors. Using scheduling theory techniques, we present dynamic programming membership algorithms that run in polynomial time, for constant k. On the other hand, it is shown that membership is NP-hard if k is a variable of the problem, even when the grammar is fixed. An analogous NP-hardness result is shown for the case where the k symbols to be rewritten are required to be adjacent.