  Arc-annotated sequences are useful in representing the structural information
of RNA and protein sequences. The longest arc-preserving common subsequence
problem has been introduced as a framework for studying the similarity of
arc-annotated sequences. In this paper, we consider arc-annotated sequences
with various arc structures. We consider the longest arc preserving common
subsequence problem. In particular, we show that the decision version of the
1-{\sc fragment LAPCS(crossing,chain)} and the decision version of the 0-{\sc
diagonal LAPCS(crossing,chain)} are {\bf NP}-complete for some fixed alphabet
$\Sigma$ such that $|\Sigma| = 2$. Also we show that if $|\Sigma| = 1$, then
the decision version of the 1-{\sc fragment LAPCS(unlimited, plain)} and the
decision version of the 0-{\sc diagonal LAPCS(unlimited, plain)} are {\bf
NP}-complete.
