Implementation of Boolean functions with a bounded number of zeros by disjunctive normal forms

Yu. V. Maximov

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 53 (2013) no. 9, pp. 1569-1588

Résumé

The problem of constructing simple disjunctive normal forms (DNFs) of Boolean functions with a small number of zeros is considered. The problem is of interest in the complexity analysis of Boolean functions and in its applications to data analysis. The method used is a further development of the reduction approach to the construction of DNFs of Boolean functions. A key idea of the reduction method is that a Boolean function is represented as a disjunction of Boolean functions with fewer zeros. In a number of practically important cases, this technique makes it possible to considerably reduce the complexity of DNF implementations of Boolean functions.

Bibliographie

[1] Zhuravlev Yu. I., “Ob algebraicheskom podkhode k resheniyu zadach raspoznavaniya ili klassifikatsii”, Probl. kibernetiki, 1978, no. 33, 5–68 | Zbl

[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 | DOI | Zbl

[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 | MR | Zbl

[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 | MR

[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 | MR

[7] Mubayi D., Turan G., Zhao Y., “The DNF exception problem”, Theoret. Comput. Sci., 352:1–3 (2006), 85–96 | DOI | MR | Zbl

[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 | MR

[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 | DOI | MR | Zbl

[11] Maksimov Yu. V., “Sravnitelnyi analiz slozhnosti bulevykh funktsii s malym chislom nulei”, Dokl. AN, 447:6 (2012), 607–609 | MR

[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 | MR

[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 | MR

[14] Dyakonov A. G., “Postroenie diz'yunktivnykh normalnykh form v logicheskikh algoritmakh raspoznavaniya”, Zh. vychisl. matem. i matem. fiz., 42:12 (2002), 1899–1907 | MR

[15] Dyakonov A. G., “Postroenie DNF posledovatelnym peremnozheniem”, Zh. vychisl. matem. i matem. fiz., 43:10 (2003), 1589–1600 | MR

[16] Yudaev P. V., “Sravnenie dvukh algoritmov uproscheniya diz'yunktivnykh normalnykh form”, Zh. vychisl. matem. i matem. fiz., 26:10 (2003), 1552–1558

[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 | DOI

[18] Romanov M. Yu., “Maximal faces of Boolean functions with a small number of zeroes”, Pat. Recogn. Image Analys., 20:4 (2010), 474–478 | DOI | MR

[19] Zhuravlev Yu. I., “O razlichnykh ponyatiyakh minimalnosti diz'yunktivnykh normalnykh form”, Sib. matem. zhurnal, 1:4 (1960), 609–610 | Zbl

[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 | MR

[22] Veber K., “O razlichnykh ponyatiyakh minimalnosti diz'yunktivnykh normalnykh form”, Probl. kibernetiki, 1979, no. 36, 129–158 | MR | Zbl

[23] Nigmatullin R. G., “Variatsionnyi printsip v algebre logiki”, Diskretnyi analiz, 1967, no. 10, 69–89 | MR | Zbl

[24] Pippenger N., “The shortes disjunctive normal form of a random Boolean function”, Random Struct. Algorithms, 22:2 (2003), 161–186 | DOI | MR | Zbl

[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 | MR | Zbl

[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 | MR | Zbl

[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 | MR | Zbl

[29] Korshunov A. D., “O slozhnosti kratchaishikh diz'yunktivnykh normalnykh form sluchainykh bulevykh funktsii”, Metody diskretnogo analiza, 40 (1983), 25–83 | MR

[30] Andreev A. E., “O sinteze diz'yunktivnykh normalnykh form blizkikh k minimalnym”, Dokl. AN SSSR, 269:1 (1983), 11–15 | MR | Zbl

[31] Korshunov A. D., “Slozhnost vychislenii bulevykh funktsii”, Uspekhi matem. nauk, 67:1 (2009), 97–168 | DOI | MR

[32] Nurlynbaev A. N., “Ob uproschenii bulevykh funktsii s mnozhestvom nulei spetsialnogo vida”, Diskretnaya matem., 3:1 (1991), 88–97 | MR

[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 | DOI | MR | Zbl

[35] Maksimov Yu. V., “Prostye diz'yunktivnye normalnye formy bulevykh funktsii s ogranichennym chislom nulei”, Dokl. AN, 445:2 (2012), 143–145 | MR

[36] Zhuravlev Yu. I., “Ob algoritmakh raspoznavaniya s predstavitelnymi naborami (o logicheskikh algoritmakh)”, Zh. vychisl. matem. i matem. fiz., 42:9 (2002), 1425–1435 | MR | Zbl

[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 | MR | Zbl

[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 | MR | Zbl

[39] Matrosov V. L., “Korrektnye algebry ogranichennoi emkosti nad mnozhestvom algoritmov vychisleniya otsenok”, Zh. vychisl. matem. i matem. fiz., 21:5 (1981), 1276–1291 | MR | Zbl

[40] Board R., Pitt L., “On the necessity of Occam algorithms”, Theoret. Comput. Sci., 100 (1992), 157–184 | DOI | MR | Zbl

[41] Li M., Tromp J., Vitnyi P., “Sharpening Occam's razor”, Inf. Proc. Lett., 85 (2003), 267–274 | DOI | MR | Zbl