Circular automata synchronize with high probability

  • Abraham Gutierrez Sanchez (Speaker)

Activity: Talk or presentationTalk at conference or symposiumScience to science


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