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
    0 references

    Identifiers