|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'500'096
Articles rated: 2609
18 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Random modification effect in the size of the fluctuation of the LCS of two sequences of i.i.d. blocks | | Heinrich Matzinger
; Felipe Torres
; | | Date: |
11 Nov 2010 | | Abstract: | The problem of the order of the fluctuation of the Longest Common Subsequence
(LCS) of two independent sequences has been open for decades. There exist
contradicting conjectures on the topic, due to Chvatal - Sankoff in 1975 and
Waterman in 1994. In the present article, we consider a special model of i.i.d.
sequences made out of blocks. A block is a contiguous substring consisting only
of one type of symbol. Our model allows only three possible block lengths, each
been equiprobable picked up. In this context, we introduce a random operation
(random modification) on the blocks of one of the sequences. In the present
article, we develop the techniques to prove the following: if we suppose that
the random modification increases the length of the LCS with high probability,
then the order of the fluctuation of the LCS is as conjectured by Waterman.
This result is a key technical part in the study of the size of the fluctuation
of the LCS for sequences of i.i.d. blocks, developed by Matzinger and Torres. | | Source: | arXiv, 1011.2679 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER