The graph structure of a deterministic automaton chosen at random. Issue 3 (30th December 2016)

• Record Type: Journal Article
• Authors: Cai, Xing Shi; Devroye, Luc
• Is Part Of: Random structures & algorithms. Volume 51:Issue 3(2017)
• Page Start: 428
• Page End: 458
• Publication Date: 2016-12-30
• Subjects: random digraphs -- deterministic finite automaton; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20707
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: An n ‐state deterministic finite automaton over a k ‐letter alphabet can be seen as a digraph with n vertices which all have k labeled out‐arcs. Grusho (Publ Math Inst Hungarian Acad Sci 5 (1960), 17–61). proved that whp in a random k ‐out digraph there is a strongly connected component of linear size, i.e., a giant, and derived a central limit theorem. We show that whp the part outside the giant contains at most a few short cycles and mostly consists of tree‐like structures, and present a new proof of Grusho's theorem. Among other things, we pinpoint the phase transition for strong connectivity. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 51, 428–458, 2017