Javascript must be enabled for the correct page display

From finite automata to power series and back again

Everts, A.R.F. (2012) From finite automata to power series and back again. Master's Thesis / Essay, Mathematics.

[img]
Preview
Text
MasterScriptieAnneroosEverts.pdf - Published Version

Download (515kB) | Preview
[img] Text
AkkoordJTop.pdf - Other
Restricted to Repository staff 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: http://fse.studenttheses.ub.rug.nl/id/eprint/9940

Actions (login required)

View Item View Item