Everts, A.R.F. (2012) From finite automata to power series and back again. Master's Thesis / Essay, Mathematics.
|
Text
MasterScriptieAnneroosEverts.pdf - Published Version Download (515kB) | Preview |
|
![[img]](https://fse.studenttheses.ub.rug.nl/style/images/fileicons/text.png) |
Text
AkkoordJTop.pdf - Other Restricted to Registered users only Download (32kB) |
Abstract
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.
| Item Type: | Thesis (Master's Thesis / Essay) |
|---|---|
| Degree programme: | Mathematics |
| Thesis type: | Master's Thesis / Essay |
| Language: | English |
| Date Deposited: | 15 Feb 2018 07:47 |
| Last Modified: | 15 Feb 2018 07:47 |
| URI: | https://fse.studenttheses.ub.rug.nl/id/eprint/9940 |
Actions (login required)
 |
View Item |