MA6420 Algebraic Theory of Codes and Automata


Course Details

Automata and words: Descriptional complexity of finite state automaton, local languages, syntactic semigroups, tree automata, words, Fine-Wilf theorem.
Codes: Basics of coding, types of codes, test for codes, flower automaton, finite transducers for codes.
Shift spaces: Finite and infinite, sofic shifts, entropy, Perron-Frobenius theory, finite state codes, cellular automata, dynamical systems.

Course References:

Texts books:
1. J. Berstel, D. Perrin, C. Reutenauer, Codes and Automata, Cambridge University Press, 2010.
2. D. Lind, B. Marcus, An introduction to Symbolic Dynamics and Coding, Cambridge University Press, 1995.
References:
1. M. Ito, Algebraic theory of Automata and Formal Languages, Cambridge University Press, 2004.
2. M. Lothaire, Combinatorics on Words, Cambridge University Press, 1997.
3. A. Salomaa, G.Rozenberg, Handbook of Formal Languages (Vol I), Springer, 1997.
4. J-P. Allouche, J.Shallit, Automatic Sequences, Cambridge University Press, 2003.
5. S. Ginsberg, Algebraic and Automata-Theoretic Properties of Formal Languages, North Holland Publishing Co., 1975.
6. R. Tao, Finite Automata and Applications to Cryptography, Springer, 2009.