Show simple item record

dc.contributor.advisorHoudre, Christian
dc.contributor.authorZhang, Yuze
dc.date.accessioned2020-01-14T14:45:06Z
dc.date.available2020-01-14T14:45:06Z
dc.date.created2019-12
dc.date.issued2019-08-27
dc.date.submittedDecember 2019
dc.identifier.urihttp://hdl.handle.net/1853/62266
dc.description.abstractThe study of LIn, the length of the longest increasing subsequences, and of LCIn, the length of the longest common and increasing subsequences in random words is classical in computer science and bioinformatics, and has been well explored over the last few decades. This dissertation studies a generalization of LCIn for two binary random words, namely, it analyzes the asymptotic behavior of LCbBn, the length of the longest common subsequences containing a fixed number, b, of blocks. We first prove that after proper centerings and scalings, LCbBn, for two sequences of i.i.d. Bernoulli random variables with possibly two different parameters, converges in law towards limits we identify. This dissertation also includes an alternative approach to the one-sequence LbBn problem, and Monte-Carlo simulations on the asymptotics of LCbBn and on the growth order of the limiting functional, as well as several extensions of the LCbBn problem to the Markov context and some connection with percolation theory.
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.publisherGeorgia Institute of Technology
dc.subjectLongest common subsequences with blocks
dc.subjectRandom words
dc.titleTopics on the length of the longest common subsequences, with blocks, in binary random words
dc.typeDissertation
dc.description.degreePh.D.
dc.contributor.departmentMathematics
thesis.degree.levelDoctoral
dc.contributor.committeeMemberFoley, Robert
dc.contributor.committeeMemberKoltchinskii, Vladimir
dc.contributor.committeeMemberDamron, Michael
dc.contributor.committeeMemberTikhomirov, Konstantin
dc.contributor.committeeMemberHanson, Jack
dc.date.updated2020-01-14T14:45:06Z


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record