This article is cited in 2 papers

On the relationship between diagnostic and checking tests of the read-once functions

D. V. Chistikov


Abstract: We consider the problem of construction of a conditional diagnostic test for the read-once functions in an arbitrary basis with the use of queries of values of function at a point and queries to check an arbitrary subfunction for an identical equality to a constant. We show a connection of this problem to the checking test and prove its polynomial solvability for a wide class of Boolean functions.

UDC: 512.7

Received: 15.11.2010

DOI: 10.4213/dm1129

 English version: Discrete Mathematics and Applications, 2011, 21:2, 203–208

Bibliographic databases:

• 
• 
•