On the complexity of the dualization problem

DOI10.1134/S0965542512100090zbMath1274.68137MaRDI QIDQ2838941

R. M. Sotnezov, E. V. Dyukova

Publication date: 3 July 2013

Published in: Computational Mathematics and Mathematical Physics (Search for Journal in Brave)

zbMATH Keywords

Boolean matrixconjunctive normal formirreducible coveringsdualization problemmaximal conjunctions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Boolean and Hadamard matrices (15B34)

Related Items (2)

Unnamed Item ⋮ Asymptotically optimal dualization algorithms

Cites Work

• Construction of irredundant coverings of a Boolean matrix
• On the complexity of discrete generation problems
• An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation
• On generating all maximal independent sets
• Estimation of the length and the number of dead-end disjunctive normal forms for almost all partial Boolean functions
• On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions
• Asymptotic estimates for the number of solutions of the dualization problem and its generalizations
• The complexity of the realization of certain recognition procedures
• On the construction of irredundant coverings of an integer matrix
• Discrete analysis of feature descriptions in recognition problems of high dimensionality
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the complexity of the dualization problem