Finite Automata and Randomness Event as iCalendar

(Science Event Tags, Computer Science, Seminars)

04 April 2018

1 - 2pm

Venue: Building 303, G14

Location: City Campus

Host: Department of Computer Science

LudwigStaiger

Speaker: Prof. Ludwig Staiger, Martin-Luther-Universität Halle-Wittenberg, Germany

Abstract

There are three main approaches to define algorithmically random sequences, namely a) the measure-theoretic approach, b)  the unpredictability approach, and  c)  the incompressibility (or complexity-theoretic) approach.

The talk presents results obtained by using finite automata instead of Turing machines in the first two of the above mentioned approaches. Both approaches result in (different) automata-independent forms of randomness: disjunctivity and Borel normality.

Finally, using asymptotic subword complexity and finite-state dimension, we discuss a scale of relaxations of automata-theoretic randomness, their interrelations and connections to classical Hausdorff dimension.