Aspects of Complexity Reduction for
                         morphoCAs -
                   The deutero approach

Dr. phil Rudolf Kaehr
copyright © ThinkArt Lab Glasgow
ISSN 2041-4358
(work in progress, vs. 0.1, Jan. 2015)

Reduction of the complexity of morphoCAs by deutero-abstraction

One important motivation for a introduction of deutero-structural based morphic cellular automata is to reduce computational complexity by saving its structural complexity.

Deutero-structures of the morphogrammatic system shall be introduced as such a further strategy of complexity reduction for morphogrammatic based cellular automata.

The focus of the previous papers on morphoCAs had been on the trito-structure of morphogrammatics. This paper turns its focus on the deutero-structure of morphogrammatics with the aim to introduce a further strategy of complexity reduction for morphoCAs.

ABSTRACTION FROM THE ORDER AND IDENTITY OF ATOMS: HEAPS OF KENOMS
“In his development of the theory of kenograms, Gotthard Gunther introduced three layers of abstraction, and called them “Trito Structure”, “Deutero Structure” and “Proto Structure”. The Trito Structure coincides with what we have called “strings of kenoms”. The Deutero Structure was derived from Trito Structure by abstracting from the order in which the kenoms occur. The Proto Structure was derived from Deutero Structure by excluding patterns in which more than one atom occur repeatedly.

- heaps of atoms are stucturally very similar to multisets.”  (R. Matzka)

http://www.rudolf-matzka.de/dharma/semabs.pdf

Deutero-Structure results from the assumption that maximal repetition is allowed for individual kenograms. As for the rest, the placing of the symbol still remains irrelevant” (Gunther 1980, p. 111).

Deutero-sets

If we abstract in this model of tritosets from the order of the occurrences of the elements (kenograms), we get a new class or type of languages, the languages based on deutero-sets.

Hence, the deutero-sets (aab), (aba), (bba) and (bab), are deutero-equal, equally [aaa] and [bbb],  while (aaa) and (aab) are not deutero-equal. Deutero-sets are measured by the sum of partitions: P(n, m). Therefore, [aaa] and [bbb] are d-equal because they have the same number of partitions, i.e. one partition of itself.

In contrast, albeit multisets {a,a,a} and {b,b,b} have the same partitions, they differ in their elements, “a” and “b”, a ≠ b.

That defines the difference between deuteroCAs and indicational CAs, indCAs. Indicational CAs are based mathematically on multisets. The famous Calculus of Indication is based on multsets with just 2 elements, Mark and Nil.

Hence, deutero-sets are not just abstracting from the order (position) of identitive elements of a set, but from the order of kenograms in trito-sets. Kenograms are not identitive elements in contrast to the elements (atoms) of sets and multisets as they are defined in set theory.

Multisets are well presented by the paper:
http://www.emis.de/journals/NSJOM/Papers/37_2/NSJOM_37_2_073_092.pdf

System of abstractions

Deutero-Reduction_1.gif

Abstraction from msets to deutero - psets and to deutero - sets:

Deutero-Reduction_2.gif

Deutero-Reduction_3.gif

Reduction from sets to tritograms

Deutero-Reduction_4.gif

Hence, deutero-sets are in a strict sense not sets and also not multi-sets but kenomic aggregations of kenograms that are abstracting from the order of the (not-identive) kenograms of a trito-structure. Multisets are abstracting from the order of their elements too, but the elements of a multiset are identive, while the kenograms of a deuterogram are not identive.

The computational domain of multisets had been studied as indictional cellular automata, indCA, in conection to the Calculus of Indication of George Spencer Brown.

http://memristors.memristics.com/IndCA/Indicational%20CA.html

             Deutero-Reduction_5.gif

multiset:  Deutero-Reduction_6.gif   ⇒  deuterogram:  Deutero-Reduction_7.gif

Multiset system of indDeutero-Reduction_8.gif

Deutero-Reduction_9.gif

