the subset diagram

  

Figure: Since the de Bruijn diagram of a (3,1/2) automaton has three vertices, the subset diagram has eight vertices, ranked at four levels according to the size of the subset.

The vertices in the subset diagram are subsets of de Bruijn vertices. Each source subset is linked to the union of all the destinations of its elements. If there are no destinations for a given label, linkage goes to the empty set.

It is useful to introduce some symbolism to express these ideas, anticipating the eventual complexity of the constructions.

• link(i,j) A predicate, true when there is a link from i to j, a phraseology which inverts colloquial english usage somewhat.
• link(i) The set of all nodes to which the node i is linked:
  

  $${\rm link}(i) \left\{ j \vert {\rm link}(i,j)\right\}$$ = (42)

  
  

• LINK(S) The set of all nodes in the de Bruijn diagram to which nodes in from the subset S are linked:
  

  $${\rm LINK(S)} \bigcup_{i\varepsilon S} {\rm link}(i)$$ = (43)

  
  
  Also note the interchangeability of points and their unit classes, lapsing from strict set theoretic syntax.

Having made these prearrangements, it is easier to connect the nodes in the subset diagram, using the word LINK instead of link because of the profusion of linkages that have to be dealt with. When suitable graphic facilities exist, such as when drawing the diagrams by hand, it is convenient to represent link linkages by thin arrows running between points, and LINK linkages by fat arrows running between subsets.

That is the reason for introducing a case-sensitive nomenclature which is more common in computer programming than in mathematical expositions. Following these precepts, it is time to define the linkage predicate for the subset diagram:

$${\rm LINK}(U,V) \equiv V = \bigcup_{u\varepsilon U}{\rm NEXT}(u)$$ (44)

A detail which should be observed in this definition, which to a certain extent captures the essence of the subset diagram, is that there is one and only one set which can be called ${\rm LINK}(U)$. There is one because in the worst case it is the empty set, and only one because of he insistence that it is the maximum set to which interelement connections via NEXT can be formed. Consequently,

$${\rm LINK}(U) \bigcup_{u\varepsilon U}{\rm link}(u)$$ = (45)

Leaves in the subset diagram have no incoming arrows, which could be a consequence of all the points in that node being leaves themselves; but it could also result from a lack of saturation. In other words, its points could have incoming arrows, emanating from sources which have additional destinations lying in some other subset.

Rootlets would have no outgoing links, which is impossible because such nodes would be connected to the empty set. But it is still possible to ask what kind has the empty set as its destination (which would have to be unique). Evidently unions of rootlets would be rootlets, just as unions of leaves would be leaves. Unlike the situation with leaves, however, there are no fat rootlets composed of anything other than thin rootlets.