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

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

Reduction from sets to tritograms

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

multiset: ⇒ deuterogram:

Multiset system of ind

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

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.

Hence, for deutero-arithmetics the items and are d- equivalent and are represented as [2,1] . This holds for too. The items and , are deutero-equivalent and represented by [] = [1,1].

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

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.

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:

System of elementary morphic cellular automata rules

System of elementary deuteroRules

System of the rules

Deutero - Arithmetics

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

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

Reduction of the trito-rule set

Representations for deutero - sets

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

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.

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:

Representations

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

Further reductions

Semi - defined representations in domain ruleCl

System of

Definition of the elementary deutero-rule set

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.

Domain ruleMD2

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

{2,4}. (2,5}, {2,15},

{{4,5}#, {4,15}#,

{5,15}#}

Equivalence and difference in ruleMD2

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}#}

Aborted Cases

Domain ruleMD4

Domain ruleMD5

Same visualization but different transition graphs

Sound representations

Comparison of deutero- and trito-Rules

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

Examples for non-commutativity