Circular automata synchronize with high probability

Activity: Talk or presentation › Talk at conference or symposium › Science to science

Description

Pin proved in 1978 a circulant automaton with a prime number of states A(p,{a,b}) synchronize with probability exactly 1- (p!/p^p). We prove that circulant automata A(n,{a,b}) synchronize with probability 1 - O(1/n), where n is any natural number.
Period10 Jun 2019
Event titleSemigroups and Groups, Automata, Logics
Event typeConference
LocationCremona, ItalyShow on map
Degree of RecognitionInternational