Título: Longest common subsequences represented as particle processes
Palestrante: Heinrich Matzinger
Local: Auditório do NUMEC (ao lado do bloco C)
Data: quinta-feira, 10 de maio, às 14h00
Resumo:
A common subsequence of two sequences X and Y is a sequence which is
a subsequence of both X and Y. A common subsequence of maximal length
is called Longest Common Subsequence (LCS). We take the sequences
X and Y to be two random sequences of length n which are also independent
of each other. The length of the LCS of X and Y is a random variable which
we denote by L_n. The asymptotic order of magnitude of the variance of
L_n when n goes to infinity is not know in general. We show that the
LCS problem can be reformulated as a interacting particle problem in random
media.
Fórum