|
Circuits for disjunction admitting short unitary diagnostic tests
S. R. Bedzhanova
Abstract:
We study tests for circuits realising disjunction. In a circuit, the inversion fault is allowed at the output of precisely one functional element. For any functionally complete basis $B$ it is found that for any $n\ge3$ the disjunction of $n$ variables can be realised by a circuit over $B$ which admits a unitary diagnostic test consisting of at most two tuples. It is proved that this result cannot be improved in the general case.
Received: 15.04.2010
Citation:
S. R. Bedzhanova, “Circuits for disjunction admitting short unitary diagnostic tests”, Diskr. Mat., 22:4 (2010), 43–54; Discrete Math. Appl., 20:5-6 (2010), 643–654
Linking options:
https://www.mathnet.ru/eng/dm1118https://doi.org/10.4213/dm1118 https://www.mathnet.ru/eng/dm/v22/i4/p43
|
Statistics & downloads: |
Abstract page: | 495 | Full-text PDF : | 191 | References: | 38 | First page: | 13 |
|