CODEWITHSUNDEEP
algorithmoptimizationboolean-logicboolean-expression
Matt Timmermans
Matt Timmermans

Reputation: 59303

Limiting the depth of Boolean expressions

I am given a Boolean expression of arbitrary depth, like (A or (B and (C or (~D and E) or F) or (G and H))). There can be any number of terms at each level.

I want to limit the depth of the expression (the maximum depth of nested parentheses + 1) to some constant like 4. If the depth exceeds that bound, then I want to generate an equivalent expression with depth that does not exceed the bound.

I know that I can convert to CNF or DNF, which would limit the depth to 2, but the size of the expression can blow up exponentially.

How can I take advantage of more available levels to limit the size of the resulting expression as much as possible?

Upvotes: 8

Views: 289

Answers (0)

Related Questions