Thermodynamical Approach to the Longest Common Subsequence Problem

Autor:	Marina Vachkovskaia, Heinrich Matzinger, Saba Amsalu
Rok vydání:	2008
Předmět:	Combinatorics Longest common subsequence problem Discrete mathematics Particle model Differential equation Particle Random media Binary number Statistical and Nonlinear Physics Scale (descriptive set theory) Longest increasing subsequence Mathematical Physics Mathematics
Zdroj:	Journal of Statistical Physics. 131:1103-1120
ISSN:	1572-9613 0022-4715
DOI:	10.1007/s10955-008-9533-z
Popis:	We introduce an interacting particle model in a random media and show that this particle process is equivalent to the Longest Common Subsequence (LCS) problem of two binary sequences. We derive a differential equation which links the mean LCS-curve to the average speed of the particles given their density and prove that the average speed of the particles and density converges uniformly on every scale which is somewhat larger than \(\sqrt{n}\) .
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::a5efffaa062c64ce57ebb364efdb56e6 https://doi.org/10.1007/s10955-008-9533-z Zobrazit plný text záznamu Plný text ve formátu PDF