The graph structure of a deterministic automaton chosen at random

DOI10.1002/RSA.20707MaRDI QIDQ5371142zbMATH OpenOpenAlexWikidataFDO

Authors Xing Shi Cai, Luc Devroye

Publication date 24 October 2017

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

deterministic finite automatonrandom digraphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Random graphs (graph-theoretic aspects) (05C80) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Formal languages and automata (68Q45)

Abstract: A deterministic finite automaton (DFA) of $n$ states over a $k$-letter alphabet can be seen as a digraph with $n$ vertices which all have exactly $k$ labeled out-arcs ($k$-out digraph). In 1973 Grusho first proved that with high probability (whp) in a random $k$-out digraph there is a strongly connected component (SCC) of linear size that is reachable from all vertices, i.e., a giant. He also proved that the size of the giant follows a central limit law. We show that whp the part outside the giant contains at most a few short cycles and mostly consists of overlapping tree-like structures. Thus the directed acyclic graph (DAG) of a random $k$-out digraph is almost the same as the digraph with the giant contracted into one vertex. These findings lead to a new, concise and self-contained proof of Grusho's theorem. This work also contains some other results including the structure outside the giant, the phase transition phenomenon in strong connectivity, the typical distance, and an extension to simple digraphs.

Recommendations

• Random deterministic automata
• Distribution of the number of accessible states in a random deterministic automaton
• scientific article; zbMATH DE number 777287
• The state complexity of random DFAs
• On the probability of being synchronizable

Cited in

(8)

• The diameter of the directed configuration model
• scientific article; zbMATH DE number 777287 (Why is no real title available?)
• The giant component of the directed configuration model revisited
• Lifts, derandomization, and diameters of Schreier graphs of Mealy automata
• Minimum stationary values of sparse random directed graphs
• Short synchronizing words for random automata
• Random deterministic automata with one added transition
• Diameter and stationary distribution of random r-out digraphs

This page was built for publication: The graph structure of a deterministic automaton chosen at random

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