Finite Automata and Randomness

Abstract : 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [10 references]  Display  Hide  Download
Contributor : Hal Ifip <>
Submitted on : Friday, October 26, 2018 - 8:01:51 AM
Last modification on : Friday, October 26, 2018 - 8:05:05 AM
Long-term archiving on : Sunday, January 27, 2019 - 12:41:32 PM


 Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2021-01-01

Please log in to resquest access to the document


Distributed under a Creative Commons Attribution 4.0 International License



Ludwig Staiger. Finite Automata and Randomness. 20th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2018, Halifax, NS, Canada. pp.1-10, ⟨10.1007/978-3-319-94631-3_1⟩. ⟨hal-01905642⟩



Record views