Dualization of regular Boolean functions (Q1084376)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Dualization of regular Boolean functions |
scientific article |
Statements
Dualization of regular Boolean functions (English)
0 references
1987
0 references
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.
0 references
monotonic Boolean function
0 references
maximal false points
0 references
minimal true points
0 references
efficient algorithm
0 references