REU Partial Words Visit The University of North Carolina Greensboro homepage. Visit the National Science Foundation web page.

Algorithmic Combinatorics on Words
Research Experiences for Undergraduates
Visit Dr. Francine Blanchet-Sadri's homepage.

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

Program Announcement
Application Form(.docx)

Application Resources Contact UNCG campus and Greensboro,NC Information
Summer 2005 Information Summer 2006 Information Summer 2007 Information
Summer 2008 Information Summer 2009 Information Summer 2010 Information
Summer 2011 Information Summer 2012 Information Summer 2013 Information
Summer 2014 Information Summer 2015 Information Summer 2016 Information
Presentations in Europe
Europe Tomar, Portugal Braga, Portugal United Kingdom Czech Republic Spain Bilbao, Spain France Amiens, France Rouen, France Dortmund, Germany Aachen, Germany Stuttgart, Germany Trier, Germany Louvain-la-Neuve, Belgium Stara Lesna, Slovakia Bratislava, Slovakia Hungary Balatonfured, Hungary Nyigeryhaza, Hungary Finland Milano, Italy Italy
Dortmund, Germany 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 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 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, UK 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 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 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 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 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).
Paris, France 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).
Paris, France 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 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.
Aachen, Germany 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 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 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 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 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 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 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 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 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 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 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.
To see details of the presentations, move the cursor on the cities marked in the colored countries.

Presentations in the United States of America
US Greensboro, NC Memphis, TN Washington DC Burlington, VT Austin, TX Boston, MA
Greensboro, North Carolina 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 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 DC 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 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 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 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.
To see details of the presentations, move the cursor on the cities marked in the colored states.

Presentations in Canada
Canada Victoria, British Columbia Halifax, Nova Scotia Toronto, Ontario
Victoria, British Columbia 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 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 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.
To see details of the presentations, move the cursor on the cities marked in the colored provinces.

Presentations in Asia
Asia Tamil Nadu, India Taipei, Taiwan
Tamil Nadu, India 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 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.
To see details of the presentations, move the cursor on the cities marked in the colored countries.


Project Summary

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.

Intellectual Merit

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.

Broader Impacts

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.


Website designed by Margaret Moorefield, 2005

This page has been accessed hit counter times since May 18, 2005 at 10:24 AM EST.
Valid XHTML 1.0! Valid CSS!