From finite automata to power series and back again

Christol's theorem links algebra in an unexpected way with a concept from computer sciences: a power series over a finite field is algebraic if and only if its coefficients are generated by a finite automaton. We examined the proof of Christol's theorem to find answers to the following two questions: Given a finite automaton with m states, what can we say about the algebraic degree of the corresponding power series? Conversely, given an algebraic power series of algebraic degree d, can we find a bound on the number of states of an automaton that generates the power series? In this thesis we explain Christol's theorem and the concept of finite automata, and give answers to the questions above.