RUS  ENG
Full version
JOURNALS // Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki
Zh. Vychisl. Mat. Mat. Fiz., 2013, Volume 53, Number 9, Pages 1569–1588 (Mi zvmmf9922)
Implementation of Boolean functions with a bounded number of zeros by disjunctive normal forms
Yu. V. Maximov

References
1. Zhuravlev Yu. I., “Ob algebraicheskom podkhode k resheniyu zadach raspoznavaniya ili klassifikatsii”, Probl. kibernetiki, 1978, no. 33, 5–68  zmath
2. Zhuravlev Yu. I., Ryazanov V. V., Senko O. V., “Raspoznavanie”. Matematicheskie metody. Programmnaya sistema. Prakticheskie primeneniya, Fazis, M., 2006
3. Valiant L. G., “A theory of learnable”, Communications of ACM, 27:11 (1984), 1134–1142  crossref  zmath  isi
4. Zhuravlev Yu. I., Kogan A. Yu., “Realizatsiya bulevykh funktsii s malym chislom nulei diz'yunktivnymi normalnymi formami i smezhnye zadachi”, Dokl. AN SSSR, 285:4 (1985), 795–799  mathnet  mathscinet  zmath
5. Zhuravlev Yu. I., Kogan A. Yu., “Algoritm postroeniya diz'yunktivnoi normalnoi formy, ekvivalentnoi proizvedeniyu levykh chastei bulevykh uravnenii nelsonovskogo tipa”, Zh. vychisl. matem. i matem. fiz., 26:8 (1986), 1243–1249  mathnet  mathscinet
6. Kogan A. Yu., “O diz'yunktivnykh normalnykh formakh bulevykh funktsii s malym chislom nulei”, Zh. vychisl. matem. i matem. fiz., 27:6 (1987), 924–931  mathnet  mathscinet
7. Mubayi D., Turan G., Zhao Y., “The DNF exception problem”, Theoret. Comput. Sci., 352:1–3 (2006), 85–96  crossref  mathscinet  zmath  isi
8. Umans C., “The minimum equivalent DNF problem and shortest implicants”, 39th Annual Symposium on Foundations of Computer Science (1998), 556–563
9. Umans C., “Hardness of approximating $\Sigma_2^p$ minimization problems”, 40th Annual Symposium on Foundations of Computer Science (1999), 465–475  mathscinet
10. Feldman V., “Hardness of approximate two-level logic minimization and PAC learning with membership queries”, J. Comput. System. Sci., 75:1 (2009), 13–26  crossref  mathscinet  zmath  adsnasa  isi
11. Maksimov Yu. V., “Sravnitelnyi analiz slozhnosti bulevykh funktsii s malym chislom nulei”, Dokl. AN, 447:6 (2012), 607–609  mathscinet
12. Dyakonov A. G., “Realizatsiya odnogo klassa bulevykh funktsii s malym chislom nulei tupikovymi diz'yunktivnymi normalnymi formami”, Zh. vychisl. matem. i matem. fiz., 41:5 (2001), 828–835  mathnet  mathscinet
13. Dyakonov A. G., “Testovyi podkhod k realizatsii diz'yunktivnymi normalnymi formami bulevykh funktsii s malym chislom nulei”, Zh. vychisl. matem. i matem. fiz., 42:6 (2002), 924–928  mathnet  mathscinet
14. Dyakonov A. G., “Postroenie diz'yunktivnykh normalnykh form v logicheskikh algoritmakh raspoznavaniya”, Zh. vychisl. matem. i matem. fiz., 42:12 (2002), 1899–1907  mathnet  mathscinet
15. Dyakonov A. G., “Postroenie DNF posledovatelnym peremnozheniem”, Zh. vychisl. matem. i matem. fiz., 43:10 (2003), 1589–1600  mathnet  mathscinet
16. Yudaev P. V., “Sravnenie dvukh algoritmov uproscheniya diz'yunktivnykh normalnykh form”, Zh. vychisl. matem. i matem. fiz., 26:10 (2003), 1552–1558  mathnet
17. Romanov M. Yu., “Efficient construction of DNF for some boolean functions with a small number of zeros”, Pat. Recogn. Image Analys., 21:4 (2011), 649–651  crossref
18. Romanov M. Yu., “Maximal faces of Boolean functions with a small number of zeroes”, Pat. Recogn. Image Analys., 20:4 (2010), 474–478  crossref  mathscinet
19. Zhuravlev Yu. I., “O razlichnykh ponyatiyakh minimalnosti diz'yunktivnykh normalnykh form”, Sib. matem. zhurnal, 1:4 (1960), 609–610  mathnet  zmath
20. Lin Syan-Lyan, “O sravnenii slozhnosti minimalnykh i kratchaishikh diz'yunktivnykh normalnykh form dlya funktsii algebry logiki”, Probl. kibernetiki, 18 (1967), 11–44
21. Sapozhenko A. A., Chukhrov I. P., “Minimizatsiya bulevykh funktsii v klasse diz'yunktivnykh normalnykh form”, Itogi nauki i tekhn. Ser. Teor. veroyatn. Matem. Stat. Teor. Kibernet., 25, VINITI, 1987, 68–116  mathnet  mathscinet
22. Veber K., “O razlichnykh ponyatiyakh minimalnosti diz'yunktivnykh normalnykh form”, Probl. kibernetiki, 1979, no. 36, 129–158  mathscinet  zmath
23. Nigmatullin R. G., “Variatsionnyi printsip v algebre logiki”, Diskretnyi analiz, 1967, no. 10, 69–89  mathscinet  zmath
24. Pippenger N., “The shortes disjunctive normal form of a random Boolean function”, Random Struct. Algorithms, 22:2 (2003), 161–186  crossref  mathscinet  zmath  isi
25. Glagolev V. V., “Otsenka slozhnosti sokraschennoi diz'yunktivnoi normalnoi formy dlya pochti vsekh funktsii algebry logiki”, Dokl. AN SSSR, 158:4 (1964), 770–773  mathnet  mathscinet  zmath
26. Kuznetsov S. E., “O nizhnei otsenke dliny kratchaishei d.n.f. pochti vsekh bulevykh funktsii”, Veroyatnostnye metody i kibernetika, 1983, no. 19, 44–47  mathscinet  zmath
27. Korshunov A. D., “Verkhnyaya otsenka slozhnosti kratchaishikh d.n.f. pochti vsekh bulevykh funktsii”, Kibernetika, 1969, no. 6, 1–8
28. Korshunov A. D., “O slozhnosti kratchaishikh diz'yunktivnykh normalnykh form bulevykh funktsii”, Metody diskretnogo analiza, 37 (1981), 9–41  mathscinet  zmath
29. Korshunov A. D., “O slozhnosti kratchaishikh diz'yunktivnykh normalnykh form sluchainykh bulevykh funktsii”, Metody diskretnogo analiza, 40 (1983), 25–83  mathscinet
30. Andreev A. E., “O sinteze diz'yunktivnykh normalnykh form blizkikh k minimalnym”, Dokl. AN SSSR, 269:1 (1983), 11–15  mathnet  mathscinet  zmath
31. Korshunov A. D., “Slozhnost vychislenii bulevykh funktsii”, Uspekhi matem. nauk, 67:1 (2009), 97–168  mathnet  crossref  mathscinet
32. Nurlynbaev A. N., “Ob uproschenii bulevykh funktsii s mnozhestvom nulei spetsialnogo vida”, Diskretnaya matem., 3:1 (1991), 88–97  mathnet  mathscinet
33. Lupanov O. B., Asimptoticheskie otsenki slozhnosti upravlyayuschikh sistem, Izd-vo MGU, M., 1984
34. Raab M., Steger A., “Balls into bins — a simple and tight analysis”, Lect. Notes In Comput. Sci., 1518, 1998, 159–170  crossref  mathscinet  zmath
35. Maksimov Yu. V., “Prostye diz'yunktivnye normalnye formy bulevykh funktsii s ogranichennym chislom nulei”, Dokl. AN, 445:2 (2012), 143–145  mathscinet
36. Zhuravlev Yu. I., “Ob algoritmakh raspoznavaniya s predstavitelnymi naborami (o logicheskikh algoritmakh)”, Zh. vychisl. matem. i matem. fiz., 42:9 (2002), 1425–1435  mathnet  mathscinet  zmath
37. Dyukova E. V., Zhuravlev Yu. I., “Diskretnyi analiz priznakovykh opisanii v zadachakh raspoznavaniya bolshoi razmernosti”, Zh. vychisl. matem. i matem. fiz., 40:8 (2000), 1264–1278  mathnet  mathscinet  zmath
38. Dyukova E. V., Zhuravlev Yu. I., Rudakov K. V., “Ob algebro-logicheskom sinteze korrektnykh protsedur raspoznavaniya na baze elementarnykh algoritmov”, Zh. vychisl. matem. i matem. fiz., 36:8 (1996), 215–223  mathnet  mathscinet  zmath
39. Matrosov V. L., “Korrektnye algebry ogranichennoi emkosti nad mnozhestvom algoritmov vychisleniya otsenok”, Zh. vychisl. matem. i matem. fiz., 21:5 (1981), 1276–1291  mathnet  mathscinet  zmath
40. Board R., Pitt L., “On the necessity of Occam algorithms”, Theoret. Comput. Sci., 100 (1992), 157–184  crossref  mathscinet  zmath  isi
41. Li M., Tromp J., Vitnyi P., “Sharpening Occam's razor”, Inf. Proc. Lett., 85 (2003), 267–274  crossref  mathscinet  zmath

© Steklov Math. Inst. of RAS, 2026