# Automatic maps on the Gaussian integers

Automatic maps on the Gaussian integers

Author Contributor Faculty Department Programme Date2013-09-18

AbstractHow can you define automatic maps on the Gaussian integers? The two key components of an automatic map are an automaton, and a numeration system that represents every Gaussian integer at least once. We start by giving a brief introduction to automata and language theory, and go on to establish the existence of a numeration system for the Gaussian integers in every base. The literature is quite scarce on this latter subject, however, so we have to reproduce a referenced result that proved too hard to find. With the basic components covered, we define the concept of automatic maps, and show that it does not rely on the particular choice of numeration system in a given base. We then continue to prove that a map is automatic with respect to every multiplicatively dependent base, and show that there exist automatic maps that are not automatic in any multiplicatively independent base. Consequently, it reveals partly how an analogue of Cobham's deep theorem for the Gaussian integers will look like, and answers an open question in the literature negatively.

Subjectautomata

numeration systems

gaussian integers

automatic sequences

automatic maps

regular languages

radix systems

cobham

ring

http://resolver.tudelft.nl/uuid:7bec892b-9fc7-4349-bbbf-bbfd4c859f19

Part of collectionStudent theses

Document typemaster thesis

Rights(c) 2013 Krebs, T.J.P.