Chu Spacesbeing revised May 2006

Contents  Introduction  Basic  Intermediate  Advanced  Future  Policy  Infrastructure 
For starters, Chu Spaces are more general, and also more abstract. Binary relations and binary operations are square matrices and there is also an identity between the rows and columns. One way to see the difference is to look at the isomorphisms of small finite space and note the differerences.
The smallest, useful comparison can be made with an alphabet of {0,1}, 2 points and 2 states. This gives us 16 matrices.
00 00 00 00 01 01 01 01 10 10 10 10 11 11 11 11
00 01 10 11 00 01 10 11 00 01 10 11 00 01 10 11
All the representations admit renaming the alphabet as an isomorphic transformation. This gives us:
11 11 11 11 10 10 10 10 01 01 01 01 00 00 00 00
11 10 01 00 11 10 01 00 11 10 01 00 11 10 01 00
As can be seen, for an alphabet of 2 characters, this is a simple folding.
Given A o B, the result is a matrix of rows. Each row represents a mapping from A into B , not necessarily onto B. Each row of A o B is read as a list of elements (of rows) of B. There are as many elements in the row as there are rows in A, so the length of a row in A o B is (rows of A * rows of B).THere is an implied correspondence between the ith row of A and the ith element in the rows of A o B, that is the function f represented by A o B (row i ) maps f ( A (row j)) > element j .
Implication is calculated by making attempts to form a matrix with size of ( rows of A, cols of B). A matrix represents a morphism when all the columns of the matrix are columns of A and all the rows are rows of B.
To exhaustively enumerate all these matrices, every possible combination of character is tried in every position of the candidate matrix. Given an alphabet K the number of possibilities is truly huge even for small K, A, B. The formula is K ^{(rows of A * cols of B)}. A table with A and B being square matrices of size n gives us K^{n2}. The following table gives some values for K and n and some calculation times assuming 1 million tests per sec.
n = 2  n = 3  n = 4  n = 5  n = 6  

K = 2  16  512  65,536  33,554,432 ~ 33 secs  68,719,476,736 ~ 19 hrs 
K=3  81  19,683  43,046,721 ~ 43 secs  847,288,609,443 ~ 10 days  150,094,635,296,999,121 ~ 4759 years 
K=4  256  262,144  4,294,967,296 ~ 71 mins  2^{50} ~ 35 years  
K=5  625  1,953,125 ~ 2 secs  152,587,890,625 ~ 42 hours  
K=6  1296  10,077,696 ~ 10 secs  2,821,109,907,456 ~ 32 days 
Typically a K=4, n=4 implication may only find 4 morphisms out of the potential 4 billion possibilities, so implication is a real needle in a haystack search. The following diagram is a flowchart for the basic logic of implication.
The candidate matrix M is filled with "."s to start with. The dots mean there is no current valid candidate for this position in M. In fact the "."s are used to facilitate regexp searching in the Tcl implementation. The Matrix has r rows and c columns, and the alphabet has k symbols. Rows, columns and symbols all number from 0,1,... to r1, c1, and k1 respectively. A path is walked thru the cells of the matrix. In theory any path could be chosen, but it is fixed for the life of the search. In each cell the symbols 0, ..., k1 are tried in order.
An Initialisation procedure sets up the M matrix with its "."s, and sets up slightly modified copies of the two spaces which make regular expression matching by rows easy. It also initialises the pointer to the first cell.
The "incr symbol(cell)" action simply increments the value of the current cell symbol, treating "." as though it were 1. Inspection of the flowchart diagram reveals four columns. Notice that the leftmost column has only one action, "Step back one cell". This is mirrored by the rightmost column which also has only one action "Step forward one cell". The left half of the flowchart is concerned with finding a new cell value worthy of a candidacy test.
The cell order could be rows within cells or cells within rows, or any set sequence of rows. For maximum efficiency a path is selected which hopefully excludes as many pointless traverses as possible. A good candidate seems to be the herringbone path, which is the first row, followed by the rest of the first col, followed by the rest of the second row followed by the rest of the second column, ... This path has a well defined stepwise order regardless of the number of rows and columns and eliminates pointless excursions by setting up a rowcolumn framework which maximises interdependancies and then strengthens it. Using this tactic, probably the only improvement would be an alternating herringbone path which is a rather more difficult path to calculate.

