This ``Research Experiences for Undergraduates (REU)'' project entitled Algorithmic Combinatorics on Words 2011-2014 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 have some undefinied positions. Research topics include computing bounds on the lengths of de Bruijn partial words, counting the number of distinct squares in partial wortds, and constructing abelian repetition-free 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 unique 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.
This "Research Experiences for Undergraduates (REU)" project entitled Algorithmic Combinatorics on Words involved 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 provided unique opportunities for summer research for approximately ten students per year for an eight-week period each year. A first objective of this interdisciplinary project was 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 "don't care" symbols.) Research in combinatorics on partial words has the potential for impacts in numerous areas, notably in molecular biology, data compression, and DNA computing. Two types of research opportunities were provided: algorithmic related research, with students performing experiments on partial words to develop algorithms and study their complexity, combinatorics related research, with students investigating properties on partial words to generate conjectures and to prove theorems. These opportunities resulted in the discovery of combinatorial algorithms on words that can be useful in string searching algorithm design for instance. Students were exposed to the techniques of language theory since this is a natural framework for formalizing and investigating strings and operations on them. Other techniques that have been used are those of graph theory, number theory, analysis, combinatorics, etc. While achieving this objective, a second objective of the project was for students to develop superior skills in mathematical writing and oral communication. A third objective of this project was 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. Papers have been published in major journals such as Discrete Applied Mathematics, Advances in Applied Mathematics, Journal of Discrete Algorithms, and Theoretical Computer Science. They have been presented at leading international conferences such as DLT, International Conference on Developments in Language Theory, LATA, International Conference on Language and Automata Theory and Applications, MFCS, International Symposium on Mathematical Foundations of Computer Science, and STACS, International Symposium on Theoretical Aspects of Computer Science. A fourth objective was 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 were established (source code is made available to interested parties). Although student participants were selected based on merit after a nationwide recruitment from a broad range of colleges and universities, a fifth objective of the project was to broaden the participation of underrepresented groups including minorities, women, and students with disabilities. For more information on the outcomes of this projet, you can visit the World Wide Web site at www.uncg.edu/cmp/reu that has been designed for this REU program. It contains the program announcement, application form, list of refereed publications with undergraduates, international presentations, etc.
