7

[2207.14108] Short Synchronizing Words for Random Automata

 2 years ago
source link: https://arxiv.org/abs/2207.14108
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

[Submitted on 28 Jul 2022]

Short Synchronizing Words for Random Automata

Download PDF

We prove that a uniformly random automaton with n states on a 2-letter alphabet has a synchronizing word of length O(n^{1/2}\log n) with high probability (w.h.p.). That is to say, w.h.p. there exists a word \omega of such length, and a state v_0, such that \omega sends all states to v_0. Prior to this work, the best upper bound was the quasilinear bound O(n\log^3n) due to Nicaud (2016). The correct scaling exponent had been subject to various estimates by other authors between 0.5 and 0.56 based on numerical simulations, and our result confirms that the smallest one indeed gives a valid upper bound (with a log factor).
Our proof introduces the concept of w-trees, for a word w, that is, automata in which the w-transitions induce a (loop-rooted) tree. We prove a strong structure result that says that, w.h.p., a random automaton on n states is a w-tree for some word w of length at most (1+\epsilon)\log_2(n), for any \epsilon>0. The existence of the (random) word w is proved by the probabilistic method. This structure result is key to proving that a short synchronizing word exists.

Comments: 46 pages
Subjects: Formal Languages and Automata Theory (cs.FL); Discrete Mathematics (cs.DM); Combinatorics (math.CO); Probability (math.PR)
Cite as: arXiv:2207.14108 [cs.FL]
  (or arXiv:2207.14108v1 [cs.FL] for this version)
  https://doi.org/10.48550/arXiv.2207.14108

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK