Thermodynamical approach to the longest common subsequence problem

dc.creatorAmsalu, S
dc.creatorMatzinger, H
dc.creatorVachkovskaia, M
dc.date2008
dc.dateJUN
dc.date2014-11-20T07:57:58Z
dc.date2015-11-26T16:09:14Z
dc.date2014-11-20T07:57:58Z
dc.date2015-11-26T16:09:14Z
dc.date.accessioned2018-03-28T22:57:50Z
dc.date.available2018-03-28T22:57:50Z
dc.identifierJournal Of Statistical Physics. Springer, v. 131, n. 6, n. 1103, n. 1120, 2008.
dc.identifier0022-4715
dc.identifierWOS:000256085700006
dc.identifier10.1007/s10955-008-9533-z
dc.identifierhttp://www.repositorio.unicamp.br/jspui/handle/REPOSIP/58144
dc.identifierhttp://www.repositorio.unicamp.br/handle/REPOSIP/58144
dc.identifierhttp://repositorio.unicamp.br/jspui/handle/REPOSIP/58144
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1266567
dc.descriptionWe 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 root n.
dc.description131
dc.description6
dc.description1103
dc.description1120
dc.languageen
dc.publisherSpringer
dc.publisherNew York
dc.publisherEUA
dc.relationJournal Of Statistical Physics
dc.relationJ. Stat. Phys.
dc.rightsfechado
dc.rightshttp://www.springer.com/open+access/authors+rights?SGWID=0-176704-12-683201-0
dc.sourceWeb of Science
dc.subjectlongest common subsequence
dc.subjectinteracting particle systems
dc.subjectoptimal sequence alignment
dc.subjectExpected Length
dc.subjectLarge Deviations
dc.subjectUpper-bounds
dc.subjectSequences
dc.subjectPercolation
dc.subjectPlane
dc.titleThermodynamical approach to the longest common subsequence problem
dc.typeArtículos de revistas


Este ítem pertenece a la siguiente institución