Cantor pairing function

In 1679 Gottfried Wilhelm Leibniz [Leib1999] developed in nine manuscripts three different models for the representation of Aristotelian logic with numbers. Corresponding to the idea of Leibniz concepts are containing or excluding higher concepts, we will use in a first step Leibniz characteristic numbers (LCN) to model semantic products. In his method each basic concept is a concept without a decomposition and is associated with a prime number, e.g.

• LCN (>PRE-Thing) = 2; LCN (>PRE-tangible) = 23.

• LCN (>PRE-Body) = LCN (>PRE-tangible) * LCN (>PRE-Thing) = 23 * 2 = 46.

• LCN (>PRE-BodyPart) = LCN (>PRE-Body) * LCN (>PRE-Part)
= 46 * 5 = 230 = 23 * 2 * 5 or
• LCN (>PRE-Creature) = LCN (>PRE-living) * LCN (>PRE-Body)
= 29 * 46 = 1334 = 29 * 23 * 2.

This works fine as long as the sequence of the two paired concepts does not matter. But it is obvious, that the concepts of boat house and house boat (noun + noun) can not be differentiated, since multiplication is commutative (Figure CNS-HB-BH):

• LCN (>PRE-HouseBoat) = LCN (>PRE-House) * LCN (>PRE-Boat) = 6 * 91 = 546 and
• LCN (>PRE-BoatHouse) = LCN (>PRE-Boat) * LCN (>PRE-House) = 91 * 6 = 546.

The only way to avoid these kind of problems was to find another method, which has the same characteristic in decomposition with respect to prime numbers and prime factors. Cantor´s pairing function

• π (y,x) = y + (x + y) (x + y + 1) / 2

provides these properties. The example in the graph of Fig. 3 shows the definition of boat house and houseboat by the method of reification using Bliss Symbols for the graphical encoding of the concept semantics. The property .CCN (Cantor Characteristic Number) is defined as a constant for a basic concept and it is computed for a composed concept. For >BLS-boathouse the left semantic factor >BLS-boat is connected via the relationship type ◊Subject, while the right semantic factor >BLS-house is connected via the relationship type ◊Object.

With .CCN(>BLS-boat) = 88 and .CCN(>BLS-house) = 130 the result of applying the pairing function is

• .CCN(>BLS-boathouse) = π (88, 130) = 24001 while
• .CCN(>BLS-houseboat) = π (130, 88) = 23959.

The reification method used so far is a reduced form, since in the general form of reification also the relation between subject and object can be modeled. I will show later, that with the general form of reification it is easier and more transparent to model description logic type of definitions

After having identified the atomic/base concepts in principal it does not matter which integer number is associated which each of the concepts. But intuitively one would say that the numbers should be kept as small as possible. Also there is an performance argument, since the algorithm for computing the pair (x, y) of numbers from a number n with Cantor´s pairing function is getting much slower for large numbers of n. The runtime for the inverting of the Cantor pairing function though can be optimized by applying the auxiliary functions triangle number (Dreieckzahl) and floored triangle root number (abgerundete Dreieckswurzel).

One heuristic for ordering the base concepts is based on the construction principle of Bliss Words. Bliss Words consisting of only one Bliss Symbol are very likely base concepts. On the other hand one can simple count, how often a certain Bliss Symbol goes into the construction of Bliss Words. Let CNT(symbol) be the number of usag/es of symbol and

• C0 = CNT(s0), C1 = CNT(s1), C2 = CNT(s2), .. , Cn=CNT(sn)

the counts of the symbols s0, s1, s2, ..., sn such that

• C0 ≥ C1 ≥ C2 ... ≥ Cn.

Let CCN (Characteristic Cantor Number) be the number, which is assigned to a concept represented by a symbol. Then as a first step we set

• CCN(s0) = 0, CCN(s1) = 1, CCN(s2) = 2, ..., CCN(sn) = n.

The pairing number for new concept q derived from two concepts m and n is computed as

• CCN(q) = π (CCN(m), CCN(m)).

We started with a set of approximately 450 base concepts of Minimal English. First of all in the set all concepts have to be analyzed, if they can be composed from other concepts. Especially groups of concepts are candidates, which fall into families of concepts (FoC) like (addition, subtraction, multiplication, division) or (north, south, west, east) or (top, bottom, in front of, behind) etc. After computing each CCN(q) for all n base concepts, there will be probably collisions with CCN(q) ≤ n. If CCN(s_x) is the smallest number, where a collision occurs, then the CCN for s_x will be increased by 1 and all CCNs ≥ CCN(sx) have to be recalculated. This procedure has to be repeated until there a no more collisions.