×

zbMATH — the first resource for mathematics

A limit law for outputs in random recursive circuits. (English) Zbl 0989.68107
Summary: We study the structure of uniform random binary recursive circuits. We show that a suitably normalized version of the number of outputs converges in distribution to a normal random variate. We also discuss the connection of the number of outputs to a non-classical urn model, and our investigation provides a first solved instance of this new class of urns.

MSC:
68R10 Graph theory (including graph drawing) in computer science
68W35 Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.)
PDF BibTeX XML Cite
Full Text: DOI