*** Applications for the Summer 2014 program are welcome until *February 27, 2014.* ***

Program Announcement

Application Form(.docx)

Presentations in Europe |
---|

Dortmund, Germany
March 10, 2011 John Lensmire, "On minimial Sturmian partial words," STACS 2011, 28th International Symposium on Theoretical Aspects of Computer Science (joint work with F. Blanchet-Sadri).
Tomar, Portugal
September 2006 F. Blanchet-Sadri, "Partial Words," F. Blanchet-Sadri, "Algorithmic Combinatorics on Words," Nathan D. Wetzler, "Counting Unbordered Partial Words," Joel Dodge, "Partial Words and the Critical Factorization Theorem," Thirteenth International Conference on Interdisciplinary Mathematical & Statistical Techniques, New University of Lisbon-Tomar Polytechnic Institute.
Braga, Portugal
July 23-25, 2012 F. Blanchet-Sadri, "Deciding Representability of Sets of Words of Equal Length," DCFS 2012, 14th International Workshop on Descriptional Complexity of Formal Systems, (joint work with S. Simmons).
London, United Kingdom
July 26-28, 2010 F. Blanchet-Sadri, "Minimum number of holes in unavoidable sets of partial words of size three," IWOCA 2010, 21st International Workshop on Combinatorial Algorithms, (joint work with Bob Chen and Aleksandar Chakarov).
Prague, Czech Republic
June 9, 2010 B. J. Wyatt, "Binary de Bruijn partial words with one hole," TAMC 2010, 7th Annual Conference on Theory and Applications of Models of Computation, (joint work with F. Blanchet-Sadri, Jarett Schwartz and Slater Stich). September 12-16, 2011 Lucas Manuelli, "Recurrent Partial Words," WORDS 2011, 8th International Conference on Words, (joint work with F. Blanchet-Sadri, Aleksandar Chakarov, Jarett Schwartz and Slater Stich).
Tarragona, Spain
May 12-13, 2006 F. Blanchet-Sadri, "Partial Words," 5th International Ph.D. School in Formal Languages and Applications. Mar 29-Apr 4, 2007 F. Blanchet-Sadri, "Fine and Wilf's periodicity result on partial words and consequences," 1st International Conference on Language and Automata Theory and Applications. Apr 2-8, 2009 Cameron Byrum, "How many holes can an unbordered partial word contain?," 3rd International Conference on Language and Automata Theory and Applications. Apr 2-8, 2009 Robert Mercas, "An answer to a conjecture on overlaps in partial words using periodicity algorithms," 3rd International Conference on Language and Automata Theory and Applications. May 26, 2011 Kevin Black, "Unary pattern avoidance in partial words dense with holes," LATA 2011, 5th International Conference on Language and Automata Theory and Applications (joint work with F. Blanchet-Sadri and Andrew Zemke).
Bilbao, Spain
April 5, 2013 Michelle Bodnar, "A Graph Polynomial Approach to Primitivity," LATA 2013, 7th International Conference on Language and Automata Theory and Applications. (joint work with F. Blanchet-Sadri, Nathan Fox, and Joe Hidakatsu). Justin Lazarow, "Suffix Trees for Partial Words and the Longest Common Compatible Prefix Problem," LATA 2013, 7th International Conference on Language and Automata Theory and Applications. (joint work with F. Blanchet-Sadri).
Paris, France
November 18, 2005 F. Blanchet-Sadri, "Mots partiels: Equations et Applications," LIAFA Laboratoire d'Informatique Algorithmique: Fondements et Applications. June 18, 2013 Brent Woodhouse, "Strict Bounds for Pattern Avoidance," DLT 2013, 17th International Conference on Developments in Language Theory (joint work with F. Blanchet-Sadri). June 21, 2013 Nathan Fox, "On the Asymptotic Abelian Complexity of Morphic Words," DLT 2013, 17th International Conference on Developments in Language Theory (joint work with F. Blanchet-Sadri).
Amiens, France
September 7, 2010 Amelia Tebbe, "Fine and Wilf's theorem for abelian periods in partial words," JM 2010, 13iemes Journees Montoises d'Informatique Theorique, (joint work with F. Blanchet-Sadri and Amy Veprauskas).
Rouen, France
July 10-12, 2013 Sinziana Munteanu, "Deciding Representability of Sets of Words of Equal Length in Polynomial Time," IWOCA 2013, 24th International Workshop on Combinatorial Algorithms, (joint work with F. Blanchet-Sadri).
Aachen, Germany
February 22, 2007 Kevin Wilson, "Correlations of Partial Words," STACS 2007, 24th International Symposium on Theoretical Aspects of Computer Science, joint work with F. Blanchet-Sadri and Joshua D. Gafni.
Trier, Germany
May 24, 2010 Eric Weissenstein, "Avoidable binary patterns in partial words," LATA 2010, 4th International Conference on Language and Automata Theory and Applications, (joint work with F. Blanchet-Sadri, Robert Mercas and Sean Simmons). Robert Mercas, "Abelian square-free partial words," LATA 2010, 4th International Conference on Language and Automata Theory and Applications, (joint work with F. Blanchet-Sadri, Jane Kim, William Severa and Sean Simmons).
Stuttgart, Germany
June 30, 2009 Josh Gunter, "Complexity of Deciding Avoidability of Partial Words," DLT 2009, 13th International Conference on Developments in Language Theory, joint work with Brandon Blakeley, F. Blanchet-Sadri and Narad Rampersad.
Louvain-la-Neuve, Belgium
September 11-14, 2012 Derek Allums, "Constructing Minimal Partial Words of Maximum Subword Complexity," JM 2012, 14th Mons Days of Theoretical Computer Science, (joint work with F. Blanchet-Sadri, John Lensmire, and B.J. Wyatt).
Stara Lesna, Slovakia
Aug 28-Sep 1, 2006 Dakota Blair, "Equations on Partial Words," MFCS 2006, 31st International Symposium on Mathematical Foundations of Computer Science, joint work with F. Blanchet-Sadri and Rebeca V. Lewis.
Bratislava, Slovakia
August 27-31, 2012 F. Blanchet-Sadri, "Abelian Pattern Avoidance in Partial Words," MFCS 2012, 37th International Symposium on Mathematical Foundations of Computer Science, (joint work with S. Simmons).
Debrecen,Hungary
October 27, 2005 F. Blanchet-Sadri, "Partial words and three periodicity results," University of Debrecen. October 28, 2005 F. Blanchet-Sadri, "On partial words," University of Debrecen. October 21-24, 2008 Emily Allen, "Counting Distinct Partial Words," International Conference on Automata, Languages and Related Topics, (joint work with F. Blanchet-Sadri, Cameron Byrum, Mihai Cucuringu and Robert Mercas). October 21-24, 2008 Michelle Cordier, "Combinatorics on Border Correlations of Partial Words," International Conference on Automata, Languages and Related Topics, (joint work with F. Blanchet-Sadri, Mihai Cucuringu and Rachel Kirsch). August 17-22, 2011 F. Blanchet-Sadri, "Algorithmic combinatorics on partial words," AFL 2011, 13th International Conference on Automata and Formal Languages . August 22, 2011 Sarah Nelson, "On operations preserving primitivity of partial words with one hole," AFL 2011, 13th International Conference on Automata and Formal Languages, (joint work with F. Blanchet-Sadri and Amelia Tebbe).
Balatonfured, Hungary
May 27-30, 2008 F. Blanchet-Sadri, "Computing Weak Periods of Partial Words," FL 2008, 12th International Conference on Automata and Formal Languages, (joint work with Taktin Oey and Timothy Rankin). May 27-30, 2008 Geoffrey Scott, "Counting Distinct Squares in Partial Words," AFL 2008, 12th International Conference on Automata and Formal Languages, (joint work with F. Blanchet-Sadri and Robert Mercas).
Nyigeryhaza, Hungary
May 23, 2008 F. Blanchet-Sadri, "Counting Unbordered Partial Words," College of Nyíregyháza, Institute of Mathematics and Computer Science, (joint work with Mihai Cucuringu, Joel Dodge and Robert Mercas). September 22, 2009 F. Blanchet-Sadri, "The Three-Squares Lemma for Partial Words with One Hole," College of Nyíregyháza, Institute of Mathematics and Computer Science, (joint work with Robert Mercas and Kristen Wetzler).
Turku, Finland
July 3-6, 2007 Justin Palumbo, "Two Element Unavoidable Sets of Partial Words," DLT 2007 11th International Conference on Developments in Language Theory. joint work with F. Blanchet-Sadri and N.C. Brownstein
Milano, Italy
July 19, 2011 F. Blanchet-Sadri, "Avoiding abelian powers in partial words," DLT 2011, 15th International Conference on Developments in Language Theory (joint work with Sean Simmons)
Salerno, Italy
September 14-18, 2009 F. Blanchet-Sadri, "The three-squares lemma for partial words with one hole," WORDS 2009 7th International Conference on Words. joint work with Robert Mercas and Kristen Wetzler September 14-18, 2009 F. blanchet Sadri, "Periods and binary partial words," WORDS 2009 7th International Conference on Words. joint work with Brian Shirey European countries where papers from this REU program have been presented at international conferences so far are colored. |

