Dualization of regular Boolean functions
From MaRDI portal
A monotonic Boolean function is regular if its variables are naturally ordered by decreasing 'strength', so that shifting to the right the non- zero entries of any binary false point always yields another false point. Peled and Simeone recently published a polynomial algorithm to generate the maximal false points (MFP's) of a regular function from a list of its minimal true points (MTP's). Another efficient algorithm for this problem is presented here, based on a characterization of the MFP's of a regular function in terms of its MTP's. This result is also used to derive a new upper bound on the number of MFP's of a regular function.
Recommendations
- Dualities in the class of extended Boolean functions
- A duality between Boolean functions
- scientific article; zbMATH DE number 2108196
- Dualization of Boolean functions using ternary decision diagrams
- On duality for Boolean programming
- Dual subimplicants of positive Boolean functions
- scientific article; zbMATH DE number 4116525
- Boolean functions with MacWilliams duality
- scientific article; zbMATH DE number 26594
- An O(nm)-time algorithm for computing the dual of a regular Boolean function
Cites work
- A characterization, existence proof and dimension bounds for the kernel of a game
- An Algorithm to Dualize a Regular Switching Function
- scientific article; zbMATH DE number 3598234 (Why is no real title available?)
- scientific article; zbMATH DE number 3266648 (Why is no real title available?)
- scientific article; zbMATH DE number 3385535 (Why is no real title available?)
- Polynomial-time algorithms for regular set-covering and threshold synthesis
- The desirability relation of simple games
- Threshold hypergraphs
Cited in
(39)- On the fractional chromatic number of monotone self-dual Boolean functions
- An O(m n) algorithm for regular set-covering problems
- Duality for a class of binary operations on [0, 1]
- Dualization, decision lists and identification of monotone discrete functions
- An O(nm)-time algorithm for computing the dual of a regular Boolean function
- Interior and exterior functions of positive Boolean functions.
- An inequality for polymatroid functions and its applications.
- Dualities in the class of extended Boolean functions
- Recognition and dualization of disguised bidual Horn functions.
- Efficient dualization of \(O(\log n\))-term monotone disjunctive normal forms
- Dual-bounded generating problems: Weighted transversals of a hypergraph
- Decompositions of positive self-dual Boolean functions
- Boolean minors
- Interior and exterior functions of Boolean functions
- Minimum self-dual decompositions of positive dual-minor Boolean functions
- On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions
- On the enumeration of Boolean functions with distinguished variables
- Boolean functions with MacWilliams duality
- Exploiting regularities for Boolean function synthesis
- Recognition of a class of unimodular functions
- Unique key Horn functions
- scientific article; zbMATH DE number 7034406 (Why is no real title available?)
- A linear time algorithm for recognizing regular Boolean functions
- scientific article; zbMATH DE number 4098710 (Why is no real title available?)
- scientific article; zbMATH DE number 26594 (Why is no real title available?)
- scientific article; zbMATH DE number 165544 (Why is no real title available?)
- Generating dual-bounded hypergraphs
- scientific article; zbMATH DE number 1522935 (Why is no real title available?)
- Bimatroidal independence systems
- Linear separation of connected dominating sets in graphs
- Tree-shellability of Boolean functions
- Incremental polynomial time dualization of quadratic functions and a subclass of degree-\(k\) functions
- Dual bounded generation: polynomial, second-order cone and positive semidefinite matrix inequalities
- The threshold order of a Boolean function
- A global parallel algorithm for the hypergraph transversal problem
- 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
This page was built for publication: Dualization of regular Boolean functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1084376)
