Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/147847
Title: A STUDY OF RANDOMNESS AND GROUPS USING FINITE AUTOMATA
Authors: MOLDAGALIYEV BIRZHAN
Keywords: Algorithmic Randomness, Automatic Structures, Automata Theory
Issue Date: 9-May-2018
Citation: MOLDAGALIYEV BIRZHAN (2018-05-09). A STUDY OF RANDOMNESS AND GROUPS USING FINITE AUTOMATA. ScholarBank@NUS Repository.
Abstract: The thesis aims to study randomness and mathematical groups from automata-theoretic perspective. A general approach to study random objects is taken from Algorithmic Randomness, while that for groups is taken from Computable Model Theory. A study of randomness in this thesis proceeds in several directions. Firstly, automatic randomness tests are introduced as a measure-theoretic tool to detect randomness. Secondly, globally automatic supermartingales are introduced as predicting machines on infinite sequences. Thirdly, a notion of randomness is extended from infinite sequences to formal languages using automatic martingales which are locally automatic. Finally, we answer the open question on subword complexity, which asks if any real in the unit interval acts as a value for subword complexity. As for study of groups, it proceeds in two directions. Firstly, presentations of various Lamplighter groups using transducers are studied. Secondly, we investigate various mathematical structures with two-way finite automata recognisable presentations.
URI: http://scholarbank.nus.edu.sg/handle/10635/147847
Appears in Collections:Ph.D Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
MoldagaliyevB.pdf652.22 kBAdobe PDF

OPEN

NoneView/Download

Page view(s)

7
checked on Oct 18, 2018

Download(s)

2
checked on Oct 18, 2018

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.