BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Semi-local string comparison - Alexander Tiskin\, Department of Co
 mputer Science\, University of Warwick
DTSTART:20121031T141500Z
DTEND:20121031T151500Z
UID:TALK40690@talks.cam.ac.uk
CONTACT:Stephen Clark
DESCRIPTION: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\n
 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. A
 part from an important role that this generalised problem\nplays in string
  algorithms\, it turns out to have surprising connections with semigroup a
 lgebra\, computational geometry\, planar graph algorithms\, comparison net
 works\, as well as practical applications in\ncomputational biology. The t
 alk will present an efficient solution for the semi-local LCS problem\, an
 d will survey some related results and applications. Among those are dynam
 ic LCS support\; fast clique\ncomputation in special graphs\; fast compari
 son of compressed strings\; parallel string algorithms.\n
LOCATION:Lecture Theatre 1\, Computer Laboratory
END:VEVENT
END:VCALENDAR