Equivalence of ruleCI[{1, 6, 3, 8}] and ruleMD3[{1, 4, 2}]

Deutero-Reduction_10.gif

Deutero-Reduction_11.gif

Deutero-Reduction_12.gif

Deutero-Reduction_13.gif

Deutero-Reduction_14.gif

Deutero-Reduction_15.gif

Deutero-Reduction_16.gif

Systematic locus of deuteroCAs

The emphasis is on the comparison of morphic, indcational and deutero CAs. Indicational CAs, indCAs, had been studied in a previous paper. They are based on multisets. As a contrast, deuteroCAs are based on partitions, while morphoCAs are framed by the Stirling numbers of the second kind. Multisets are, like sets, defined by the identity of their elements. Trito- and deutero structures are structured by non-identive signs, i.e. kenograms.

It follows that the deutero rules are defined by the trito-abstraction for the morphograms and by permutations defining the deutero-structure of morphograms.

Deutero-Reduction_17.gif

Hence, for deutero-arithmetics the items  Deutero-Reduction_18.gif and Deutero-Reduction_19.gif are d- equivalent and are represented as [2,1] . This holds for Deutero-Reduction_20.gif too. The items Deutero-Reduction_21.gif and Deutero-Reduction_22.gif, are deutero-equivalent and represented by [Deutero-Reduction_23.gif] = [1,1].

A summary of the systematic situation is given by the following table:

Deutero-Reduction_24.gif

Other methods of complexity reduction for morphoCAs had been presented at:

http://memristors.memristics.com/Decompositions/Decomposition.pdf , (html, cdf)

The deutero-approach to writing systems is well placed in the system of graphematics.

Deutero-Reduction_25.gif

http://memristors.memristics.com/Graphematics/Graphematics%20of%20Cellular%20Automata.pdf

http://memristors.memristics.com/Graphematics%20of%20Multisets/Graphematics%20of%20Multisets.pdf

As a consequence of combinatorial sketch to deuterograms it follows that deuteroCAs are placed at a genuine place between multi-sets and tritograms, and are therefore exploring a new domain of an algorithmic poly-verse.

Again,in contrast to Stirling patterns, i.e. morphograms of the trito-structure, that are being studied by the new type of CAs, the morphoCAs, the deutero-structure is abstracting additionally from the abstraction of the identity of the signs also from the positions of the elements involved in the morphic patterns. Therefore they are mathematically characterized not by the Stirling numbers of the second kind but by the concept of integer partitions (Pascal) and defining its algorithmic domain by deuteroCAs.

Partitions of classical elementary CAs are studied by:
http://www.mathpages.com/home/kmath416/kmath416.htm

Reduction steps

The steps of numerical reduction as part of a reduction of morphoCAs is given by the chain:

Deutero-Reduction_26.gif

Deutero-Reduction_27.gif

Deutero-Reduction_28.gif

Deutero-Reduction_29.gif

Deutero-Reduction_30.gif

Deutero-Reduction_31.gif

System of elementary morphic cellular automata rules

Deutero-Reduction_32.gif

System of elementary deuteroRules

Deutero-Reduction_33.gif

Deutero-Reduction_34.gif

Deutero-Reduction_35.gif

Deutero-Reduction_36.gif

Deutero-Reduction_37.gif

Deutero-Reduction_38.gif

System of the Deutero-Reduction_39.gif rules

Deutero-Reduction_40.gif

Deutero - Arithmetics

Deutero-Reduction_41.gif

Deutero-Reduction_42.gif

Deutero-Reduction_43.gif

Deutero-Reduction_44.gif

Deutero-Reduction_45.gif

Deutero-Reduction_46.gif

Deutero-Reduction_47.gif

Deutero-Reduction_48.gif

http : // memristors.memristics.com/Interplay/Interplay %20 of %20 Elementary %20 Graphematic %20 Calculi.pdf

http : // www.vordenker.de/ggphilosophy/gg_natural - numbers.pdf

