Abstract.

Let $f(n)$ be the expected length of a longest common subsequence of two random binary sequences of length $n$. It is known that the limit $\gamma=\lim\limits_{n\to\infty}n^{-1}f(n)$ exists. Improved upper bounds for $\gamma$ are given using a new method.

Note: This paper also appeared in Proceedings of 11th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science 775(1994):669-678

Bibtex entries:

@Article{DaPa95,
  author =       "Vlado Dan{\v c}{\'\i}k and Mike Paterson",
  title =        "Upper Bounds for the Expected Length of a Longest Common 
                  Subsequence of two Binary Sequences",
  journal =      "Random Structures and Algorithms",
  year =         "1995",
  number =       "4", 
  volume =       "6", 
  pages  =       "449-458" 
}


@InProceedings{DaPa94,
  author =       "Vlado Dan{\v c}{\'\i}k and Mike Paterson",
  title =        "Upper Bounds for the Expected Length of a Longest Common 
                  Subsequence of two Binary Sequences",
  editor =       "P. Enjalbert and E. W. Mayr and K.W.Wagner",
  pages =        "669-678",
  booktitle =    "11th Annual Symposium on Theoretical Aspects of
                  Computer Science, Proceedings",
  year =         "1994",
  publisher =    "Lecture Notes in Computer Science 775, Springer-Verlag",
}

Return to Previous Level

USC Computational Biology Home Page