This three-year REU project entitled "Algorithmic Combinatorics on Words" involves students in research at the crossroads between Mathematics and Computer Science. Words, or strings 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. The Department of Mathematical Sciences of the University of North Carolina at Greensboro will provide unique opportunities for summer research for eight students per year for an eight-week period each year.
A first objective of this interdisciplinary project is to investigate challenging problems of current interest related in particular to coding, primitivity testing, and computing periods in partial words, or strings that may contain a number of "do not know" symbols. Two types of research opportunities will be provided: (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 on partial words to generate conjectures. These opportunities will result in the discovery of combinatorial algorithms on words. Students will be exposed to the techniques of language theory since this is a natural framework for formalizing and investigating strings and operations on them. 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. As a result, World Wide Web server interfaces for automated use of the programs related to the combinatorial algorithms will be established. 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 broaden the participation of underrepresented groups including minorities, women, and students with disabilities. Through participating in this project, students will get motivated to pursue graduate studies in mathematical sciences as they feel the excitement and reward of making original contributions.
