April 10, Tuesday
12:00 – 14:00
On the subword complexity of k-automatic and k-context-free sequences
Computer Science seminar
Lecturer : Yossi Moshe
Affiliation : The Hebrew University Of Jerusalem
Location : 202/37
Host : Dr. Michael Elkin
Given a positive integer
$k$, a sequence
$A=(a_n)_{n=0}^{\infty}$ over a finite alphabet set
$\Omega$ is said to be
$k$-automatic if the
$n$th term of this sequence is generated by a finite state machine with
$n$ in base-
$k$ as an input. Those sequences occur in many different areas (such as number theory, combinatorics, computer graphics, ergodic theory, physics and even music). We begin with some background on the theory of automatic sequences. Then we study the subword complexity of those sequences and of some more general sequences which are defined in terms of context-free languages. In particular we consider a problem of Allouche and Shallit [1] on
$k$-context-free sequences.
J.-P. Allouche and J. O. Shallit, Automatic Sequences. Theory, Applications, Generalizations. Cambridge University Press, Cambridge, 2003.