Skip to Main content Skip to Navigation
Journal articles

Synchronizing Almost-Group Automata

Abstract : In this paper we address the question of synchronizing random automata in the critical settings of almost-group automata. Group automata are automata where all letters act as permutations on the set of states, and they are not synchronizing (unless they have one state). In almost-group automata, one of the letters acts as a permutation on n−1 states, and the others as permutations. We prove that this small change is enough for automata to become synchronizing with high probability. More precisely, we establish that the probability that a strongly connected almost-group automaton is not synchronizing is (2k−1−1)/(n2(k−1))*(1+o(1)), for a k-letter alphabet.
Document type :
Journal articles
Complete list of metadata
Contributor : Admin Upem Connect in order to contact the contributor
Submitted on : Monday, February 8, 2021 - 5:02:45 AM
Last modification on : Saturday, January 15, 2022 - 3:59:22 AM

Links full text



Mikhail Berlinkov, Cyril Nicaud. Synchronizing Almost-Group Automata. International Journal of Foundations of Computer Science, World Scientific Publishing, 2020, 31 (08), pp.1091-1112. ⟨10.1142/S0129054120420058⟩. ⟨hal-03134003⟩



Les métriques sont temporairement indisponibles