Semi-local string comparison

Add to your list(s) Download to your calendar using vCal

• Alexander Tiskin, Department of Computer Science, University of Warwick
• Wednesday 31 October 2012, 14:15-15:15
• Lecture Theatre 1, Computer Laboratory.

If you have a question about this talk, please contact Stephen Clark.

The computation of a longest common subsequence (LCS) between two strings is a classical algorithmic problem. Some applications require a generalisation of this problem, which we call semi-local LCS . It asks for the LCS between a string and all substrings of another string, and/or the LCS between all prefixes of one string and all suffixes of another. Apart from an important role that this generalised problem plays in string algorithms, it turns out to have surprising connections with semigroup algebra, computational geometry, planar graph algorithms, comparison networks, as well as practical applications in computational biology. The talk will present an efficient solution for the semi-local LCS problem, and will survey some related results and applications. Among those are dynamic LCS support; fast clique computation in special graphs; fast comparison of compressed strings; parallel string algorithms.

This talk is part of the Computer Laboratory Wednesday Seminars series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge talks
• Chris Davis' list
• Computer Laboratory Wednesday Seminars
• Computer Laboratory talks
• Graduate-Seminars
• Guy Emerson's list
• Interested Talks
• Lecture Theatre 1, Computer Laboratory
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• computer science
• se393's list

Note that ex-directory lists are not shown.