The candidacy test is for whether the current symbol(cell) is valid in the context of its column, that is , is there a column in A that looks like this candidate column? The column for this cell is used as a regular expression and this pattern is sought among the columns of A. Similarly the row for this cell is used as a regular expression to search for matching rows in B. If a matching A column and a matching B row exist, then this cell is OK for now. The search proceeds until there are no matches, in which case the M matrix is unwound back down its path, or else we get to the last cell in the path which is OK, so that all cells are OK and a morphism is identified.
When the cell path has been completely unwound back to the initial cell, we know the search has been exhaustive. And very neatly, the M matrix is returned to being all "."s, and the cell pointer is returned to the first cell.
Given the table of staggering figures above, just how long does it take perform these calculations. I have run a test using a sample square matrix which I called E for no better reason than it followed on after some other test matrices called A B C and D. The E space is defined for an alphabet of size k over an n*n space. Cell E(i,j) = min { (i+j)mod n , k1 }. Note that E = E^{__} which ensures at least one function, the identity. Rows and columns of E start with all letters of the alphabet, as far as is possible, and so candidate search paths exist over a wide range of values on the search path. In particular cell E(0,0) satisfies the candidacy test for the alphabet. For k=2, E2n represents the space of n discrete points, and E2n o E2n represents the discrete topology with n! points. This explains the factorial time behaviour for k=2. For k=3, E3n represnts the points of a directed cycle of n points. E3n o E3n represents the cyclic group on the ring and also has n points.
secs  n = 2  n = 3  n = 4  n = 5  n = 6  n = 7  n = 8  n = 9  n = 10  n = 11  n = 12 

K = 2  0.011  0.051  0.29  1.9  15  180  
K = 3  0.016  0.043  0.18  0.47  1.0  2.1  4.0  6.8  11  18  27 
K = 4  0.016  0.055  0.26  0.58  1.2  2.3  4.3  7.4  12  19  29 
K = 5  0.022  0.099  0.30  0.064  1.2  2.3  4.4  7.5  12  19  29 
K = 6  0.021  0.13  0.36  0.74  1.4  2.5  4.4  7.6  12  19  29 
K = 7  0.024  0.15  0.41  0.86  1.6  3.0  5.1  7.8  12  19  30 
K = 8  0.028  0.17  0.48  1.0  1.9  3.4  5.6  8.5  13  20  29 
secs  n = 2  n = 3  n = 4  n = 5  n = 6  n = 7  n = 8  n = 9  n = 10  n = 11  n = 12 

K = 2  0.0054  0.025  0.15  1.1  8.7  115  
K = 3  0.0055  0.018  0.051  0.16  0.32  0.61  1.0  1.5  2.3  3.3  4.5 
K = 4  0.0049  0.016  0.058  0.20  0.36  0.62  0.99  1.6  2.2  3.3  4.5 
K = 5  0.0050  0.017  0.065  0.21  0.39  0.65  1.0  1.5  2.3  3.2  4.4 
K = 6  0.0050  0.016  0.059  0.20  0.40  0.67  1.0  1.5  2.3  3.3  4.4 
K = 7  0.0049  0.016  0.059  0.20  0.40  0.71  1.1  1.6  2.3  3.2  4.4 
K = 8  0.0055  0.016  0.059  0.20  0.38  0.68  1.1  1.7  2.4  3.3  4.5 
These times do not match the trends which one would expect to see in theory from Table 1 above. For K = 2 the time does indeed rise expontentially w.r.t n, but for the other k the times seem to increment O(n^{2}) at most. How do we explain this behaviour?
One answer is that E(2,n) o E(2,n) returns n! morphisms. For k>2 E(k,n)oE(k,n) has only n morphisms for n>=k, and only 1 morphism otherwise. This explains the almost linear look of the times in the table. The implication here is that deadends in the search path are dispensed with very quickly, and that the algorithm spends most of its time "rubberstamping" a candidate morphism. So the time it takes to calculate an implication is mainly dependant on the size of the answer rather than on the size of the arguments.
Simply calculating a factorial is an NPhard problem, but factorials are calculated as part of binomial coefficients and binomial probabilities all the time. The importance is not the potential size of all the possible answers, but the time it takes to get the "interesting" answers. An answer of order n! is not particularly interesting because it is just a numeric way of saying "every" combination, which is not a particularly useful result. So a more interesting question in relation to the implication algorithm is:
How long does it take to tell if there are 0 morphisms?
To this we can then add:
How long does it take to tell if there is only 1 morphism (typically the identity) and no others?
How long does it take to tell if there are only order n morphisms?
One way of addressing these issues is to first understand the nature and anatomy of morphisms. The first issue is: how many morphisms are there between two spaces? Given a space A (ka pa sa) and a space B (kb pb sb), since AoB consists of symbols that must all be in both A and B take k = min(ka,kb). The minimum number of output rows (points p) is of course 0. The maximum number is pa^{pb}. But it is possible that this can only occur for spaces which are nonunique to start with, and then perhaps only for constant spaces. The following is a table of results for AoA where A is (k , n , m ) . This is the same class of spaces as was considered in the timing section in Table 1. In this case however we are not simply enumerating them, but performing AoA on them which takes longer than 1 microsecond on my laptop. The execution time for each cell in Table 3 below is the product of the corresponding cells in Tables 1 and 2! For A(2,4) it is 65,536 * .21 secs = 3.8 hours. For A(2,5) it is 33554432*1.2secs = 15 months
k=2  m = 2  m = 3  n = 4  n = 5  n = 6 

