Internship supervised by Mika Hirvensalo at the University of Turku, during summer 2016.
This internship leaded to a paper, accepted at LATA2017 conference.
Abstract
In this report we investigate the computational power of affine automaton, a computational model recently introduced in [DY16]. First, we compare it to better known deterministic models. In particular we present a logarithmic-space language that is not recognized by some affine automata. Then, we present some stability results of functions and languages generated by affine automata. And finally we try to find some equivalent but simpler models in order to understand better the origin of the power of affine models.