Presentations in the United States of America |
---|

Greensboro, North Carolina
October 12-14, 2007 Naomi Brownstein, "Two Element Unavoidable Sets of Partial Words." International Conference on Advances in Interdisciplinary Statistics and Combinatorics, (joint work with F. Blanchet-Sadri and Justin Palumbo).
Memphis, Tennessee
May 15-18, 2008 Naomi Brownstein, "Two Element Unavoidable Sets of Partial Words", International Conference on Interdisciplinary Mathematical and Statistical Techniques IMST 2008/FIM XVI, (joint work with F. Blanchet-Sadri and Justin Palumbo).
Washington, District of Columbia
January 6, 2009 Rachel Kirsch, "Combinatorics on Border Correlations of Partial Words", Joint Mathematics Meetings, AMS Session on Combinatorics, II (joint work with F. Blanchet-Sadri, Michelle Cordier and Mihai Cucuringu).
Burlington, Vermont
June 19, 2008 Brian Shirey, "Periods, Partial Words, and a Result of Guibas and Odlyzko," SIAM Conference on Discrete Mathematics, (joint work with F. Blanchet-Sadri).
Austin, Texas
June 16, 2010 Travis Mandel, "Computing periods in partial words ," SIAM Conference on Discrete Mathematics, (joint work with F. Blanchet-Sadri,James Carraher, Brian Shirey and Gautam Sisodia). Emily Allen, "Counting bordered partial words by critical positions ," SIAM Conference on Discrete Mathematics, (joint work with F. Blanchet-Sadri and John Lensmire).
Boston, Massachusetts
January 6, 2012 Bob Chen, "Subword Languages of Infinite Partial Words," Joint Mathematics Meetings, AMS Session, (joint work with F. Blanchet-Sadri, S. Munteanu, J. Schwartz and S. Stich). American states where papers from this REU program have been presented at international conferences so far are colored. |

