Mathematics of String Spaces and Algorithmic Applications (09w5124)

The Banff International Research Station will host the “Mathematics of String Spaces and Algorithmic Applications” workshop next week, January 25 - January 30, 2009.

Strings from a given alphabet can be treated as objects. There are a number of distance measures that can be used to determine the similarity between such objects: perhaps the most common one is the edit distance which is defined as the minimum number of single symbol insertions, deletions and replacements that can transform one string to another. Variants of this measure involve edits that are performed on substrings (or blocks) such as deleting a whole substring, or copying a substring somewhere else in the string.

String spaces are not as well understood as normed vector spaces. In vector spaces, the specific ordering of dimensions does not typically have an effect on the distance measure used; in string spaces, the specific ordering of symbols is of high significance. Thus, recent work on improving our understanding of string spaces has aimed to provide distance preserving embeddings of string spaces to well understood normed vector spaces. Such embeddings also have applications to many domains such as indexing, compressing, sketching and streaming of strings.

The proposed workshop thus aims to discuss recent results that have helped us improve our understanding of the mathematical properties of string spaces by investigating their relationship to normed vector spaces. In addition to the embeddings of string spaces to L_1, L_2 and other vector spaces, we will also discuss applications of such results to more traditional problems in combinatorial pattern matching.

The Banff International Research Station for Mathematical Innovation and Discovery (BIRS) is a collaborative Canada-US-Mexico venture that provides an environment for creative interaction as well as the exchange of ideas, knowledge, and methods within the Mathematical Sciences, with related disciplines and with industry. The research station is located at The Banff Centre in Alberta and is supported by Canada's Natural Science and Engineering Research Council (NSERC), the US National Science Foundation (NSF), Alberta's Advanced Education and Technology, and Mexico's Consejo Nacional de Ciencia y Tecnologí­a (CONACYT).