# Uniform _vs._ Nonuniform Membership for Mildly Context-Sensitive Languages: A Brief Survey
## 6 The Parameterized Complexity of LCFRS Membership
Since the generation chains can be linear in the size of \(S\), it seems that the simulation needs a way of \"remembering\" what subset of \(S\) has been generated so far. We were unable to construct a solution for this. This does, of course, not mean that it is impossible to do so. We have not been able to provide any parameterized upper bound for the problem, besides the trivial XP membership. This difficulty may be explained by a conjecture of [PERSON] [27], stating that if a problem has a certain property, that [PERSON] calls _additive_, then it is either fixed-parameter tractable or does not belong to \(W[P]\). Simply put, a parameterized problem is additive if, whenever we have a number of instances \(I_{1},\ldots,I_{n}\), all with the same parameter value \(k\), we can in polynomial time compute an instance \(I\), also with parameter value \(k\), such that \(I\) is a yes-instance if and only if \(I_{1},\ldots,I_{n}\) are all yes-instances. We do not know if \(1\)-LCFRS membership, parameterized by the fan-out, is additive. We can, however, prove that \(2\)-LCFRS membership, parameterized by the fan-out, is. This means that if [PERSON]'s conjecture holds and the W-hierarchy does not collapse, then \(2\)-LCFRS membership, parameterized by the fan-out, cannot belong to \(W[P]\). For our second result, we fixed the fan-out to \(2\) (remember that an LCFRS with fan-out \(1\) is a CFG) and treated the rank as parameter. **Theorem 2** ([24]). : _The uniform membership problem for LCFRS(\(2\)), where the rank is the parameter, is \(W[1]\)-hard._  
The reduction is from \(k\)-Clique and illustrates the ability of LCFRS to transfer and compare information from different parts of the input string. Concretely, the grammar encodes the structure of the graph. Unlike the reduction for Theorem 1 above, where \(k\) items are guessed by having one nonterminal with large fan-out selecting parts of the input string, we now use \(k\) nonterminals, each with fan-out \(2\), to each select, as the first component of their tuples, one of the \(k\) vertices to be included in the clique. The second component is used for bookkeeping and verification, using a scheme that is similar to the one utilized by [PERSON] in his proof that the membership problem for LCFRS(\(2\)) is NP-hard [19]. Given the negative results reported above, we tried yet another parameterization, hoping to achieve fixed-parameter tractability. In a \"short derivation\" membership problem for a grammar,we are given an integer \(k\) as additional input. The question is whether the grammar can generate the input string by a derivation that has length at most \(k\). The length of a derivation is the number of rule applications it uses. This time we used rank, fan-out, and derivation length as parameters. Unfortunately, the problem remains W[1]-hard:  
Theorem 3 ([24]): _The uniform short derivation membership problem, where rank, fan-out, and derivation length are parameters, is W[1]-hard._  
By polynomial time reductions, all the results above immediately transfer to multiple context-free grammars, multi-component TAGs, and string-producing hyperedge replacement grammars. We discovered, however, that the situation for DTWTs is a little bit different. A DTWT is a regular tree-grammar \(G\) together with a deterministic tree-walking transducer \(T\). The system is said to produce a string \(s\) if there is a tree \(t\) produced by \(G\) such that when running \(T\) on \(t\), it accepts and outputs \(s\). As mentioned above the emptiness problem for DTWTs is hard (EXPTIME-complete). Since the emptiness problem for LCFRSs is polynomial and \(\mathrm{P}\
eq\mathrm{EXPTIME}\), this allows us to conclude that there is no polynomial time procedure for transforming DTWTs into language equivalent LCFRSs. It also turned out to allow us to show a stronger parameterized complexity result for this formalism.