Karp, R. M. Functional decomposition and switching circuit design. (English) Zbl 0135.38802 J. Soc. Ind. Appl. Math. 11, 291-335 (1963). The author investigates, how a given function of finite-valued variables can be successively composed from more elementary ones that are partly prescribed or restricted as far as their ranges are concerned. The problem is solved for some special cases, e. g. for the case that each variable (from both the original independent variables and the intermediate functions) occurs only in one function (so called disjoint treelike decompositions). In the second part of the paper, applications to (multi-level) circuit synthesis are discussed; this part is closely related to H. A. Curtis [J. Assoc. Comput. Mach. 8, 484–496 (1961; Zbl 0103.34603)]. The present article brings new results as well as a review of about ten other ones and is supplied with a lot of examples. It was written before the monograph [H. A. Curtis, A new approach to the design of switching circuits. Princeton, New Jersey: D. Van Nostrand company (1962)] has appeared. Reviewer: J. Hořejš Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page Cited in 2 Documents MSC: 94C11 Switching theory, applications of Boolean algebras to circuits and networks 94C30 Applications of design theory to circuits and networks Keywords:switching circuit design Citations:Zbl 0103.34603 PDFBibTeX XMLCite \textit{R. M. Karp}, J. Soc. Ind. Appl. Math. 11, 291--335 (1963; Zbl 0135.38802) Full Text: DOI