| |
Automatic Sequences
| Credits |
8 credit points |
| Instructors |
Bosma, W. (Radboud Universiteit Nijmegen), Fokkink, R.J. (Technische Universiteit Delft) |
| E-mail |
w.bosma@science.ru.nl, R.J.Fokkink@tudelft.nl |
| Aim |
This course is suitable for students of mathematics and theoretical computer science. The aim of this course is to obtain knowledge on a topic at the border of mathematics and computer science, about one of the simplest models of computation, using finite automata, and the "automatic sequences" that can be generated by them. There will be particular emphasis on aspects of elementary number theory, and the properties of numbers representated in various ways (such as binary expansion, continued fractions) by automatic sequences. What can be said, for example, about the connection between formal languages and digit properties of real numbers? |
| Description |
The course will follow the lines set out by the textbook (see below) of Allouche and Shallit. After an introduction on various aspects of words and representations of numbers, the main concepts of finite automata and transducers are presented, with their links in the theory of languages. Element n of an automatic sequence A is generated by following the arrows between a finite number of states with output, in an order determined by the representation of the index n. Various examples (such as the famous infinite Thue-Morse, Rudin-Shapiro and Fibonacci words) are studied in detail, with respect to subword frequency, complexity, and overlap, among others. Results on the transcendence of real automatic numbers and of elements of function fields over finite fields are derived. Various generalizations are also briefly considered. |
| Organization |
Weekly meetings will consist of a 75 minute lecture and a 60 minute problem/discussion session, approximately. At the rate of 1 chapter of about 25 pages a week, the student will be required to spend considerable time on reading and digesting the well-written text by himself, as well as on doing some homework problems.
|
| Examination |
There will be a written exam. Together with the average grade for homework handed in, this will determine the end grade (on a 50-50 base). |
| Literature |
The lectures will be largely based on Jean Paul Allouche, Jeffrey Shallit: Automatic sequences; theory, applications, generalizations. Cambridge University Press, 2003. |
| Remarks |
Elementary number theory required, familiarity with regular languages and algebra is useful. |
|
