Canalization Map does not correctly account for multiple permutable groups in Two Symbol Schema

[hsizek]

BooleanNode.canalizing_map() doesn't account for the SmS/ ss in the two symbol schema. This is not a problem if there are only one permutable group in the two symbols, but it become an issue when there are multiple permutable groups, as in the example below. Right now, the return from the canalizing_map() is nonsensical (see image below).

Logic Statement: E *= (A and B) or (C and D) Two Symbols: ([('0202', [[0, 1, 2, 3]], [[0, 2], [1, 3]])], [('1122', [[0, 1, 2, 3]], [[0, 1], [2, 3]])]) DCM:

Example Network: N = BooleanNetwork.from_string_boolean("""A *= A B *= B C *= C D *= D E *= (A and B) or (C and D)""",type="logical",name="test",keep_constraints=True)

[rionbr]

Hey @hsizek thanks for submitting this,

After looking over the code and discussing this with you, the output you see is actually correct based on the assumptions of the two-symbol schemata computation. For instance, in node E we have the following logic

E *= (A and B) or (C and D)

which is translated to this prime-implicant look-up-table (only ON shown)

PI-LUT	input	output
4	11##	ON
5	##11	ON

which in turn gets translated to (in parenthesis the same-symbol permutability is shown)

TS-LUT	input	output
1	1°1°#°#° or (1°1°## or 11#°#°)	ON

Note that the TS computation assumes all positions are permutable because it doesn't consider higher-level (i.e., n-tuple inputs) permutability. This is an assumption of the method, of course, and future implementations should try to account for that. Nonetheless, the canalizing map you see, based on the TS-schemata, is correct.

I'm going to mark this issue as an enhancement request as it's not necessarily a bug.

Cheers,

[austin-marcus]

I believe that CANA was intended to detect partial, conditional symmetry. "Partial" means it can detect the case when some proper subset of variables can be arbitrarily permuted without changing the output. "Conditional" means it can detect this even if it only occurs within a proper subset of the entire set of schemata. E.g., in the function $f=\bar AD(B\oplus C) \lor A\bar D \bar B C$, $B$ and $C$ can be arbitrarily permuted with each other iff $A=0$ and $D=1$.

However, the original function given above, $E = AB \lor CD$, contains an instance of strong (higher-order) symmetry. This is where groups of variables can be permuted, but not all subsets of those groups can be permuted. E.g., $AB$ can be interchanged as a group with $CD$, but $A$ and $C$ for instance, cannot be permuted only. Again, I agree that CANA was not intended to detect this kind of symmetry, but then it should render the output as 11## and ##11. Otherwise, it expands to implicants that are not part of the original function. E.g., 1#1# could be 1010, which should make the function false.

I implemented a fix (83ee8372fe409fff98fef8270c9ce7ba207661b2) to ensure that CANA correctly identifies partial conditional symmetry, without producing schemata not in the original function. I also implemented a series of unit tests on the cell collective functions to test it.

CANA now produces the following on $E$:

I am marking this resolved.