Presentations in Canada |
---|

Victoria, British Columbia
June 20, 2011 Gautam Sisodia, "Periods in partial words, an algorithm," IWOCA 2011, 22nd International Workshop on Combinatorial Algorithms, (joint work with F. Blanchet-Sadri and Travis Mandel).
Halifax, Nova Scotia
June 20, 2012 Bob Chen, "Recurrence in Infinite Partial Words," SIAM DM12, Conference on Discrete Mathematics, (joint work with F. Blanchet-Sadri and S. Munteanu). June 20, 2012 Laure Flapan, "Unavoidable Sets," SIAM DM12, Conference on Discrete Mathematics, (joint work with F. Blanchet-Sadri, S. Ji, E. Reiland and S. Watkins). Bob Chen, "Counting Minimal Sturmian Words," SIAM DM12, Conference on Discrete Mathematics, (work of F. Blanchet-Sadri and S. Simmons). July 16, 2013 F. Blanchet-Sadri, "Partial Word DFAs," CIAA 2013, 18th International Conference on Implementation and Application of Automata, (joint work with Eric Balkanski, Matthew Kilgore, and B.J. Wyatt).
Toronto, Ontario
April 25, 2013 F. Blanchet-Sadri, "Strict Bounds for Pattern Avoidance," Fields Workshop on Challenges in Combinatorics on Words, (joint work with Brent Woodhouse). Canadian provinces where papers from this REU program have been presented at international conferences so far are colored. |

Presentations in Asia |
---|

Tamil Nadu, India
July 19-21, 2012 Shane Scott, "Computing the Partial Word Avoidability Indices of Ternary Patterns," IWOCA 2012, 23rd International Workshop on Combinatorial Algorithms, (joint work with F. Blanchet-Sadri and A. Lohr).
Taipei, Taiwan
August 14-17, 2012 Yang Jiao, "Squares in Binary Partial Words," DLT 2012, 16th International Conference on Developments in Language Theory, (joint work with F. Blanchet-Sadri and J. M. Machacek). Asian countries where papers from this REU program have been presented at international conferences so far are colored. |

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:

- 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 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.*