Finite Automata and Randomness

摘要

The lecture surveys approaches using finite automata to define several notions of (automata-theoretic) randomness. It focuses on the one hand on automata-theoretic randomness of infinite sequences in connection with automata-independent notions like disjunctivity and Borel normality. On the other hand it considers the scale of relaxations of randomness (Borel normality and disjunctivity), that is, finite-state dimension and subword complexity and their interrelations.