Dualization of regular Boolean functions

DOI10.1016/0166-218X(87)90056-4zbMath0605.94011OpenAlexW2041698105MaRDI QIDQ1084376

Yves Cramer

Publication date: 1987

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(87)90056-4

zbMATH Keywords

efficient algorithmmaximal false pointsminimal true pointsmonotonic Boolean function

Mathematics Subject Classification ID

Related Items (27)

An \(O(nm)\)-time algorithm for computing the dual of a regular Boolean function ⋮ Dual-bounded generating problems: Weighted transversals of a hypergraph ⋮ Decompositions of positive self-dual Boolean functions ⋮ An O(m n) algorithm for regular set-covering problems ⋮ A global parallel algorithm for the hypergraph transversal problem ⋮ Boolean minors ⋮ Recognition of a class of unimodular functions ⋮ Interior and exterior functions of Boolean functions ⋮ Unique key Horn functions ⋮ Interior and exterior functions of positive Boolean functions. ⋮ An inequality for polymatroid functions and its applications. ⋮ Incremental polynomial time dualization of quadratic functions and a subclass of degree-\(k\) functions ⋮ Minimum self-dual decompositions of positive dual-minor Boolean functions ⋮ On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions ⋮ Generating all minimal integral solutions to AND-OR systems of monotone inequalities: Conjunctions are simpler than disjunctions ⋮ Computational aspects of monotone dualization: a brief survey ⋮ On the complexity of monotone dualization and generating minimal hypergraph transversals ⋮ Counting and enumerating aggregate classifiers ⋮ Generating dual-bounded hypergraphs ⋮ Tree-shellability of Boolean functions ⋮ On the fractional chromatic number of monotone self-dual Boolean functions ⋮ Linear separation of connected dominating sets in graphs ⋮ Bimatroidal independence systems ⋮ Recognition and dualization of disguised bidual Horn functions. ⋮ On the enumeration of Boolean functions with distinguished variables ⋮ The threshold order of a Boolean function ⋮ Efficient dualization of \(O(\log n\))-term monotone disjunctive normal forms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Threshold hypergraphs
• The desirability relation of simple games
• Polynomial-time algorithms for regular set-covering and threshold synthesis
• A characterization, existence proof and dimension bounds for the kernel of a game
• An Algorithm to Dualize a Regular Switching Function

This page was built for publication: Dualization of regular Boolean functions