Index-Period Normal Forms for Monoid-Aggregated Recursive Summaries

A rooted cop-labeled tree is a finite rooted unordered tree T with root \rho_T together with a multiplicity function

m_T : V(T) \to \mathbb{N}.

Sibling order is not part of the structure.

A rooted one-hole context K[\square] is a finite rooted cop-labeled tree with one distinguished subtree slot. If X is a rooted cop-labeled tree, then K[X] is obtained by plugging X into the slot. Contexts compose, and the empty context is E[\square] = \square.

A finite resource datum is a tuple

\mathcal{R} = (A, \mu, S, M, \oplus, 0_M)

where:

1. A is a finite multiplicity alphabet;
2. \mu : \mathbb{N} \to A is a fixed multiplicity observation map;
3. S is a finite state set;
4. (M, \oplus, 0_M) is a finite commutative monoid.

For the clean fixed-resource theory, \mu and (M, \oplus, 0_M) are part of the resource datum. Fixing only |A| would allow infinitely many exact multiplicity tests by varying \mu. Fixing only |M| still leaves only finitely many monoid structures on a fixed finite set, but the pumping constants depend on the actual operation. Therefore all sharp statements below are parametrized by the actual resource datum \mathcal{R}.

A monoid-aggregated summary over \mathcal{R} is a pair

P = (\alpha_P, f_P)

with

\alpha_P : S \to M, \qquad f_P : A \times M \to S.

It evaluates a rooted tree bottom-up by

P(T_v) = f_P\!\left( \mu(m_T(v)),\; \bigoplus_{u \text{ child of } v} \alpha_P(P(T_u)) \right),

where the empty sum is 0_M. The root value is denoted P(T).

Let D(\mathcal{R}) be the finite class of all monoid-aggregated summaries over \mathcal{R}.

The number of syntactic summaries over \mathcal{R} is

|D(\mathcal{R})| = |M|^{|S|} \cdot |S|^{|A||M|},

where equality means syntactic equality of pairs (\alpha, f). The number of extensionally distinct summaries is at most this quantity.

The \mathcal{R}-behavior vector of a tree T is

\beta_{\mathcal{R}}(T) = (P(T))_{P \in D(\mathcal{R})} \in S^{D(\mathcal{R})}.

We write

B_{\mathcal{R}} := S^{D(\mathcal{R})}

for the finite set of formal behavior vectors. A vector b \in B_{\mathcal{R}} is realizable if b = \beta_{\mathcal{R}}(T) for some tree T.

For rooted cop-labeled trees X, Y, define

X \sim_{\mathcal{R}} Y

if for every rooted one-hole context K[\square] and every summary P \in D(\mathcal{R}),

P(K[X]) = P(K[Y]).

For all rooted cop-labeled trees X, Y,

X \sim_{\mathcal{R}} Y \iff \beta_{\mathcal{R}}(X) = \beta_{\mathcal{R}}(Y).

Consequently \sim_{\mathcal{R}} has finite index, with at most |S|^{|D(\mathcal{R})|} classes.

In this note a behavior type means an element of B_{\mathcal{R}}, usually a realizable one. Two trees have the same behavior type exactly when they are \sim_{\mathcal{R}}-equivalent.

If X \sim_{\mathcal{R}} Y, then for every rooted one-hole context K[\square],

K[X] \sim_{\mathcal{R}} K[Y].

Equivalently, replacing a subtree by another subtree with the same \mathcal{R}-behavior vector preserves the \mathcal{R}-behavior vector of the whole tree.

Let M^{D(\mathcal{R})} denote the product monoid of D(\mathcal{R}) copies of M — equivalently, the set of functions D(\mathcal{R}) \to M — with coordinatewise operation, also denoted \oplus, and zero element (0_M)_{P \in D(\mathcal{R})}.

For a formal behavior vector

b = (b_P)_{P \in D(\mathcal{R})} \in B_{\mathcal{R}},

define its product contribution element

