Multilevel [Boolean] formulas DNF formulas always have depth 2. … A formula of polynomial size and logarithmic depth exists only when a function is the computational complexity class NC discussed on page 1149 . … And this for example allows SIS to generate higher depth formulas somewhat smaller than the minimal DNF for the first three steps of rule 30 evolution.

Rule structure [for network systems] For depth 1, the possible results from NeighborNumbers are {1} and {2} . For depth 2, they are {1, 1} , {1, 2} , {2, 1} , {2, 2} , {2, 3} and {2, 4} .

How the minimal size or depth of circuit needed grows with input size then gives a measure of the difficulty of the computation, with circuit depth growing roughly like number of steps for a Turing machine.

The depth of this inner part for initial condition ℯ [ ℯ ][ ℯ ][ ℯ ][ ℯ ][ ℯ ] is shown below. For all initial conditions this depth seems at first to increase linearly, then to decrease in a nested way according to FoldList[Plus, 0, Flatten[Table[ {1, 1, Table[-1, {IntegerExponent[i, 2] + 1}]}, {i, m}]]] This quantity alternates between value 1 at position 2 j and value j at position 2 j - j + 1 . It reaches a fixed point as soon as the depth reaches 0.

When n is even, the structure is a balanced tree of depth 2^IntegerExponent[n, 2] and degree 2 for rule 60, and depth 2^IntegerExponent[n/2, 2] and degree 4 for rule 90.

If there is a tree of possible replacements (as in "A"  "AA" ), then the sequential substitution system in a sense does depth-first recursion in the infinite tree, never returning from the single path it takes.

DNF and CNF both involve Boolean formulas of depth 2. As in the note on multilevel formulas below, one can also in effect introduce intermediate variables to get recursive formulas of larger depth, somewhat analogous to results from Collect .

On the right-hand edge, the first few periods that are seen are {1, 2, 2, 4, 8, 8, 16, 32, 32, 64, 64, 64, 64, 64, 128, 256} and in general the period seems to increase exponentially with depth. On the left-hand edge, the period increases only extremely slowly: period 2 is first achieved at depth 3, period 4 at depth 8, 8 at 29, 16 at 400, 32 at 87,867, 64 at 2,107,985,255 or more, and so on.

Higher-dimensional generalizations [of substitution systems] The state of a d -dimensional substitution system can be represented by a nested list of depth d .

[Enumerating] possible expressions LeafCount[expr] gives the number of symbols that appear anywhere in an expression, while Depth[expr] gives the number of closing brackets at the end of its functional representation—equal to the number of levels in the rightmost branch of the tree representation.