Search NKS | Online
11 - 13 of 13 for Complement
![](/common/images/search/spacer.gif)
Given an original DNF list s , this can be done using PI[s, n] :
PI[s_, n_] := Union[Flatten[ FixedPointList[f[Last[#], n] &, {{}, s}] 〚 All, 1 〛 , 1]]
g[a_, b_] := With[{i = Position[Transpose[{a, b}], {0,1}]}, If[Length[i] 1 && Delete[a, i] === Delete[b, i], {ReplacePart[a, _, i]}, {}]]
f[s_, n_] := With[ {w = Flatten[Apply[Outer[g, #1, #2, 1] &, Partition[Table[ Select[s, Count[#, 1] i &], {i, 0, n}], 2, 1], {1}], 3]}, {Complement[s, w, SameTest MatchQ], w}]
The minimal DNF then consists of a collection of these prime implicants.
The possible configurations that repeat with period p then correspond to the finite complement language (see page 958 ) obtained by stringing together these blocks.
And indeed, of the 4096 symmetric 5-neighbor rules, only identity and complement conserve e[s] . … Of the 262,144 9-neighbor outer totalistic rules the only ones that conserve e[s] are identity and complement.
![](/common/images/search/spacer.gif)