Synchronizing random almost-group automata

DOI10.1007/978-3-319-94812-6_8MaRDI QIDQ1616960zbMATH OpenOpenAlexFDO

Authors Mikhail V. Berlinkov, Cyril Nicaud

Publication date 7 November 2018

Full work available at URL https://arxiv.org/abs/1805.02154

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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 $frac{2}^{k-1}-1n^{2(k-1)}(1+o(1))$, for a $k$-letter alphabet.

Recommendations

• Synchronizing almost-group automata
• On the probability of being synchronizable
• Groups synchronizing a transformation of non-uniform kernel
• Synchronizing random automata on a 4-letter alphabet
• Synchronizing random automata

Cited in

(8)

• On two problems of almost synchronizing groups
• Circular automata synchronize with high probability
• Synchronizing groups and automata
• Dixon's theorem and random synchronization
• Groups synchronizing a transformation of non-uniform kernel
• scientific article; zbMATH DE number 6861928 (Why is no real title available?)
• Synchronizing almost-group automata
• Short synchronizing words for random automata

This page was built for publication: Synchronizing random almost-group automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1616960)