Geodesic
Using relevance queries for identification of read-once functions
Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part IV, Tome 402 (2012), pp. 183-217 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

A Boolean function is called read-once if it can be expressed by a formula over $\{\land,\lor,\neg\}$ where no variable appears more than once. The problem of identifying an unknown read-once function $f$ depending on a known set of variables $x_1,\dots,x_n$ by making queries is considered. Algorithms are allowed to perform standard membership queries and queries of two special types, allowing to reveal the relevance of variables to projections of $f$. Two exact identification algorithms are developed: one makes $O(n^2)$ yes–no queries, and the other makes $O(n\log^2n)$ queries with logarithmically long answers. Information-theoretic lower bound on the number of bits transferred from oracles to identification algorithms in the worst case is $\Omega(n\log n)$. 
@article{ZNSL_2012_402_a10,
     author = {D. V. Chistikov},
     title = {Using relevance queries for identification of read-once functions},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {183--217},
     year = {2012},
     volume = {402},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2012_402_a10/}
}
TY  - JOUR
AU  - D. V. Chistikov
TI  - Using relevance queries for identification of read-once functions
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2012
SP  - 183
EP  - 217
VL  - 402
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2012_402_a10/
LA  - ru
ID  - ZNSL_2012_402_a10
ER  - 
%0 Journal Article
%A D. V. Chistikov
%T Using relevance queries for identification of read-once functions
%J Zapiski Nauchnykh Seminarov POMI
%D 2012
%P 183-217
%V 402
%U http://geodesic.mathdoc.fr/item/ZNSL_2012_402_a10/
%G ru
%F ZNSL_2012_402_a10
D. V. Chistikov. Using relevance queries for identification of read-once functions. Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part IV, Tome 402 (2012), pp. 183-217. http://geodesic.mathdoc.fr/item/ZNSL_2012_402_a10/

[1] A. V. Akho, D. E. Khopkroft, D. D. Ulman, Struktury dannykh i algoritmy, Vilyams, M., 2007, 400 pp.

[2] A. A. Voronenko, “O zadachakh globalnogo testirovaniya (rasshifrovki) bespovtornykh bulevykh funktsii”, Sintaksis i semantika logicheskikh sistem, Materialy 3-i Rossiiskoi shkoly-seminara, Izd-vo Vostochno-Sibirskoi gosudarstvennoi akademii obrazovaniya, Irkutsk, 2010, 17–22

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

[4] A. A. Voronenko, D. V. Chistikov, “Learning read-once functions using subcube parity queries”, Computational Mathematics and Modeling, 22:1 (2011), 81–91 | DOI | Zbl

[5] V. A. Gurvich, “O bespovtornykh bulevykh funktsiyakh”, Usp. matem. nauk, 32:1 (1977), 183–184 | MR | Zbl

[6] V. A. Stetsenko, “On almost bad Boolean bases”, Theor. Comput. Sci., 136:2 (1994), 419–469 | DOI | MR | MR | Zbl

[7] B. A. Subbotovskaya, “O sravnenii bazisov pri realizatsii funktsii algebry logiki formulami”, Dokl. AN SSSR, 149:4 (1963), 784–787 | Zbl

[8] D. V. Chistikov, “Rasshifrovka bespovtornykh funktsii po dvum mladshim bitam chisla edinits podfunktsii”, Sintaksis i semantika logicheskikh sistem, Materialy 3-i Rossiiskoi shkoly-seminara, Izd-vo Vostochno-Sibirskoi gosudarstvennoi akademii obrazovaniya, Irkutsk, 2010, 114–118

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

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

[11] D. V. Chistikov, “Checking tests for read-once functions over arbitrary bases”, Proc. CSR 2012, Lecture Notes in Computer Science, 7353, 2012, 52–63 | DOI | MR | Zbl

[12] M. Karchmer, N. Linial, I. Newman, M. Saks, A. Widgerson, “Combinatorial characterization of read-once formulae”, Discrete Mathematics, 114:1–3 (1993), 275–282 | DOI | MR | Zbl

[13] P. Savicky, A. R. Woods, “The number of Boolean functions computed by formulas of a given size”, Random Structures and Algorithms, 13:3–4, Proc. of the Eighth International Conference (1998), 349–382 | 3.0.CO;2-V class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

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