Affordable Access

deepdyve-link
Publisher Website

Synchronizing Almost-Group Automata

Authors
  • Berlinkov, Mikhail
  • Nicaud, Cyril
Publication Date
Dec 01, 2020
Identifiers
DOI: 10.1142/S0129054120420058
OAI: oai:HAL:hal-03134003v1
Source
HAL-INRIA
Keywords
Language
English
License
Unknown
External links

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 (2<sup>k−1</sup>−1)/(n<sup>2(k−1)</sup>)*(1+o(1)), for a k-letter alphabet.

Report this publication

Statistics

Seen <100 times