\gamma_b \in M^{D(\mathcal{R})}

by

(\gamma_b)_P := \alpha_P(b_P).

Thus \gamma_b is the simultaneous child contribution made by a child subtree of behavior type b to every summary P \in D(\mathcal{R}). This definition also makes sense for formal, non-realizable behavior vectors; only realizable vectors occur as actual child types in trees.

The symbols used below are as follows: B_{\mathcal{R}} = S^{D(\mathcal{R})} is the set of formal behavior vectors; M^{D(\mathcal{R})} is the product contribution monoid; \gamma_b \in M^{D(\mathcal{R})} is the contribution element of a behavior type b; \operatorname{ind}(\gamma_b) and \operatorname{per}(\gamma_b) are computed inside M^{D(\mathcal{R})}; and N_{\mathcal{R}}(b) = \operatorname{ind}(\gamma_b) + \operatorname{per}(\gamma_b) - 1 is the exact per-type sibling bound.

Let a node have child behavior-type multiplicities

(n_b)_{b \in B_{\mathcal{R}}},

with all but finitely many n_b zero. Then the simultaneous child aggregate seen by all summaries is

\Gamma := \bigoplus_{b \in B_{\mathcal{R}}} n_b \gamma_b \in M^{D(\mathcal{R})}.

The P-coordinate of \Gamma is exactly

\bigoplus_{u \text{ child}} \alpha_P(P(T_u)),

the aggregate used by P at the parent.

Let (N, +, 0_N) be a finite monoid and let g \in N. The sequence

0g,\; 1g,\; 2g,\; 3g,\; \ldots

is eventually periodic. Define \operatorname{ind}_N(g) to be the least i \geq 0 for which there exists a p \geq 1 such that

(n+p)g = ng \quad \text{for all } n \geq i.

Given this least index, define \operatorname{per}_N(g) to be the least such positive period p. When N is clear, write simply \operatorname{ind}(g) and \operatorname{per}(g). This is the least-index-then-least-period convention; other equivalent conventions are possible, but this one is fixed throughout the note.

For every element g of a finite monoid N, \operatorname{ind}(g) and \operatorname{per}(g) exist. Moreover

\operatorname{ind}(g) + \operatorname{per}(g) \leq |N|.

Equivalently, the exact contribution bound satisfies \operatorname{ind}(g) + \operatorname{per}(g) - 1 \leq |N| - 1.

Let g \in N, and put

i = \operatorname{ind}(g), \quad p = \operatorname{per}(g).

Define

\operatorname{red}_g(n) = \begin{cases} n, & n < i, \\ i + ((n-i) \bmod p), & n \geq i. \end{cases}

Then 0 \leq \operatorname{red}_g(n) \leq i + p - 1.

For every n \geq 0,

ng = \operatorname{red}_g(n)\, g.

Moreover \operatorname{red}_g(n) \leq n, and if n > \operatorname{ind}(g) + \operatorname{per}(g) - 1, then \operatorname{red}_g(n) < n.

For g \in N, define

N(g) := \operatorname{ind}(g) + \operatorname{per}(g) - 1.

The exact pumping lemma says every coefficient of g can be reduced to at most N(g) without changing the monoid value.

For a behavior type b \in B_{\mathcal{R}}, its sibling signature is

\sigma_{\mathcal{R}}(b) := \bigl(\operatorname{ind}(\gamma_b), \operatorname{per}(\gamma_b)\bigr),

computed inside the product monoid M^{D(\mathcal{R})}. Its exact sibling bound is

N_{\mathcal{R}}(b) := \operatorname{ind}(\gamma_b) + \operatorname{per}(\gamma_b) - 1.

A uniform exact sibling bound is

N^{\max}_{\mathcal{R}} := \max_{b \in B_{\mathcal{R}}} N_{\mathcal{R}}(b).

Let a node have child behavior-type multiplicities (n_b)_{b \in B_{\mathcal{R}}}. For each b, set

