Let \(K\)  be the set of all possible labels of the end points, in the labeled graph produced at the output
of each node in the parse tree. We refer to elements of \(K\)  as types. Note that every \(M\)  consists of at
most \(|K|\)  distinct types and \(F(X)\)  has at most \({(n + 1)}^{|K|}\)  distinct multisets each with at
most \(n\)  multisets of size 2.
Here \(K = K_0 \uplus K_1 \uplus K_2\)  is the set of distinct
types where \(K_2\)  accounts for types of the
form \(\langle i,j\rangle \)  (for \(i \ne j\) ) corresponds to paths whose end points are
\(i\)  and \(j\) ; \(K_0\)  for the empty type \(\langle \rangle = \emptyset \)  corresponds to a cycle;
\(K_1\)  for types of the form \(\langle i, i \rangle \)  which could be either
paths whose end points are both labeled \(i\) , or isolated vertices with the label
\(i\) . Observe that, \(|K_2| = \binom{k}{2}\) , \(K_1 = 2k\)  and \(K_0 = 1\) , where we
distinguish between the cases of single isolated vertex of label \(i\)  and multiple
vertex paths with end points labeled \(i\)  for technical reasons, leading to the extra
factor of 2. Our notation is consistent with [1]} in all cases except for
the empty type, since in [1]} cycles are not permitted.