Deutero-Reduction_49.gif

Deutero-Reduction_50.gif

Deutero-Reduction_51.gif

Deutero-Reduction_52.gif

Deutero-Reduction_53.gif

Reduction of the trito-rule set

Deutero-Reduction_54.gif

Representations for deutero - sets

Deutero-Reduction_55.gif

Example 1. How many permutations are there of the mset [abccbccbddb]?
Solution. We want to find the number of permutations of the multiset
[A] = [a, b, c, d] 11243442 = {1·a, 4·b, 4·c, 2·d}.

Thus, n = 11, n1 = 1, n2 = 4, n3 = 4, n4 = 2. Then number of permutations is given by
Deutero-Reduction_56.gif
Thus, the mset[A] = [a, b, c, d] 11243442 has 330 identitive representations. The notation
[abccbccbddb] for [A] is therefore a conventional choice and put into mset - normal form notation.

Non-commutativity

A consequence of the loss of the morphic pattern quality, the order of the components of the composed deutero-rules is not anymore commutative in general.

Deutero-Reduction_57.gif

Commutativity for ruleM

The rule set for the domain ruleM are based on the ordered morphograms of the ‘system of elementary morphic cellular automata rules’. The criterion of the composed rules is not commutativity but the acceptance of the order of the morphic components.

Therefore, a constellation like ruleM[{1,2,7,3,8}] is not accepting the order of the morphogrammatic system and results in a undefined situation.

Formally:

      Deutero-Reduction_58.gif

Deutero-Reduction_59.gif

Deutero-Reduction_60.gif

Deutero-Reduction_61.gif

Deutero-Reduction_62.gif

Deutero-Reduction_63.gif

Deutero-Reduction_64.gif

Deutero-Reduction_65.gif

Deutero-Reduction_66.gif

Deutero-Reduction_67.gif

Deutero-Reduction_68.gif

Deutero-Reduction_69.gif

Deutero-Reduction_70.gif

Deutero-Reduction_71.gif

Deutero-Reduction_72.gif

Deutero-Reduction_73.gif

Deutero-Reduction_74.gif

Deutero-Reduction_75.gif

Deutero-Reduction_76.gif

Deutero-Reduction_77.gif

Deutero-Reduction_78.gif

Deutero-Reduction_79.gif

Deutero-Reduction_80.gif

Deutero-Reduction_81.gif

Deutero-Reduction_82.gif

Representations

ruleM[{1, 2, 12, 9, 15}]             ⇒           permutations of ruleMD4[{1, 2, 4, 5}]

Deutero-Reduction_83.gif

Further reductions

Deutero-Reduction_84.gif

Deutero-Reduction_85.gif

Deutero-Reduction_86.gif

Deutero-Reduction_87.gif

Deutero-Reduction_88.gif

Deutero-Reduction_89.gif

Deutero-Reduction_90.gif

Deutero-Reduction_91.gif

Deutero-Reduction_92.gif

Deutero-Reduction_93.gif

Semi - defined representations in domain ruleCl

Deutero-Reduction_94.gif

Deutero-Reduction_95.gif

Deutero-Reduction_96.gif

Deutero-Reduction_97.gif

Deutero-Reduction_98.gif

Deutero-Reduction_99.gif

Deutero-Reduction_100.gif

Deutero-Reduction_101.gif

System of Deutero-Reduction_102.gif

Definition of the elementary deutero-rule set Deutero-Reduction_103.gif

Domain ruleMD1

