On the limiting law of the length of the longest common and increasing subsequences in random words

DOI10.1016/j.spa.2016.09.005zbMath1361.05006arXiv1505.06164OpenAlexW2143972405MaRDI QIDQ529438

Christian Houdré, Jean-Christophe Breton

Publication date: 18 May 2017

Published in: Stochastic Processes and their Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1505.06164

zbMATH Keywords

random matriceslongest common subsequencelast passage percolationlongest increasing subsequencerandom wordsDonsker's theoremoptimal alignment

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Permutations, words, matrices (05A05) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Combinatorial probability (60C05)

Related Items

A central limit theorem for the length of the longest common subsequences in random words ⋮ On the limiting law of the length of the longest common and increasing subsequences in random words with arbitrary distribution

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Asymptotics for random Young diagrams when the word length and alphabet size simultaneously grow to infinity
• A linear space algorithm for computing a longest common increasing subsequence
• On the longest common increasing binary subsequence
• Departures from many queues in series
• A scaling limit for queues in series
• A universality property for last-passage percolation paths close to the axis
• On the Limiting Shape of Young Diagrams Associated with Inhomogeneous Random Words
• On the longest increasing subsequence for finite and countable alphabets
• The Surprising Mathematics of Longest Increasing Subsequences
• On the distribution of the length of the longest increasing subsequence of random permutations
• Algorithms and Computation
• GUEs and queues
• Discrete orthogonal polynomial ensembles and the Plancherel measure
• Random words, Toeplitz determinants and integrable systems. II
• Limit theorems for height fluctuations in a class of discrete space and time growth models
• On the distributions of the lengths of the longest monotone subsequences in random words