n'_b := \operatorname{red}_{\gamma_b}(n_b).

Replace the child multiset by one having exactly n'_b children of behavior type b for every b, using any available representatives of those behavior types. Then the simultaneous child aggregate in M^{D(\mathcal{R})} is unchanged. Consequently, if the node’s observed multiplicity label is unchanged, then its parent behavior vector is unchanged.

Every sibling multiset is equivalent, as seen by all summaries in D(\mathcal{R}), to one in which each behavior type b occurs at most

N_{\mathcal{R}}(b) = \operatorname{ind}(\gamma_b) + \operatorname{per}(\gamma_b) - 1

times. In particular, the total number of children after exact sibling normalization is at most

C_{\mathcal{R}} := \sum_{b \in B_{\mathcal{R}}} N_{\mathcal{R}}(b) \leq |B_{\mathcal{R}}| \cdot N^{\max}_{\mathcal{R}}.

The bounds may be sharpened by taking b only over realizable behavior vectors. The present statement uses all formal b \in B_{\mathcal{R}} to avoid introducing a separate realizability analysis. Note that realizability of behavior vectors is defined existentially over all trees and is not in general algorithmically transparent, so the formal-version bounds are also the practically computable ones.

Let M = (\{0, 1\}, \vee, 0). Then for g = 0,

\operatorname{ind}(g) = 0, \quad \operatorname{per}(g) = 1, \quad N(g) = 0,

and for g = 1,

\operatorname{ind}(g) = 1, \quad \operatorname{per}(g) = 1, \quad N(g) = 1.

Thus a nonzero child contribution is remembered only by presence or absence.

If M is a finite Boolean semilattice, for example a finite power of (\{0, 1\}, \vee, 0), every element is idempotent. Hence every behavior type has bound 0 if its contribution is zero and bound 1 otherwise.

Let M = \mathbb{Z}/q\mathbb{Z} under addition. For g \in M,

\operatorname{ind}(g) = 0, \quad \operatorname{per}(g) = \operatorname{ord}(g) = \frac{q}{\gcd(q, g)},

with the convention that \operatorname{ord}(0) = 1. Thus

N(g) = \operatorname{ord}(g) - 1.

If M is a finite abelian group and g \in M, then

\operatorname{ind}(g) = 0, \quad \operatorname{per}(g) = \operatorname{ord}(g), \quad N(g) = \operatorname{ord}(g) - 1.

For a product element g = (g_i), \operatorname{ord}(g) is the least common multiple of the coordinate orders.

For T \geq 0, let

\Theta_T := \{0, 1, \ldots, T\}

with operation

x \oplus y := \min(T, x + y)

and identity 0.

Let M = \Theta_T. If g = 0, then \operatorname{ind}(g) = 0, \operatorname{per}(g) = 1, and N(g) = 0. If 1 \leq g \leq T, then

\operatorname{ind}(g) = \lceil T/g \rceil, \quad \operatorname{per}(g) = 1, \quad N(g) = \lceil T/g \rceil.

Threshold monoids show why arbitrary finite commutative monoids cannot be treated as semilattices of abelian groups. In \Theta_2, the element 1 has the sequence 0, 1, 2, 2, 2, \ldots; this has a genuine preperiod and no group-like cycle before saturation.

Let

M = \Theta_T \times \mathbb{Z}/q\mathbb{Z}

with coordinatewise operation, and let g = (g_{\text{thr}}, g_{\text{cyc}}). Then

\operatorname{ind}(g) = \begin{cases} 0, & g_{\text{thr}} = 0, \\ \lceil T/g_{\text{thr}} \rceil, & g_{\text{thr}} > 0, \end{cases}

and

\operatorname{per}(g) = \operatorname{ord}(g_{\text{cyc}}).

Consequently

N(g) = \operatorname{ind}(g) + \operatorname{per}(g) - 1.

