The number of strings of depth d (and thus taking d steps to annihilate completely) is given by c[{n, n}, d] - c[{n, n}, d - 1] where c[{_, _}, -1] = 0; c[{0, 0}, _] = 1; c[{m_, n_}, _] := 0 /; n > m; c[{m_, n_}, d_] := Sum[c[{i, j}, d], {i, 0, m - 1}, {j, m - d, n - 1}] Several types of structures are equivalent to strings of balanced parentheses, as illustrated below.

With rules set up in this way, each step in the evolution of a network system is given by NetEvolveStep[{depth_Integer, rule_List}, list_List] := Block[ {new = {}}, Join[Table[Map[NetEvolveStep1[#, list, i] &, Replace[NeighborNumbers[list, i, depth], rule]], {i, Length[list]}], new]] NetEvolveStep1[s : {___Integer}, list_, i_] := Follow[list, i, s] NetEvolveStep1[{s1 : {___Integer}, s2 : {___Integer}}, list_, i_] := Length[list] + Length[ AppendTo[new, {Follow[list, i, s1], Follow[list, i, s2]}]] The set of nodes that can be reached from node i is given by ConnectedNodes[list_, i_] := FixedPoint[Union[Flatten[{#, list 〚 # 〛 }]] &, {i}] and disconnected nodes can be removed using RenumberNodes[list_, seq_] := Map[Position[seq, #] 〚 1, 1 〛 &, list 〚 seq 〛 , {2}] The sequence of networks obtained on successive steps by applying the rules and then removing all nodes not connected to node number 1 is given by NetEvolveList[rule_, init_, t_Integer] := NestList[(RenumberNodes[#, ConnectedNodes[#, 1]] &)[ NetEvolveStep[rule, #]] &, init, t] Note that the nodes in each network are not necessarily numbered in the order that they appear on successive lines in the pictures in the main text.

If one wants to find just a single initial condition that works then one can set up a recursive algorithm that in effect does a depth-first traversal of the tree.

(Such trees have been studied since at least the early 1900s, with typical examples of concepts being Horton stream order, equal to Depth for trees given as Mathematica expressions.)

Minimization of Boolean expressions with depth larger than 2 has been considered off and on since the late 1950s, and became popular in the 1990s in connection with the BDDs discussed above.

Nand expressions If one allows a depth of at most 2n any n -input Boolean function can be obtained just by combining 2-input Nand functions.

To emulate cellular automaton evolution one starts by encoding a list of cell values by the single combinator p[num[Length[list]]][ Fold[p[Nest[s, k, #2]][#1] &, p[k][k], list]] //. crules where num[n_] := Nest[inc, s[k], n] inc = s[s[k[s]][k]] One can recover the original list by using Extract[expr, Map[Reverse[IntegerDigits[#, 2]] &, 3 + 59(16^Range[Depth[expr[s[k]][s][k] //. crules] - 1, 1, -1] - 1)/ 15)]]/.

The total lengths of these chains (corresponding to the depth of the evaluation tree) seem to increase roughly like Log[n] for all the rules on this page.

The maximum number of levels in these expressions (see page 897 ) grows roughly linearly, although Depth[expr] reaches 14 after 26 and 25 steps, then stays there.

One attempt at an abstract definition was what Charles Bennett called logical depth: the number of computational steps needed to reproduce something from its shortest description.