zbMATH — the first resource for mathematics

Outputs in random $$f$$-ary recursive circuits. (English) Zbl 1259.94087
Summary: This paper extends the study of outputs for random recursive binary circuits in [T. Tsukiji and H. Mahmoud, Algorithmica 31, No. 3, 403–412 (2001; Zbl 0989.68107)]. We show via martingales that a suitably normalized version of the number of outputs in random $$f$$-ary recursive circuits converges in distribution to a normal random variable.
MSC:
 94C15 Applications of graph theory to circuits and networks 05C80 Random graphs (graph-theoretic aspects) 60G42 Martingales with discrete parameter 68W40 Analysis of algorithms