Fast synchronization of inhomogenous random automata

DOI10.1016/J.IC.2023.105129MaRDI QIDQ6178462zbMATH OpenFDO

Authors Balázs Gerencsér, Zsombor Várkonyi

Publication date 18 January 2024

Published in Information and Computation (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

fast synchronizationrandom deterministic automatatransitivity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: We examine the reset threshold of randomly generated deterministic automata. We claim that an automaton with a random mapping and two random permutation letters has a reset threshold of $$ with high probability. Our observation is motivated by the breakthrough of Nicaud in 2014 providing a near-linear bound in a similar case, among multiple other results. Recent numerical analyses have conjectured that the expected reset threshold is closer to $mathcalO(sqrtn)$ but not even a sublinear bound was confirmed for any variant.

Recommendations

• Synchronizing random automata
• scientific article; zbMATH DE number 6861928
• On the probability of being synchronizable
• On randomized generation of slowly synchronizing automata

Cites work

• A fast algorithm finding the shortest reset words
• An extremal problem for two families of sets
• An improvement to a recent upper bound for synchronizing words of finite automata
• Experimental study of the shortest reset word of random automata
• scientific article; zbMATH DE number 7228447 (Why is no real title available?)
• scientific article; zbMATH DE number 3222112 (Why is no real title available?)
• On randomized generation of slowly synchronizing automata
• On two Combinatorial Problems Arising from Automata Theory
• Synchronizing almost-group automata
• The action of a few permutations onr-tuples is quickly transitive
• The Cerny Conjecture Holds with High Probability
• The probability of generating the symmetric group

Cited in

(1)

• Short synchronizing words for random automata

This page was built for publication: Fast synchronization of inhomogenous random automata

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