This research addresses combinatorial and algorithmic problems related to searching and matching of strings and slightly more complicated structures such as regular expressions, arrays, trees, and compounds thereof. These problems arise in a vast variety of applications, and their impact is widely perceived as more and more crucial in future information infrastructures, as unprecedented volumes of information are increasingly amassed, disseminated and shared. A list would include the design of structures for the efficient management of large repositories of strings, arrays, and special types of graphs, fundamental primitives such as the various variants of exact and approximate searching, specific applications such as the identification of periodicities and other regularities, efficient implementations of ancillary functions such as compression and encoding of elementary discrete objects, etc. The main objective of this project is to abstract and clearly identify these problems, develop new techniques and efficient algorithms to solve them, both by serial and parallel/distributed computation, and implement the new algorithms. This research represents a joint effort by teams having bases at Polytechnic University, Georgia Tech. and Purdue University, respectively. These teams have marked commonalities in backgrounds and complementary expertise in highly specialized subareas of the field. The research represents in part a natural extension of the work carried out by the PI's under previous NSF sponsorships.
Annual Research Report