Informatics and Applications
2019, Volume 13, Issue 1, pp 25-32
ON THE NUMBER OF MAXIMAL INDEPENDENT ELEMENTS OF PARTIALLY ORDERED SETS (THE CASE OF CHAINS)
- E. V. Djukova
- G. O. Maslyakov
- P. A. Prokofyev
Abstract
One of the central intractable problems of logical data analysis is considered - dualization over the product of partially ordered sets. The authors investigate an important special case where each order is a chain. If the power of each chain is two, then the problem under consideration is to construct the reduced disjunctive normal form of a monotone Boolean function given by a conjunctive normal form. This is equivalent to enumerating irreducible covers of a Boolean matrix. Provided the growth of the row's number of the Boolean matrix to be less than the growth of the column's number, the asymptotic for the typical number of irreducible covers is known.
In the present work, a similar result is obtained for the dualization over the product of chains when the power of each chain is more than two. Obtaining such asymptotic estimates is a technically complex task and is necessary, in particular, to justify the existence of asymptotically optimal algorithms for the problem of monotonic dualization and various generalizations of this problem.
[+] References (9)
- Johnson,D., M. Yannakakis,and C. Papadimitriou.1988. On generating all maximal independent sets. Inform. Process.Lett. 27(3):119–123.
- Fredman, M., and L. Khachiyan. 1996. On the complexity of dualization of monotone disjunctive normal forms. J.Algorithm. 21(3):618–628.
- Boros, E., K. Elbassioni, V. Gurvich, L. Khachiyan, and K. Makino. 2002. Dual-bounded generating problems: All minimal integer solutions for a monotone system of linear inequalities. SIAM J. Comput. 31(5):1624- 1643.
- Elbassioni, K. 2009. Algorithms for dualization over products of partially ordered sets. SIAM J. Discrete Math. 23(1):487-510.
- Djukova, E. 1977. On an asymptotically optimal algo- ritm for constructing irredundant tests. Sov. Math. Dokl. 18(2):423-426.
- Djukova, E., and P. Prokofyev. 2015. Asymptotically optimal dualization algoritms. Comp. Math. Math. Phys. 55(5):891-905.
- Noskov, V., and V. Slepian. 1972. O chisle tupikovykhtestov dlya odnogo klassa tablits [On the number of irredundant tests for a class of tables]. Kibernetika [Cybernetics] 1:6065.
- Djukova, E., G. Masliakov, and P. Prokofjev. 2017. O dua- lizatsii nad proizvedeniem chastichnykh poryadkov [About product over partially ordered sets]. Mashinnoe obuchenie ianalizdannykh [Machine Learning Data Anal.] 3(4):239- 249.
- Dyukova, E. 1987. On the complexity of implementation of some recognition procedures. Comp. Math. Math. Phys. 27(1):74-83.
[+] About this article
Title
ON THE NUMBER OF MAXIMAL INDEPENDENT ELEMENTS OF PARTIALLY ORDERED SETS (THE CASE OF CHAINS)
Journal
Informatics and Applications
2019, Volume 13, Issue 1, pp 25-32
Cover Date
2019-04-30
DOI
10.14357/19922264190104
Print ISSN
1992-2264
Publisher
Institute of Informatics Problems, Russian Academy of Sciences
Additional Links
Key words
problem of dualization; product of partially ordered sets; chain; covering of a Boolean matrix; ordered covering of an integer matrix; asymptotically optimal algorithm
Authors
E. V. Djukova  ,  , G. O. Maslyakov ,
and P. A. Prokofyev 
Author Affiliations
Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 42 Vavilov Str., Moscow 119333, Russian Federation
Faculty of Computational Mathematics and Cybernetics, M. V. Lomonosov Moscow State University, 1-52 Leninskiye Gory, GSP-1, Moscow 119991, Russian Federation
Mechanical Engineering Research Institute of the Russian Academy of Sciences, 4 Bardina Str., Moscow 119334, Russian Federation
|