APPLIED MATH SEMINAR

Speaker: Jacques Peyriere, University of Paris-Sud (Orsay)

Title: Automatic and substitutive sequences; applications

When/where: Tuesday, February 1st, 4:15 PM, AKW 200

Abstract:
Substitutive sequences are obtained by iterating a morphism of free monoid of finite type. They are sequences with a complexity immediately higher than the complexity of periodic sequences. For example, the well known Thue-Morse sequence is obtained in the following way: we start with the single letter a and iterate the operation consisting in replacing a by ab and b by ba; we get, a, ab, abba, abbabaab, and so on. This defines an infinite sequence of letters a and b. The so obtained sequences are the substitutive sequences. These sequences  are of low complexity: the number of subwords of length n grows slower than n squared (in contrast to a random sequence). Applications in particular to condensed matter physics and optics are presented.