|
Diskretnyi Analiz i Issledovanie Operatsii, 2010, Volume 17, Issue 6, Pages 68–76
(Mi da631)
|
|
|
|
This article is cited in 2 scientific papers (total in 2 papers)
A lower bound for the complexity of generalized parallel-serial contact circuits for a characteristic function of divisibility by $q$
K. L. Rychkov S. L. Sobolev Institute of Mathematics, SB RAS, Novosibirsk, Russia
Abstract:
We consider generalization of the concept of a parallel-serial contact circuit in the case when the variables assigned to contacts can take not two as in the Boolean case but a greater number of values. The conductivity of contacts as well as in the Boolean case remains two-valued (a contact is either close or break). We obtain a lower bound for the complexity of such circuits computing the characteristic function of divisibility by $q$, i.e., the function $\varphi_q\colon\{0,1,\dots,q-1\}^n\to\{0,1\}$ which is equal to 1 if the sum of values of its variables is divided by $q$. Bibliogr. 6.
Keywords:
Boolean function, contact circuit, complexity of circuits.
Received: 26.06.2010
Citation:
K. L. Rychkov, “A lower bound for the complexity of generalized parallel-serial contact circuits for a characteristic function of divisibility by $q$”, Diskretn. Anal. Issled. Oper., 17:6 (2010), 68–76
Linking options:
https://www.mathnet.ru/eng/da631 https://www.mathnet.ru/eng/da/v17/i6/p68
|
Statistics & downloads: |
Abstract page: | 329 | Full-text PDF : | 70 | References: | 53 | First page: | 3 |
|