Geodesic
On the relationship between diagnostic and checking tests of the read-once functions
Diskretnaya Matematika, Tome 23 (2011) no. 1, pp. 46-50.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DM_2011_23_1_a3,
     author = {D. V. Chistikov},
     title = {On the relationship between diagnostic and checking tests of the read-once functions},
     journal = {Diskretnaya Matematika},
     pages = {46--50},
     publisher = {mathdoc},
     volume = {23},
     number = {1},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2011_23_1_a3/}
}
TY  - JOUR
AU  - D. V. Chistikov
TI  - On the relationship between diagnostic and checking tests of the read-once functions
JO  - Diskretnaya Matematika
PY  - 2011
SP  - 46
EP  - 50
VL  - 23
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2011_23_1_a3/
LA  - ru
ID  - DM_2011_23_1_a3
ER  - 
%0 Journal Article
%A D. V. Chistikov
%T On the relationship between diagnostic and checking tests of the read-once functions
%J Diskretnaya Matematika
%D 2011
%P 46-50
%V 23
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2011_23_1_a3/
%G ru
%F DM_2011_23_1_a3
D. V. Chistikov. On the relationship between diagnostic and checking tests of the read-once functions. Diskretnaya Matematika, Tome 23 (2011) no. 1, pp. 46-50. http://geodesic.mathdoc.fr/item/DM_2011_23_1_a3/

[1] Angluin D., Hellerstein L., Karpinski M., “Learning read-once functions with queries”, J. ASM, 40 (1993), 185–210 | MR | Zbl

[2] Angluin D., “Queries and concept learning”, Machine Learning, 2 (1987), 319–342

[3] Bshouty N. H., Hancock T. R., Hellerstein L., “Learning Boolean read-once formulas over generalized bases”, J. Comput. Syst. Sci., 50:3 (1995), 521–542 | DOI | MR | Zbl

[4] Valiant L. G., “A theory of the learnable”, Comm. ACM, 27 (1984), 1134–1142 | DOI | Zbl

[5] Voronenko A. A., Chistikov D. V., “Rasshifrovka bespovtornykh funktsii orakulom – schetchikom chetnosti”, Prikladnaya matematika i informatika, 34, 2010, 93–106

[6] Voronenko A. A., “O zadachakh globalnogo testirovaniya (rasshifrovki) bespovtornykh bulevykh funktsii”, Materialy III Rossiiskoi shkoly-seminara “Cintaksis i semantika logicheskikh sistem”, Izd-vo GOU VPO “Vostochno-Sibirskaya gosudarstvennaya akademiya obrazovaniya”, Irkutsk, 2010, 17–22

[7] Voronenko A. A., “O proveryayuschikh testakh dlya bespovtornykh funktsii”, Matematicheskie voprosy kibernetiki, 11, 2002, 163–176 | MR | Zbl

[8] Voronenko A. A., “Raspoznavanie bespovtornosti v proizvolnom bazise”, Prikladnaya matematika i informatika, 23, 2006, 67–84

[9] Voronenko A. A., Chistikov D. V., “O testirovanii bespovtornykh bulevykh funktsii v bazise $B_5$”, Materialy XVII Mezhdunarodnoi shkoly-seminara “Sintez i slozhnost upravlyayuschikh sistem”, IMSO RAN, Novosibirsk, 2008, 24–30