n = 2  6 spaces nonunique 10 had 2 morphisms 
40 spaces nonunique 12 had 2 morphisms 12 had 3 morphisms 
232 spaces nonunique 24 had 4 morphisms 
ALL spaces are nonunique  
n = 3  40 spaces nonunique 12 had 2 morphisms 12 had 3 morphisms 
248 spaces nonunique 72 had 2 morphisms 72 had 3 morphisms 84 had 6 morphisms 36 had 7 morphisms 
2488 spaces nonunique 144 had 1 morphism 288 had 2 morphisms 288 had 3 morphisms 288 had 5 morphisms 168 had 6 morphisms 288 had 9 morphisms 144 had 10 morphisms 
Same as k=2 n=5 m=3 
Same as k=2 n=6 m=3 
n = 4  232 spaces nonunique 24 had 4 morphisms 
2488 spaces nonunique 144 had 1 morphism 288 had 2 morphisms 288 had 3 morphisms 288 had 5 morphisms 168 had 6 morphisms 288 had 9 morphisms 144 had 10 morphisms 
31672 spaces nonunique 3456 had 1 morphism 5184 had 2 morphisms 4608 had 3 morphisms 4752 had 4 morphisms 3456 had 5 morphisms 960 had 6 morphisms 2304 had 7 morphisms 2880 had 8 morphisms 1152 had 14 morphisms 2568 had 16 morphisms 2304 had 20 morphisms 48 had 24 morphisms 192 had 34 morphisms 
Same as k=2 n=5 m=4 

n = 5  ALL spaces nonunique  26048 spaces nonunique 1440 had 2 morphisms 1440 had 3 morphisms 1440 had 6 morphisms 240 had 9 morphisms 2160 had 11 morphisms 
564736spaces nonunique 80640 had 1 morphisms 89280 had 2 morphisms 51840 had 3 morphisms 33840 had 4 morphisms 37440 had 5 morphisms 25920 had 6 morphisms 28800 had 7 morphisms 28800 had 8 morphisms 8640 had 9 morphisms 8640 had 10 morphisms 5760 had 11 morphisms 8640 had 12 morphisms 5760 had 13 morphisms 5760 had 14 morphisms 2880 had 15 morphisms 720 had 16 morphisms 5760 had 18 morphisms 2880 had 19 morphisms 7200 had 20 morphisms 2880 had 21 morphisms 11520 had 22 morphisms 5760 had 23 morphisms 480 had 24 morphisms 5760 had 25 morphisms 5760 had 26 morphisms 5760 had 27 morphisms 2880 had 33 morphisms 2880 had 35 morphisms 960 had 37 morphisms 

n = 6  241984 spaces nonunique 4320 had 2 morphisms 5040 had 6 morphisms 4320 had 11 morphisms 4320 had 12 morphisms 2160 had 17 morphisms 

n = 7  2056832 spaces nonunique 10080 had 6 morphisms 30240 had 17 morphisms 

n = 8  
n = 9 