Transparallel processing by hyperstrings

Abstract

Human vision research aims at understanding the brain processes that enable us to see the world as a structured whole consisting of separate objects. To explain how humans organize a visual pattern, structural information theory starts from the idea that our visual system prefers the organization with the simplest descriptive code, that is, the code that captures a maximum of visual regularity. Empirically, structural information theory gained support from psychological data on a wide variety of perceptual phenomena, but theoretically, the computation of guaranteed simplest codes remained a troubling problem. Here, the graph-theoretical concept of "hyperstrings" is presented as a key to the solution of this problem. A hyperstring is a distributed data structure that allows a search for regularity in O(2(N)) strings as if only one string of length N were concerned. Thereby, hyperstrings enable transparallel processing, a previously uncharacterized form of processing that might also be a form of cognitive processing.

Fig. 1.

Suppose for the string 𝒫 = ababfabab that the regularity search has yielded simplest covering ISA-forms for the substrings of 𝒫 (only a few of these ISA-forms are shown). Then, the SPM yields S[(2*(ab)), (f)] as the simplest code of 𝒫. (Note: the number of string symbols in a code is taken to quantify its structural complexity.)

Fig. 2.

A hyperstring. The paths from vertex 1 to vertex 4 represent the same substrings as those represented by the paths from vertex 5 to vertex 8; that is, the substring sets π(1, 4) and π(5, 8) are identical.

Fig. 3.

A hyperstring that represents 13 chunkings of the string abcfabcg. Just as in Fig. 2, the substring sets π(1, 4) and π(5, 8) are identical.

Fig. 4.

The A-graph for the string T = akagakakag, with three independent hyperstrings and with, among others, identical substring sets π(1, 5) and π(7, 11).

Fig. 5.

The S-graph for the string T = ababfdedgpfdedgbaba, with two independent subgraphs. Dashed edges and bold edges represent pivots and S-chunks, respectively, in S-forms covering diafixes of T.

Fig. 6.

(a) The S-graph for the string T₁ = ababfababgbabafbaba, with, among others, identical substring sets π(1, 5) and π(6, 10). (b) The S-graph for the nearly identical string T₂ = ababfababgbabafabab, in which the substring sets π(1, 5) and π(6, 10) are disjunct.

Fig. 7.

For the hyperstring in the S-graph from Fig. 6a, with T₁ = ababfababgbabafbaba, the hierarchically recursive regularity search yields simplest covering ISA-forms for the hypersubstrings (only a few of these ISA-forms are shown). By including the pivots, the all-pairs SPM then yields simplest covering S-forms for the diafixes of T₁ (only a few of these S-forms are shown). Note that the number of string symbols in a code is taken to quantify its structural complexity, and for clarity the substrings aba and bab inside chunks are shown uncoded but should be read as S[(a), (b)] and S[(b), (a)], respectively.