Searching in Rhizomes
In this post I will look into how it is possible to search in rhizomes. I will assume that the rhizome implementation relies on pairing functions to store relations. I described the basic necessary data structures in a previous post. The term “searching in a rhizome” is not defined precisely. Searching implies that some contextual order is given and that the search is conducted in relation to this order. For rhizomes (similar to graphs) it is not entirely clear what constitutes this contextual order, the the definition of contextual order might depend upon one’s situation.
Let us begin with a simple example and gradually continue to more complicated ones. First, let us assume we want to know whether a relation between the atomic symbols A and B exists. We can create the two relations (A, B) and (B, A), look up the terminal relations for A and B and reduce them to their final z-pairing values.
r(A, B) <= ((0, 0), (1, 1)) = (0, 3) = 9r(B, A) <= ((1, 1), (0, 0)) = (3, 0) = 12
Next, we simply look up each z-pairing values 9 and 12 in the hashmap of pairings. If there exists such a value, then the corresponding relation has been stored. One should note that the search can easily be parallelized.
Another example. This time we will look for a string of three atomic symbols, A, B and C. For the sake of the example, let us assume we know the ordering of the symbols from left to right (A followed by B followed by C), but not their nesting. In this situation, two different possible pairings exist: ((A, B), C) and (A, (B, C)). We compute all possible nestings, replace the atomic symbols with terminal relations, reduce them to their z-pairing values and look them up in the hashmap. We can then determine which nestings actually exist. If none does then the ordered string ABC has not been stored. If we were only interested in the question if at least one nesting exists, but would not care which nesting this were, then we could immediately stop computation after we found the first one. Again, the whole process can be parallelized easily.
The situation becomes more complicated if we cannot guarantee the order between A, B and C. Basically, we need to compute all possible orders and nestings and then look them up individually. These are all possible orderings and nestings:
((A, B), C),(A, (B, C)),((A, C), B),(A, (C, B)),((B, A), C),(B, (A, C)),((B, C), A),(B, (C, A)),((C, A), B),(C, (A, B)),((C, B), A),(C, (B, A))
Fortunately, it is possible to memoize in-between results. Some relations are shared, for example (A, B) is part of both ((A, B), C) and (C, (A, B)). If (A, B) does not exist, we can immediately stop computation for both cases and conclude that neither of these two more complex relations exist. We only need to compute all z-pairing values if none of the listed relations exists.
What if we do not only want to know if a relation actually exists but also where it is stored? As I mentioned further above as long as no clearly defined contextual order is given this is impossible to answer. A rhizome has no inherent order or indexing scheme. The term “where” is not defined. What is possible to answer though is questions of the type: Does the relation represented by z-pairing value z contain the relation (A, B)? We simply need to expand the relator rz to its relata and continue down the rhizome tree recursively. If anywhere in the chain the relation (A, B) is found the answer is yes.