  The parameterized complexity of a problem is considered "settled" once it has
been shown to lie in FPT or to be complete for a class in the W-hierarchy or a
similar parameterized hierarchy. Several natural parameterized problems have,
however, resisted such a classification. At least in some cases, the reason is
that upper and lower bounds for their parameterized space complexity have
recently been obtained that rule out completeness results for parameterized
time classes. In this paper, we make progress in this direction by proving that
the associative generability problem and the longest common subsequence problem
are complete for parameterized space classes. These classes are defined in
terms of different forms of bounded nondeterminism and in terms of simultaneous
time--space bounds. As a technical tool we introduce a "union operation" that
translates between problems complete for classical complexity classes and for
W-classes.
