THE FIELDS INSTITUTE FOR RESEARCH IN MATHEMATICAL SCIENCES 20th ANNIVERSARY YEAR

April 22-26, 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 decades-old 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” (slides) • 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: “p-automatic sequences, from equation to automaton” (slides) • Jeffrey Shallit: “Decidability of divisibility in automata” (slides) • Francine Blanchet-Sadri: “Partial word representation” (slides) • 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, “Mix-automatic sequences” (slides)
3:15 p.m.	Coffee Break
3:30 p.m.	Tutorial: Narad Rampersad, “Pattern avoidance”, I (slides)
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 k-abelian repetition-freeness” • Juhani Karhumäki, “Variations of the Morse-Hedlund theorem for k-abelian equivalence”
10:00 a.m.	Open Problem Presentation Session 3: •Dirk Nowotka: “Avoidability under permutations” • Florin Manea: “Text search under involution” (slides) • Mike Müller: “Parikh matrices” • Juhani Karhumäki: “k-abelian complexity of (k - 1)-abelian periodic words” • Aleksi Saarela: “k-abelian 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” (slides) • James Currie: “Avoidability problems”
3:15 p.m.	Coffee Break
3:30 p.m.	Tutorial: Narad Rampersad, “Pattern avoidance”, II (slides)
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” (slides) • 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” (slides) • Florin Manea, “Discovering hidden repetitions in words” (slides) • Eric Rowland, “p-automatic sequences and cellular automata” (slides)
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 Brlek-Reutenauer conjecture” • Antonio Restivo, “A new complexity measure for words” (slides)
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” (slides) • Hamoon Mousavi, “Repetition avoidance in circular factors” (slides)
12:30 p.m.	Lunch
2:15 p.m.	Contributed Talks Session 7: • Francine Blanchet-Sadri, “Strict bounds for pattern avoidance” (slides) • Joerg Endrullis, “Degrees of streams’ (slides)
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 (slides)
10:00 a.m	Contributed Talks Session 8: • Svetlana Puzynina, “Twins in words” (15 mins) (slides) • Émilie Charlier, “Self-shuffling words” (15 mins) (slides) • 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 (slides)
3:15 p.m.	Coffee Break
3:30 p.m.	Contributed Talks Session 9: • Michelangelo Bucci, “Palindromes in pure morphic words” (slides)
4:00 p.m.	Open Problems – Final Report on Progress
6:00 p.m.	Dinner (on your own)

 

Top