Let N = N_1 \times \cdots \times N_r be a product of finite monoids and let g = (g_1, \ldots, g_r). If i_j = \operatorname{ind}(g_j) and p_j = \operatorname{per}(g_j), then a valid index-period pair for g is

i = \max_j i_j, \quad p = \operatorname{lcm}_j p_j.

Thus

N(g) \leq \max_j i_j + \operatorname{lcm}_j p_j - 1.

For fixed \mathcal{R}, if

\mu(n) = \mu(m),

then

A_n \sim_{\mathcal{R}} A_m.

Conversely, if \mu(n) \neq \mu(m) and |S| \geq 2, then A_n and A_m are separated by some summary in D(\mathcal{R}).

For fixed a and Q, if

n \gamma_b = m \gamma_b

in the product monoid M^{D(\mathcal{R})}, then

\mathrm{Star}_n(a; Q) \sim_{\mathcal{R}} \mathrm{Star}_m(a; Q).

More generally, the two stars have the same behavior vector exactly when, for every summary P \in D(\mathcal{R}),

f_P(a, n \alpha_P(b_P)) = f_P(a, m \alpha_P(b_P)).

The implication from product-aggregate equality to star equivalence is the one needed for pumping and normal forms. It is not generally necessary: two different aggregates may be identified by all root update maps at the observed label a for the summaries under discussion. In particular examples one can often force separation by choosing a summary whose update map distinguishes the two aggregates, but the exact statement is the displayed coordinatewise criterion.

Assume unit contribution \gamma_b = g.

1. Boolean support: all positive n are equivalent; n = 0 is separate from n > 0 if g \neq 0.
2. Cyclic \mathbb{Z}/q\mathbb{Z}: n and m are equivalent exactly modulo \operatorname{ord}(g).
3. Threshold \Theta_T with g = 1: n and m are equivalent iff either n = m < T or both n, m \geq T.

For each observed multiplicity label a \in A, define

U_a : B_{\mathcal{R}} \to B_{\mathcal{R}}

by declaring U_a(b) to be the behavior vector of a new root with observed label a and exactly one child of behavior type b. Coordinatewise,

(U_a(b))_P = f_P(a, \alpha_P(b_P)).

Fix a \in A and b \in B_{\mathcal{R}}. The sequence

b,\; U_a(b),\; U_a^2(b),\; U_a^3(b),\; \ldots

is eventually periodic. In particular, among the first |B_{\mathcal{R}}| + 1 terms two are equal.

Any sufficiently long constant-label unary chain contains a proper subchain whose deletion preserves the behavior vector at the top of the chain. A crude bound is |B_{\mathcal{R}}| + 1 vertices for a repeated behavior vector.

If labels vary along a unary path, one obtains the finite transformation semigroup generated by the maps U_a for a \in A: this is the subsemigroup, under composition, of the finite monoid of all self-maps of B_{\mathcal{R}} generated by the maps U_a. Long labeled unary words can be pumped using repetitions in this finite transformation semigroup, but the minimal-representative argument in Section 9 gives a simpler global height bound for entire trees.

Suppose two trees have the same observed root label a. One has child multiset consisting of two children of behavior type b, and the other has one child of behavior type c. Their root behavior vectors are equal exactly when, for every P \in D(\mathcal{R}),

f_P(a, 2\alpha_P(b_P)) = f_P(a, \alpha_P(c_P)).

Equivalently, equality follows from the stronger aggregate identity

2 \gamma_b = \gamma_c

in M^{D(\mathcal{R})}, but may also occur accidentally because all update maps in question identify the two aggregates at label a.

