|
Diskretnyi Analiz i Issledovanie Operatsii, 2009, Volume 16, Issue 5, Pages 78–87
(Mi da589)
|
|
|
|
This article is cited in 4 scientific papers (total in 4 papers)
On the complexity of generalized contact circuits
K. L. Rychkov S. L. Sobolev Institute of Mathematics, SB RAS, Novosibirsk, Russia
Abstract:
We consider generalizations of the concepts of a contact circuit and a parallel-serial contact circuit in the case when the variables assigned to contacts can accept not two as in a Boolean case, but a greater number of values. The conductivity of contacts as well as in a Boolean case remains two-valued (a contact either will close, or will break). We have obtained upper and lower bounds on the complexity of such circuits computing a function $f\colon\{0,1,\dots,q-1\}^n\to\{0,1\}$ which accepts the value 1 at a vector $(\delta_1,\dots,\delta_n)\in\{0,1,\dots,q-1\}^n$ if $\delta_1+\dots+\delta_n\neq0\pmod q$. Bibl. 9.
Keywords:
Boolean function, contact circuit, complexity of circuits.
Received: 05.06.2009
Citation:
K. L. Rychkov, “On the complexity of generalized contact circuits”, Diskretn. Anal. Issled. Oper., 16:5 (2009), 78–87
Linking options:
https://www.mathnet.ru/eng/da589 https://www.mathnet.ru/eng/da/v16/i5/p78
|
Statistics & downloads: |
Abstract page: | 433 | Full-text PDF : | 106 | References: | 55 | First page: | 3 |
|