Asymptotic estimates for the number of solutions of the dualization problem and its generalizations

E. V. Djukova   ; R. M. Sotnezov

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 51 (2011) no. 8, pp. 1531-1540

Résumé

Asymptotic estimates for the typical number of irreducible coverings and the typical length of an irreducible covering of a Boolean matrix are obtained in the case when the number $m$ of rows is no less than the number $n$ of columns. As a consequence, asymptotic estimates are obtained for the typical number of maximal conjunctions and the typical rank of a maximal conjunction of a monotone Boolean function of $n$ variables defined by a conjunctive normal form of $m$ clauses. Similar estimates are given for the number of irredundant coverings and the length of an irredundant covering of an integer matrix (for the number of maximal conjunctions and the rank of a maximal conjunction of a two-valued logical function defined by its zero set). Results obtained previously in this area are overviewed.

Bibliographie

[1] Chegis I. A., Yablonskii S. V., “Logicheskie sposoby kontrolya elektricheskikh skhem”, Tr. MI AN SSSR, 1958, M. | Zbl

[2] Dyukova E. V., “Ob asimptoticheski optimalnom algoritme postroeniya tupikovykh testov”, Dokl. AN SSSR, 233:4 (1977), 527–530 | MR | Zbl

[3] Dyukova E. V., “Asimptoticheski optimalnye testovye algoritmy v zadachakh raspoznavaniya”, Probl. kibernetiki, 39, Nauka, M., 1982, 165–169 | MR

[4] Dyukova E. V., “O slozhnosti realizatsii nekotorykh protsedur raspoznavaniya”, Zh. vychisl. matem. i matem. fiz., 27:1 (1987), 114–127 | MR | Zbl

[5] Dyukova E. V., “Algoritmy raspoznavaniya tipa “Kora”: slozhnost realizatsii i metricheskie svoistva”, Raspoznavanie, klassifikatsiya, prognoz (matem. metody i ikh primenenie), vyp. 2, Nauka, M., 1989, 99–125 | MR

[6] 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

[7] Dyukova E. V., “O slozhnosti realizatsii diskretnykh (logicheskikh) protsedur raspoznavaniya”, Zh. vychisl. matem. i matem. fiz., 44:3 (2004), 562–572 | MR | Zbl

[8] Dyukova E. V., Inyakin A. S., “Asimptoticheski optimalnoe postroenie tupikovykh pokrytii tselochislennoi matritsy”, Matem. vopr. kibernetiki, 17, Nauka, M., 2008, 235–246

[9] Djukova E. V., Nefedov V. Yu., “The complexity of transformation of normal forms for characteristic functions of classes”, Pattern Recognition and Image Analysis, 19:3 (2009), 435–440 | DOI

[10] Noskov V. N., Slepyan V. A., “O chisle tupikovykh testov dlya odnogo klassa tablits”, Kibernetika. Kiev, 1972, no. 1, 60–65 | MR | Zbl

[11] Sapozhenko A. A., “Otsenka chisla tupikovykh d.n.f. dlya pochti vsekh ne vsyudu opredelennykh bulevykh funktsii”, Mateem. zametki, 28:2 (1980), 279–299 | MR

[12] Dyukova E. V., Peskov N. V., “Postroenie raspoznayuschikh protsedur na baze elementarnykh klassifikatorov”, Matem. vopr. kibernetiki, 14 (2005), 57–92 | Zbl

[13] Dyukova E. V., Inyakin A. S., “O protsedurakh klassifikatsii, osnovannykh na postroenii pokrytii klassov”, Zh. vychisl. matem. i matem. fiz., 43:12 (2003), 1884–1895 | MR | Zbl

[14] Dyukova E. V., “O chisle tupikovykh pokrytii tselochislennoi matritsy”, Zh. vychisl. matem. i matem. fiz., 45:5 (2005), 935–940 | MR | Zbl

[15] Dyukova E. V., “Metricheskie svoistva blizkikh k minimalnym pokrytii tselochislennykh matrits”, Intellektualizatsiya obrabotki informatsii, Tezisy dokl. Mezhdunar. konf., Simferopol, 2002, 37–38

[16] Dyukova E. V., “O postroenii tupikovykh pokrytii bulevoi matritsy”, Dokl. RAN, 412:1 (2007), 15–17 | MR

[17] Demyanov E. A., Dyukova E. V., “O postroenii tupikovykh pokrytii tselochislennoi matritsy”, Zh. vychisl. matem. i matem. fiz., 47:3 (2007), 538–546 | MR

[18] Andreev A. E., “Ob asimptoticheskom povedenii chisla tupikovykh testov i dliny minimalnogo testa dlya pochti vsekh tablits”, Probl. kibernetiki, 41, Nauka, M., 1984, 117–142 | MR