The stronger aggregate identity 2\gamma_b = \gamma_c is a clean sufficient condition for equality of the two root behavior vectors. Its failure is not, by itself, a clean separation theorem. The behavior coordinates b_P, c_P of the child subtrees are fixed properties of those subtrees, indexed by every P \in D(\mathcal{R}). If a particular coordinate P^* witnesses aggregate inequality in M^{D(\mathcal{R})}, the summary P^* itself may still fail to separate the parents because f_{P^*} may identify the two aggregates. One cannot remedy this by “switching to a different f” while holding the child contributions fixed: choosing a different summary P' means looking at a different coordinate P' of the child behavior vectors, with potentially different aggregate values. Thus separation should be checked by the exact coordinatewise criterion in Proposition 8.2 and Proposition 8.9, not by aggregate inequality alone. This is precisely why split-versus-concentrated examples are diagnostically interesting rather than trivial.

This is the first family where horizontal aggregation interacts with vertical recursion. It is a natural bridge to later pursuit-evasion questions about whether support is split across branches or concentrated inside one branch.

Choose once and for all a representative integer r(a) \in \mathbb{N} for each a \in A with \mu(r(a)) = a, for every a in the image of \mu. No representative is needed for a \notin \operatorname{im}(\mu), since no vertex of any tree has observed label a. A tree is label-normalized if every vertex with observed label a has actual multiplicity r(a).

Every tree T is \sim_{\mathcal{R}}-equivalent to a label-normalized tree T^{\ell} with the same underlying rooted unordered tree and the same observed labels.

A tree T is size-minimal for its behavior vector if among all trees T' with \beta_{\mathcal{R}}(T') = \beta_{\mathcal{R}}(T), the number of vertices of T' is minimized. It is normalized size-minimal if it is also label-normalized.

Every realizable behavior vector has a normalized size-minimal representative.

Let T be a normalized size-minimal representative. At every node v of T, each child behavior type b occurs at most

N_{\mathcal{R}}(b) = \operatorname{ind}(\gamma_b) + \operatorname{per}(\gamma_b) - 1

times.

Let T be a normalized size-minimal representative. No root-to-leaf path of T contains two distinct vertices u and v, with v a proper descendant of u, such that

\beta_{\mathcal{R}}(T_u) = \beta_{\mathcal{R}}(T_v).

Consequently every root-to-leaf path has at most |B_{\mathcal{R}}| vertices.

Let U_{\mathcal{R}} be the finite set of all label-normalized rooted cop-labeled trees satisfying:

1. every root-to-leaf path has at most |B_{\mathcal{R}}| vertices;
2. at every node, behavior type b occurs among the children at most N_{\mathcal{R}}(b) times, for every b \in B_{\mathcal{R}}.

One may replace |B_{\mathcal{R}}| and the sum over all formal b \in B_{\mathcal{R}} by the corresponding quantities for realizable behavior vectors. The formal version is cruder but avoids a separate realizability computation. Since realizability is defined existentially over all trees and is not in general algorithmically transparent, the formal version is also the version most directly usable in computations.

Every \sim_{\mathcal{R}}-equivalence class has a representative in the finite universe U_{\mathcal{R}}.

Let

H_{\mathcal{R}} := |B_{\mathcal{R}}|, \quad C_{\mathcal{R}} := \sum_{b \in B_{\mathcal{R}}} N_{\mathcal{R}}(b).

Then every class has a representative with at most

1 + C_{\mathcal{R}} + C_{\mathcal{R}}^2 + \cdots + C_{\mathcal{R}}^{H_{\mathcal{R}} - 1}

vertices, with the usual interpretation as H_{\mathcal{R}} when C_{\mathcal{R}} = 1.

Fix a total order \preceq on the finite universe U_{\mathcal{R}}. For example, order first by number of vertices, then by height, then recursively by sorted child lists and vertex labels.

For a realizable behavior vector b, define

\operatorname{Can}_{\mathcal{R}}(b)

to be the \preceq-least tree in U_{\mathcal{R}} with behavior vector b.

After choosing the external order \preceq, every \sim_{\mathcal{R}}-equivalence class has a unique selected canonical representative.

The theorem does not claim that each class has a unique minimal tree in any intrinsic sense. Different non-isomorphic trees of the same size may realize the same behavior vector. The uniqueness is selected uniqueness after a chosen tie-breaking order.