
THE
FIELDS INSTITUTE FOR RESEARCH IN MATHEMATICAL SCIENCES
20th
ANNIVERSARY
YEAR 
April
2226, 2013
Workshop
on Challenges in Combinatorics on Words
at the Fields Institute
Organizers:
James Currie, University of Winnipeg
Dirk Nowotka, Universität Kiel
Jeffrey Shallit, University of Waterloo



Overview
Combinatorics on words is an old area of research that
has matured into a separate discipline in the last few decades. It studies
properties of sequences of symbols, either finite or infinite, typically over
affinite alphabet. The focus on words can be algebraic, combinatorial, or
algorithmic. The field has many connections, not only to topics in mathematics
and theoretical computer science, but also to other scientific disciplines.
Such areas inside mathematics include, for example, certain parts of algebra
(e.g., combinatorial group theory and semigroups), probability theory, number
theory, and discrete symbolic dynamics. Areas in other sciences include, for
example, crystallography, and DNA sequencing. Combinatorics on words has been
particularly connected to and motivated by theoretical computer science, e.g.,
automata theory and pattern matching algorithms.
Recent breakthroughs, however, like the resolution of the decadesold Dejean
conjecture, have led to new interest and momentum in this area. The aim of
this workshop is to bring together both experts in the various flavours of
combinatorics on words and young researchers to work on the outstanding problems
of this field. The approximate attendance is expected to be 40 persons. This
workshop will be the fourth in a series. Previous workshops were held at Oberwolfach
(August 2010); Dagstuhl (February 2011); and BIRS (February 2012).
Schedule
Sunday, April 21 
7:00 p.m. 
Meet infront of the Fields Institute, 222 College
Street, followed by walk to a local restaurant. 
Monday, April 22 
8:30 a.m. 
Doors open 
9:00 a.m. 
Registration 
9:45 a.m. 
Welcome 
10:00 a.m. 
Open Problem Presentation Session 1:
• Kalle Saari: “Minimum number of unbordered factors”
• Gwénaël Richomme: “Critical exponent
of quasiperiodic words”
• Thomas Stoll: “Sums of digits of squares”
• Luca Zamboni: “Palindromic factors”
• Amy Glen: “Total run lengths”

11:00 a.m. 
Coffee Break 
11:30 a.m. 
Open Problem Presentation Session 2:
• Eric Rowland: “pautomatic sequences, from equation
to automaton”
• Jeffrey Shallit: “Decidability of divisibility in automata”
• Francine BlanchetSadri: “Partial word representation”
• Michelangelo Bucci: “Palindrome defect conjecture”
• Michelangelo Bucci: “The class P conjecture” 
12:30 p.m. 
Lunch (on your own) 
2:15 p.m. 
Contributed Talks Session 1:
• Neil Sloane, “On curling numbers of strings of integers”
• Dimitri Hendriks, “Mixautomatic sequences” 
3:15 p.m. 
Coffee Break 
3:30 p.m. 
Tutorial: Narad Rampersad, “Pattern avoidance”,
I 
4:30 p.m. 
Open Problem Solving Session I 
6:00 p.m. 
Dinner (organized by Dirk Nowotka) 
Tuesday, April 23 
9:00 a.m. 
Contributed Talks Session 2:
• Aleksi Saarela, “On kabelian repetitionfreeness”
• Juhani Karhumäki, “Variations of the MorseHedlund
theorem for kabelian equivalence” 
10:00 a.m. 
Open Problem Presentation Session 3:
•Dirk Nowotka: “Avoidability under permutations”
• Florin Manea: “Text search under involution”
• Mike Müller: “Parikh matrices”
• Juhani Karhumäki: “kabelian complexity of (k
 1)abelian periodic words”
• Aleksi Saarela: “kabelian avoidability”

11:00 a.m. 
Coffee Break 
11:30 a.m. 
Plenary Talk – Jason Bell – “Algebraic
aspects of automatic sequences”, I 
12:30 p.m. 
Lunch 
2:15 p.m. 
Open Problem Presentation Session 4:
• Stepán Starosta: “Open questions related to
(generalized) rich words”
• Boris Adamczewski: “Repetitions in Sturmian words”
• Steffen Kopecki: “Iterated hairpin completion”
• Michael Rao: “Bifix codes on smooth words”
• James Currie: “Avoidability problems” 
3:15 p.m. 
Coffee Break 
3:30 p.m. 
Tutorial: Narad Rampersad, “Pattern avoidance”,
II 
4:30 p.m. 
Open Problem Solving Session II 
6:00 p.m. 
Dinner (organized by Jeffrey Shallit) 
Wednesday, April 24 
9:00 a.m. 
Contributed Talks Session 3:
• Bill Smyth, “Three overlapping squares & applications”
• Frantisek Franek, “On singularities of extremal periodic
strings” 
10:00 a.m. 
Open Problem Solving Session III 
11:00 a.m. 
Coffee Break 
11:30 a.m. 
Plenary Talk – Jason Bell – “Algebraic
aspects of automatic sequences”, II 
12:30 p.m. 
Lunch 
2:15 p.m. 
Contributed Talks Session 4:
• Pascal Ochem, “Application of entropy compression in
pattern avoidance”
• Florin Manea, “Discovering hidden repetitions in words”
• Eric Rowland, “pautomatic sequences and cellular automata”

3:15 p.m. 
Coffee Break 
6:00 p.m. 
Dinner (organized by Narad Rampersad) 
Thursday, April 25 
9:00 a.m. 
Contributed Talks Session 5:
• Lubomíýra Balková, “On the BrlekReutenauer
conjecture”
• Antonio Restivo, “A new complexity measure for words”

10:00 a.m 
Open Problem Solving Session IV 
11:00 a.m. 
Coffee Break 
11:30 a.m. 
Contributed Talks Session 6:
• Luke Schaeffer, “Avoiding additive cubes”
• Hamoon Mousavi, “Repetition avoidance in circular factors”

12:30 p.m. 
Lunch 
2:15 p.m. 
Contributed Talks Session 7:
• Francine BlanchetSadri, “Strict bounds for pattern
avoidance”
• Joerg Endrullis, “Degrees of streams’ 
3:15 p.m. 
Coffee Break 
3:30 p.m. 
Open Problem Solving Session V 
6:00 p.m. 
Dinner (organized by Amy Glen) 
Friday, April 26 
9:00 a.m. 
Plenary Talk – Kiran Kedlaya –
“Christol’s theorem and its analogue for generalized power series”,
I 
10:00 a.m 
Contributed Talks Session 8:
• Svetlana Puzynina, “Twins in words” (15 mins)
• Émilie Charlier, “Selfshuffling words”
(15 mins)
• Boris Adamczewski, “Some occurrences of automatic sets
in number theory” 
11:00 a.m. 
Coffee Break 
11:30 a.m. 
Open Problem Solving Session VI 
12:30 p.m. 
Lunch 
2:15 p.m. 
Plenary Talk – Kiran Kedlaya – “Christol’s
theorem and its analogue for generalized
power series”, II 
3:15 p.m. 
Coffee Break 
3:30 p.m. 
Contributed Talks Session 9:
• Michelangelo Bucci, “Palindromes in pure morphic words”

4:00 p.m. 
Open Problems – Final Report on Progress 
6:00 p.m. 
Dinner (on your own) 
Top

