Exact and Approximation Pattern Matching, and Network Routing

点击翻译按钮获取中文摘要

The main focus of this proposal is on "pattern matching", the identifying of an object, called the "pattern", in a larger body, often called the `text". The pattern might be a DNA sequence and the text a (large) collection of DNA sequences. While it is fairly well understood how to find exact matches of an object, finding similar instances of an object is not as well understood, or at least it is not known how to find them nearly as efficiently. Further, it is natural to suppose that this task can be carried out progressively more efficiently the greater the similarity between the objects being matched. But, by and large, achieving this remains problematic. The aim of this project is to develop methods whose efficiency improves in tandem with increased similarity. Motivating problems include the already mentioned DNA matching, matching of words or phrases in bodies of text, and matching of objects in images. A secondary focus for this proposal is the study of network switches; more specifically, the devising of methods for sending (routing) messages and designs for facilitating such routings.