Fast algorithm for inverting the boolean sum of products

Question

I am trying to implement a very fast logical expression engine. I use it to represent states in very large state spaces, so I need it to process as many operations per second as possible. At the heart of this engine is the sum of the products. However, I ran into the problem of optimizing the NOT operator. For example, if I have a sum of products with N minterms, where each minterm has about M variables, then tries to invert, which would create M ^ N minterms, which would then be simplified using the espresso algorithm. I can speed it up a bit and save some memory if I run the espresso algorithm intermittently during the reverse operation, but this is not enough. I doubt that I am the first person to encounter this problem, and I tried to do a study,but I cannot find an effective way to do this.

Can someone point me in the right direction?

Answer 1

So, 5 years have passed since I posted this question. After a recent discovery, I realized that I had committed a cardinal sin. At some point between this and now I found a pretty quick algorithm to do this, and never came back to answer a question. The problem is that I lost all related documentation. Welp ... there it is. I will update this answer if I reopen the source.

https://github.com/nbingham1/boolean/blob/a0f21eb1808dbcf86a3360ea85ab4eae15f5bf49/boolean/cover.cpp#L1055

EDIT: found source

Multi-valued logic minimization for PLA synthesis Richard L. Rudell, p. 58

https://apps.dtic.mil/dtic/tr/fulltext/u2/a606736.pdf

, .

Answer 2

O(n+m),

answer = ( x1 OR x2 OR .. xn ) AND ( y1 OR y2 OR .. ym )

, , 1

answer = ( x1 OR x2 OR .. xn ) LOGICAL-AND ( y1 OR y2 OR .. ym )

LOGICAL-AND , 0, 0 O(n+1)

DEFINE X = { X1, X2, .. Xn }
DEFINE Y = { Y1, Y2, .. Ym }

ANSWER =  X ∈ 1  AND  Y ∈ 1

IF X ∈ 1
THEN RETURN Y ∈ 1
ELSE RETURN 0

Time = i + j

i = position of left-most 1 in X
j = position of left-most 1 in Y 

, O(n+m)

000..001, 000..000

000..001, 000..001