Hyperstrings

A hyperstring is a special kind of distributed representation. It allows for transparallel processing, that is, it enables a search for regularity in up to 2^N strings as if only one string of length N were concerned. See Hyperstring proofs for the formal definition of a hyperstring; here, this concept may be illustrated as follows.

In the next figure, the 15 separate strings at the top are gathered in a distributed representation on 9 vertices. Every path from vertex 1 to vertex 9 represents one of the 15 strings, by way of the edge labels in such a path. For instance, the path along vertices 1, 2, 4, 5, and 9, represents the string ayfw.




This distributed representation is a hyperstring, which in graph-theoretical terms, is defined as a simple semi-Hamiltonian directed acyclic graph. A hyperstring contains one and only one Hamilton path, that is, one and only one path that visits every vertex, and it is characterized by the following crucial property:

• the set of strings represented by all paths between one pair of vertices and the set of strings represented by all paths between another pair of vertices are either completely disjunct or completely identical -- never something in between.

For instance, as indicated in red in the figure above, the set of strings represented by all paths from vertex 1 to vertex 4 is identical to the set of strings represented by all paths from vertex 5 to vertex 8.

Because of this crucial property, the hyperstring can be conceived of as one string in which each substring stands for such a set of all paths between two vertices. Any identity relationship between substrings in one of the 15 strings corresponds to an identity relationship between substrings in this single string. Inversely, any identity relationship between substrings in this single string corresponds, in one go, to identity relationships between substrings in many of the 15 strings. This implies that a search for regularity in this single string suffices to get all regularities in all 15 strings.

The foregoing finds application in the computation of minimal codes of strings, which requires a hierarchically recursive search for regularities. For instance, in the next figure, the string at the top can be encoded into 9 different symmetries. To compute a minimal code of the string at the top, the arguments of all these 9 symmetries have to be recoded in turn. At first glance, it seems necessary to encode each of the 9 symmetry arguments separately. However, the 9 symmetry arguments can be gathered in a distributed representation which, by nature, forms a hyperstring (see Hyperstring proofs). This implies that all 9 symmetry arguments can be recoded in a transparallel fashion, that is, as if only one symmetry argument were concerned.




For a full account of transparallel processing by hyperstrings, see Proceedings of the National Academy of Sciences USA 2004
For a demo on its position with respect to other forms of processing, see Smart processing
For a demo on its potential relevance in cognitive (neuro)science, see Cognitive architecture
For an extensive discussion on these issues, see Cognitive Processing 2012

For a natural example of transparallel processing without hyperstrings, see Pencil selection