Longest common subsequences in sets of words

DOI10.1137/140975000MaRDI QIDQ5246103zbMATH OpenOpenAlexFDO

Authors Boris Bukh, Jie Ma

Publication date 17 April 2015

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

balanced wordcommon subsequencelongest common subsequencetwins in words

Mathematics Subject Classification ID

Extremal combinatorics (05D99) Combinatorics on words (68R15)

Abstract: Given a set of $t$ words of length $n$ over a $k$-letter alphabet, it is proved that there exists a common subsequence among two of them of length at least $fracnk+c{n}^{1-1/(t-k-2)}$, for some $c>0$ depending on $k$ and $t$. This is sharp up to the value of $c$.

Recommendations

• On the asymptotic average length of a maximum common subsequence for words over a finite alphabet
• Twins in words and long common subsequences in permutations
• LATIN 2004: Theoretical Informatics
• Expected length of the longest common subsequence for large alphabets
• Common Subsequences and Supersequences and their Expected Length

Cited in

(9)

• On the longest common subsequence of Thue-Morse words
• Universal arrays
• Longest Common Extensions in Partial Words
• Twins in words and long common subsequences in permutations
• Maximal Words in Sequence Comparisons Based on Subword Composition
• scientific article; zbMATH DE number 736284 (Why is no real title available?)
• Subsequence covers of words
• Shuffle squares and reverse shuffle squares
• Diametric problem for permutations with the Ulam metric (optimal anticodes)

This page was built for publication: Longest common subsequences in sets of words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5246103)