×

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
PDF BibTeX XML Cite