Bounding the expected length of longest common subsequences and forests

Consultar RECERCAT

Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/82911

Título:	Bounding the expected length of longest common subsequences and forests
Autor/a:	Baeza-Yates, Ricardo A; Gavaldà Mestre, Ricard; Navarro, Gonzalo
Otros autores:	Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
Abstract:	Subsumed by LSI-98-50-R
Abstract:	We present two techniques to find upper and lower bounds for the expected length of longest common subsequences of forests of two random sequences of the same lenght, over a fixed size, uniformly distributed alphabet. We emphasize the power of the methods used, which are Markov chains and Kolmogorov complexity. As a corollary we obtain new lower and upper bounds for the problems mentioned.
Materia(s):	-Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica -Longest common subsequence -LCS
Derechos:
Tipo de documento:	Artículo - Versión publicada Informe
Compartir:

Xhafa Xhafa, Fatos; Navarro, Gonzalo

Berral García, Josep Lluís; Poggi Mastrokalo, Nicolas; Alonso López, Javier; Gavaldà Mestre, Ricard; Torres Viñals, Jordi; Parashar, Manish

Gavaldà Mestre, Ricard; Universitat Politècnica de Catalunya.

Bifet Figuerol, Albert Carles; Holmes, Geoff; Pfahringer, Bernhard; Gavaldà Mestre, Ricard

Bifet Figuerol, Albert Carles; Holmes, Geoffrey; Pfahringer, Bernhard; Gavaldà Mestre, Ricard

Coordinación

Patrocinio