, finite set
R
of strings from
.
such that
w
is a subsequence of each
,
i.e. one can get
w
by taking away letters from each
x
.
, where
m
is the length of the
shortest string in
R
[
152
].
for any
,
where in is the maximum of
|R|
and
[
49
], [
192
] and [
40
].
is fixed [
192
]
and [
58
].
Variation in which the objective is to find the shortest maximal common
subsequence (a subsequence that cannot be extended to a longer common
subsequence) is A
PX
-hard even over the binary alphabet
[
272
].
Viggo Kann