ruleMD1 = {[R1]#, [R2], [R4]#, [R5]#, [R15]#}

There is just one deuteroCA with a rule length of 1 that is accepted by the CellularAutomaton of the deuteroCA construction. It is the deutero-rule ruleMD[{2}].

The other constellations are not accepted by the CellularAutomaton of the deuteroCA construction.

Deutero-Reduction_104.gif

Deutero-Reduction_105.gif

Deutero-Reduction_106.gif

Deutero-Reduction_107.gif

Deutero-Reduction_108.gif

Deutero-Reduction_109.gif

Deutero-Reduction_110.gif

Deutero-Reduction_111.gif

Deutero-Reduction_112.gif

Deutero-Reduction_113.gif

Deutero-Reduction_114.gif

Deutero-Reduction_115.gif

Deutero-Reduction_116.gif

Deutero-Reduction_117.gif

Deutero-Reduction_118.gif

Deutero-Reduction_119.gif

Deutero-Reduction_120.gif

Deutero-Reduction_121.gif

Deutero-Reduction_122.gif

Deutero-Reduction_123.gif

Deutero-Reduction_124.gif

Deutero-Reduction_125.gif

Deutero-Reduction_126.gif

Deutero-Reduction_127.gif

Deutero-Reduction_128.gif

Deutero-Reduction_129.gif

Domain ruleMD2

ruleMD2 = {{1,2}, {1,4}, {1,5}, {1,15}#
                 {2,4}.  (2,5}, {2,15},
                 {{4,5}#, {4,15}#,
                 {5,15}#}

Deutero-Reduction_130.gif

Deutero-Reduction_131.gif

Deutero-Reduction_132.gif

Deutero-Reduction_133.gif

Deutero-Reduction_134.gif

Deutero-Reduction_135.gif

Deutero-Reduction_136.gif

Deutero-Reduction_137.gif

Deutero-Reduction_138.gif

Deutero-Reduction_139.gif

Deutero-Reduction_140.gif

Deutero-Reduction_141.gif

Deutero-Reduction_142.gif

Deutero-Reduction_143.gif

Deutero-Reduction_144.gif

Deutero-Reduction_145.gif

Deutero-Reduction_146.gif

Deutero-Reduction_147.gif

Deutero-Reduction_148.gif

Deutero-Reduction_149.gif

Deutero-Reduction_150.gif

Deutero-Reduction_151.gif

Deutero-Reduction_152.gif

Deutero-Reduction_153.gif

Deutero-Reduction_154.gif

Deutero-Reduction_155.gif

Deutero-Reduction_156.gif

Deutero-Reduction_157.gif

Deutero-Reduction_158.gif

Deutero-Reduction_159.gif

Deutero-Reduction_160.gif

Deutero-Reduction_161.gif

Deutero-Reduction_162.gif

Deutero-Reduction_163.gif

Equivalence and difference in ruleMD2

Deutero-Reduction_164.gif

Deutero-Reduction_165.gif

Deutero-Reduction_166.gif

Deutero-Reduction_167.gif

Deutero-Reduction_168.gif

Deutero-Reduction_169.gif

Deutero-Reduction_170.gif

Deutero-Reduction_171.gif

Deutero-Reduction_172.gif

Deutero-Reduction_173.gif

Deutero-Reduction_174.gif

Deutero-Reduction_175.gif

Deutero-Reduction_176.gif

Deutero-Reduction_177.gif

Deutero-Reduction_178.gif

Deutero-Reduction_179.gif

Deutero-Reduction_180.gif

Deutero-Reduction_181.gif

Deutero-Reduction_182.gif

Deutero-Reduction_183.gif

Domain ruleMD3

ruleMD3 = {{1,2,4}, {1,2,5}, {1,2,15}, {1,4,5},{1,4,15},
                  {2,4,5}, {2,4,15}, {4,5,15}#}

Deutero-Reduction_184.gif

Deutero-Reduction_185.gif

Deutero-Reduction_186.gif

Deutero-Reduction_187.gif

Deutero-Reduction_188.gif

Deutero-Reduction_189.gif

Deutero-Reduction_190.gif

Deutero-Reduction_191.gif

Deutero-Reduction_192.gif

Deutero-Reduction_193.gif

Deutero-Reduction_194.gif

Deutero-Reduction_195.gif

Deutero-Reduction_196.gif

Deutero-Reduction_197.gif

Deutero-Reduction_198.gif

Deutero-Reduction_199.gif

Deutero-Reduction_200.gif

Deutero-Reduction_201.gif

Deutero-Reduction_202.gif

Deutero-Reduction_203.gif

Deutero-Reduction_204.gif

Deutero-Reduction_205.gif

Deutero-Reduction_206.gif

Deutero-Reduction_207.gif

Deutero-Reduction_208.gif

Deutero-Reduction_209.gif

Aborted Cases

Deutero-Reduction_210.gif

Deutero-Reduction_211.gif

Deutero-Reduction_212.gif

Deutero-Reduction_213.gif

Domain ruleMD4

Deutero-Reduction_214.gif

Deutero-Reduction_215.gif

Deutero-Reduction_216.gif

Deutero-Reduction_217.gif

Deutero-Reduction_218.gif

Deutero-Reduction_219.gif

Deutero-Reduction_220.gif

Deutero-Reduction_221.gif

Deutero-Reduction_222.gif

Deutero-Reduction_223.gif

Deutero-Reduction_224.gif

Deutero-Reduction_225.gif

Deutero-Reduction_226.gif

Deutero-Reduction_227.gif

Deutero-Reduction_228.gif

Deutero-Reduction_229.gif

Deutero-Reduction_230.gif

Domain ruleMD5

Deutero-Reduction_231.gif

Deutero-Reduction_232.gif

Deutero-Reduction_233.gif

Deutero-Reduction_234.gif

Deutero-Reduction_235.gif

Deutero-Reduction_236.gif

Same visualization but different transition graphs

Deutero-Reduction_237.gif

Deutero-Reduction_238.gif

Deutero-Reduction_239.gif

Deutero-Reduction_240.gif

Deutero-Reduction_241.gif

Deutero-Reduction_242.gif

Deutero-Reduction_243.gif

Deutero-Reduction_244.gif

Deutero-Reduction_245.gif

Deutero-Reduction_246.gif

Deutero-Reduction_247.gif

Deutero-Reduction_248.gif

Deutero-Reduction_249.gif

Deutero-Reduction_250.gif

Deutero-Reduction_251.gif

Deutero-Reduction_252.gif

Deutero-Reduction_253.gif

Deutero-Reduction_254.gif

Deutero-Reduction_255.gif

Deutero-Reduction_256.gif

Deutero-Reduction_257.gif

Deutero-Reduction_258.gif

Deutero-Reduction_259.gif

Deutero-Reduction_260.gif

Deutero-Reduction_261.gif

Deutero-Reduction_262.gif

Sound representations

Deutero-Reduction_263.gif

Deutero-Reduction_265.gif

Deutero-Reduction_267.gif

Deutero-Reduction_269.gif

Deutero-Reduction_271.gif

Comparison of deutero- and trito-Rules

Deutero-Reduction_273.gif

Deutero-Reduction_274.gif

Deutero-Reduction_275.gif

Deutero-Reduction_276.gif

Non-commutativity of rule components

In contrast to the morpho-rules of the type ruleM, ruleMN, etc. deutero-rules are not generally commutative.

For the domain of ruleM, the constituents are strictly disjunctive and are defining patterns and not partitions, therefore they are supporting commutativity.

Disjunctivity of the components of for ruleMD holds too, but the functions are defining partitions and not patterns, hence the commutativity of the domain ruleMD is not granted in general.

Non-commutative constellations

Deutero-Reduction_277.gif

Examples for non-commutativity

Deutero-Reduction_278.gif

Deutero-Reduction_279.gif

Deutero-Reduction_280.gif

Deutero-Reduction_281.gif

Deutero-Reduction_282.gif

Deutero-Reduction_283.gif

Deutero-Reduction_284.gif

Deutero-Reduction_285.gif

Deutero-Reduction_286.gif

Deutero-Reduction_287.gif

Deutero-Reduction_288.gif

Deutero-Reduction_289.gif

Deutero-Reduction_290.gif

Deutero-Reduction_291.gif

Deutero-Reduction_292.gif

Deutero-Reduction_293.gif

Deutero-Reduction_294.gif

Deutero-Reduction_295.gif

Deutero-Reduction_296.gif

Deutero-Reduction_297.gif

Deutero-Reduction_298.gif

Deutero-Reduction_299.gif

Deutero-Reduction_300.gif

Deutero-Reduction_301.gif

Deutero-Reduction_302.gif

Deutero-Reduction_303.gif

Deutero-Reduction_304.gif

Deutero-Reduction_305.gif

Deutero-Reduction_306.gif

Deutero-Reduction_307.gif

Deutero-Reduction_308.gif

Deutero-Reduction_309.gif

Deutero-Reduction_310.gif

Deutero-Reduction_311.gif

Deutero-Reduction_312.gif

Deutero-Reduction_313.gif

Deutero-Reduction_314.gif

Deutero-Reduction_315.gif

Deutero-Reduction_316.gif

Deutero-Reduction_317.gif

Deutero-Reduction_318.gif

Deutero-Reduction_319.gif

Deutero-Reduction_320.gif

Deutero-Reduction_321.gif

Deutero-Reduction_322.gif

Deutero-Reduction_323.gif

Deutero-Reduction_324.gif

Deutero-Reduction_325.gif

Deutero-Reduction_326.gif

Deutero-Reduction_327.gif

Deutero-Reduction_328.gif

Deutero-Reduction_329.gif

Deutero-Reduction_330.gif

Deutero-Reduction_331.gif

Deutero-Reduction_332.gif

Deutero-Reduction_333.gif

Deutero-Reduction_334.gif

Deutero-Reduction_335.gif

Deutero-Reduction_336.gif

Deutero-Reduction_337.gif

Deutero-Reduction_338.gif

Deutero-Reduction_339.gif

Deutero-Reduction_340.gif

Deutero-Reduction_341.gif

Deutero-Reduction_342.gif

Deutero-Reduction_343.gif

Deutero-Reduction_344.gif

Deutero-Reduction_345.gif

Deutero-Reduction_346.gif

Deutero-Reduction_347.gif

Deutero-Reduction_348.gif

Deutero-Reduction_349.gif

Deutero-Reduction_350.gif

Deutero-Reduction_351.gif

Deutero-Reduction_352.gif

Deutero-Reduction_353.gif

Deutero-Reduction_354.gif

Deutero-Reduction_355.gif

Deutero-Reduction_356.gif

Deutero-Reduction_357.gif

Deutero-Reduction_358.gif

Deutero-Reduction_359.gif

Deutero-Reduction_360.gif

Deutero-Reduction_361.gif

Deutero-Reduction_362.gif

Deutero-Reduction_363.gif

Deutero-Reduction_364.gif

Deutero-Reduction_365.gif

Deutero-Reduction_366.gif

Deutero-Reduction_367.gif

Deutero-Reduction_368.gif

Deutero-Reduction_369.gif

Deutero-Reduction_370.gif

Deutero-Reduction_371.gif

Deutero-Reduction_372.gif

Deutero-Reduction_373.gif

Deutero-Reduction_374.gif

Deutero-Reduction_375.gif

Deutero-Reduction_376.gif

Deutero-Reduction_377.gif

Deutero-Reduction_378.gif

Deutero-Reduction_379.gif

Deutero-Reduction_380.gif

Deutero-Reduction_381.gif

Deutero-Reduction_382.gif

Deutero-Reduction_383.gif

Deutero-Reduction_384.gif

Deutero-Reduction_385.gif

Deutero-Reduction_386.gif

Deutero-Reduction_387.gif

Deutero-Reduction_388.gif

Deutero-Reduction_389.gif

Deutero-Reduction_390.gif

Spikey Created with Wolfram Mathematica 9.0