April 2009 May 2009 June 2009 Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa 1 2 3 4 1 2 1 2 3 4 5 6 5 6 7 8 9 10 11 3 4 5 6 7 8 9 7 8 9 10 11 12 13 12 13 14 15 16 17 18 10 11 12 13 14 15 16 14 15 16 17 18 19 20 19 20 21 22 23 24 25 17 18 19 20 21 22 23 21 22 23 24 25 26 27 26 27 28 29 30 24 25 26 27 28 29 30 28 29 30 31 |

4:00 pm Friday, May 1, 2009 ERGODIC THEORY SEMINAR: To Be AnnouncedOn Uniformly Recurrent Morphic Sequencesby Yuri PritykinPrinceton University (Princeton University) in HB227 (Tea served at 3:30 HB438)- A sequence over a finite alphabet is uniformly recurrent if every its subword occurs infinitely many times with bounded distances between consecutive occurrences. A pure morphic sequence is a right-infinite, symbolic sequence obtained by iterating a letter-to-word substitution. For instance, the Fibonacci sequence and the Thue-Morse sequence, which play important role in theoretical computer science, are pure morphic. Define a coding as a letter-to-letter substitution. The image of a pure morphic sequence under a coding is called a morphic sequence. We start from the problem of deciding whether a given morphic sequence is uniformly recurrent. Although the status of the problem remains open, we show some evidence for its decidability: in particular, we prove that it can be solved in polynomial time on pure morphic sequences and on automatic sequences. In addition, we prove that the complexity of every uniformly recurrent, morphic sequence has at most linear growth: here, complexity is understood as the function that maps each positive integer n to the number of distinct n-length subwords occurring in the sequence. (joint work with Francois Nicolas)
Submitted by maxine@rice.edu |