REU Site: Algorithmic Combinatorics on Words 2008-2011

University Of North Carolina Greensboro, Greensboro NC

Investigators

Abstract

This ``Research Experiences for Undergraduates (REU)'' project entitled Algorithmic Combinatorics on Words 2008-2011 involves students at the crossroads between Mathematics and Computer Science. Words, or sequences of symbols over a finite alphabet, are natural objects in several research areas including group theory, number theory, automata and formal language theory, coding theory, and theory of algorithms. This project will provide unique opportunities for summer research for ten students per year for an eight-week period each year. The five goals or objectives for student activities are: A first objective of this interdisciplinary project is to investigate challenging problems of current interest related to partial words, or sequences that may contain a number of ``do not know'' symbols. Research topics include computing periods in partial words, counting primitive and unbordered partial words, and classifying unavoidable sets of partial words. Combinatorics on partial words is a promising line of research that has practical uses in several areas, notably in molecular biology and bio-inspired computing, as well as in the design of a new generation of pattern matching algorithms. Two types of research opportunities will be emphasized: (1) computer related research, with students writing programs to perform experiments on partial words and to implement algorithms; and (2) combinatorics related research, with students investigating properties of partial words to generate conjectures, to prove theorems, and to discover algorithms. While achieving this objective, a second objective of the project is for students to develop superior skills in mathematical writing and oral communication. A third objective of this project is to submit the resulting original and high quality research on algorithmic combinatorics on words done with undergraduate students to leading journals and to encourage them to present it at national/international meetings or conferences. A fourth objective is for students to gain experience in the use of computers and their interaction in mathematical research. In addition, students will establish World Wide Web server interfaces for automated use of the programs related to the discovered combinatorial algorithms. Although student participants will be selected based on merit after a nationwide recruitment from a broad range of colleges and universities, a fifth objective of the project is to encourage the participation of underrepresented groups including women, minorities, and persons with disabilities. As a result of taking part in this project, students will get motivated and will become better prepared to pursue advanced degree programs in mathematical sciences. The site is co-funded by the Department of Defense in partnership with the NSF REU program.