This "Research Experiences for Undergraduates (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 University of North Carolina at Greensboro will provide unique opportunities for summer research for ten students per year for an eight-week period each year. The Principal Investigator, Dr. Francine Blanchet-Sadri, can be contacted by phone at (336)256-1125 or via email at blanchet@uncg.edu.

A first objective of this interdisciplinary project is to investigate challenging problems of current interest related in particular to repetitions in partial words, pattern avoidance in partial words, subword and abelian complexity in partial words, etc. (partial words are sequences that may contain some "do not know" symbols). Research in combinatorics on partial words has the potential for impacts in numerous areas, notably in molecular biology, nano-technology, and DNA computing.

Two types of research opportunities will be provided:

1. algorithmic related research, with students performing experiments on partial words to develop algorithms and study their complexity
2. combinatorics related research, with students investigating properties on partial words to generate conjectures and to prove theorems

These opportunities will result in the discovery of combinatorial algorithms on words that can prove useful in string searching algorithm design for instance. 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 (source code will be made available to interested parties).

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.

Acknowledgement: This material is based upon work supported by the National Science Foundation under Grant Nos. DMS-0452020, DMS-0754154, and DMS-1060775. The Department of Defense is also gratefully acknowledged.

Disclaimer: Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.