Asymptotic behavior of the Shannon function for a class of circuits of functional elements.
The author investigates the particular case of so called transistor circuits of functional elements (c.f.e.) in which every functional element corresponds to some circuit with a single delay and implements the Boolean function which is everywhere determined. The transistor circuits of functional elements are constructed on the basis \(B(m)\) of all functional elements, every element has the complexity (weight) which is not more than m. The author considers Shannon's function \[ L_{B(m)} (n)\,=\,\max \min\, L(s), \] in which \(L(s)\) is the total weight of all functional elements of the circuit and which is minimized on the set of all c.f.e., implementing the Boolean function \(f\) of \(n\) variables, and is maximized on the set of all such functions \(f\). The major result is the asymptotic approximation of Shannon's function \[ L_{B(m)} (n)\,\sim \, 2^{n+1}/n, \] that does not depend on \(m\).
- Asymptotics of the Shannon function for switching circuits in the ``Sheffer stroke basis with partial unreliability
- The asymptotically best method for synthesizing limited-depth Boolean recursive schemes
- One approach to synthesizing predicate circuits on the basis of generalized variables
- Delay in networks of functional elements in a model with an arbitrary distribution of basis element input delays
- Refined bounds on Shannon's function for complexity of circuits of functional elements
- Asymptotic bounds of the Shannon function for a depth model of functional-element networks with capacity parameters for element outputs
- On asymptotic estimates of the complexity of circuit realization of languages
- Network delay in a model with inputs of functional elements
- On complexity of oriented contact circuits with limited out-degree
- scientific article; zbMATH DE number 5827847 (Why is no real title available?)
- scientific article; zbMATH DE number 3877096 (Why is no real title available?)
- scientific article; zbMATH DE number 3896833 (Why is no real title available?)
- Asymptotically Optimal Circuit for a Storage Access Function
- scientific article; zbMATH DE number 3257823 (Why is no real title available?)
- scientific article; zbMATH DE number 3422276 (Why is no real title available?)
This page was built for publication: Asymptotic behavior of the Shannon function for a class of circuits of functional elements.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1284339)
