Bird's array notation

Bird's array notation is a googological notation invented by Chris Bird.Chris Bird's Super Huge Numbers It is an extension of Jonathan Bowers' Extended Array Notation, and is akin to BEAF both in its history and its definition. 
== "Simple" arrays ==
=== Linear and multidimensional arrays ===
For linear and multidimensional arrays, BAN is the same as BEAF.
*Rule 1. With one or two entries, we have \(\{a\} = a\), \(\{a,b\} = a^b\) (by the way, \(\lbrace a \rbrace = a\) follows from \(\{a,b\} = a^b\), since \(\{a\} = \{a,1\} = a^1 = a\) (inverse of rule 2)).
*Rule 2. If the last entry is 1, it can be removed: \(\{\# 1\} = \{\#\}\). (The octothorpe indicates the unchanged remainder of the array.)
*Rule 3. If the second entry is 1, the value is just the first entry: \(\{a,1 \#\} = a\).
*Rule 4. If the third entry is 1:
*:\(\{a,b,1,1,\cdots,1,1,c \#\} = \{a,a,a,a,\cdots,a,\{a,b-1,1,1,\cdots,1,1,c \#\},c-1 \#\}\)
*Rule 5. Otherwise:
*:\(\{a,b,c \#\} = \{a,\{a,b-1,c \#\},c-1 \#\}\)
With multidimensional arrays, Bird uses \(\textrm` a \langle c \rangle b \textrm'\), which is equivalent to Bowers' \(b^c \& a\). These strings are written within the quote signs and have their own specific rules:
*Rule A1. If \(c = 0\), we have \(\textrm` a \langle 0 \rangle b = a \textrm'\).
*Rule A2. If \(b = 1\), we have \(\textrm` a \langle c \rangle 1 = a \textrm'\).
*Rule A3. Otherwise, \(\textrm` a \langle c \rangle b \textrm' = \textrm` a \langle c - 1 \rangle b [c] a \langle c \rangle (b - 1) \textrm'\).
The main rules are:
* Rule M1. If there are only two entries, \(\{a, b\} = a^b\).
* Rule M2. If \(m < n\), we have \(\{\# [m] 1 [n] \#*\} = \{\# [n] \#*\}\). Also, \(\{\# [a] 1\} = \{\#\}\).
* Rule M3. If the second entry is 1, we have \(\{a,1 \#\} = a\).
* Rule M4. If \(m_1 \geq 2\) and \(m_1 \geq \cdots \geq m_x\), we have \(\{a,b [m_1] 1 [m_2] \cdots 1 [m_x] c \#\} = \{a \langle m_1-1 \rangle b [m_1] a \langle m_2-1 \rangle b [m_2] \cdots a \langle m_x-1 \rangle b [m_x] (c-1) \#\}\)
* Rule M5. If \(m_1 \geq \cdots \geq m_x \geq 2\), \(\{a,b [m_1] 1 [m_2] \cdots 1 [m_x] 1,c \#\} =\)
\(\{a \langle m_1-1 \rangle b [m_1] a \langle m_2-1 \rangle b [m_2] \cdots a \langle m_x-1 \rangle b [m_x] \{a,b-1 [m_1] 1 [m_2] \cdots 1 [m_x] 1,c \#\},c-1 \#\}\)
* Rule M6. Rules M1-M5 don't apply.
*:\(\{a,b,c \#\} = \{a,\{a,b-1,c \#\},c-1 \#\}\)
For example, \(\{3,3 [3] 1 [2] 1,1,1,4\}\) = \(\{3 \langle 2 \rangle 3 [3] 3 \langle 1 \rangle 3 [2] 3,3,\{3,2 [3] 1 [2] 1,1,1,4\},3\}\)
Bird uses \([m]\) as a dimensional separator; in Bowers' notation it is equivalent to an \((m - 1)\) separator. This resolves a minor issue in BEAF, where ones are default in the array and zeroes are default in the separators. Meaning that if in BEAF, if an expression is {a,b(n)c}, then in Bird's array notation, this is equal to {a,b[n+1]c}.
For example: if the BEAF expression is {10,10(2)2} then we say that it's equal to {10,10[3]2} in BAN.
In the fast-growing hierarchy, functions which diagonalize over linear and multidimensional array notations are roughly comparable to \(f_{\omega^\omega}(n)\) and \(f_{\omega^{\omega^\omega}}(n)\) respectively, using Wainer hierarchy.
=== Hyperdimensional and nested arrays ===
Next, the bracket separators become arrays (such as \([1, 1, 2]\)). Rules M1 to M6 remain unchanged, except that we replace the \([m_n]\) with \([m_n \#]\).
The angle bracket rules require some modification. Rule A3 becomes A4, and a new rule A3 is created:
* Rule A3. If the first entry in the angle brackets is zero, and there exists a non-zero entry after it:
*: \(\textrm` a \langle 0,1,1,\cdots,1,1,c \# \rangle b \textrm' = \textrm` a \langle b,b,b,\cdots,b,b,c-1 \# \rangle b \textrm'\)
This rule is visually similar to the Rule M4.
The next step is to allow strings inside arrays and thereby define nested array notation. Rule A3 becomes A4 and A4 becomes A5. We then add a new A3 and generalize A4:
* Rule A3. If \([A] < [B]\), \(\textrm` a <\# [A] 1 [B] \#^*> b \textrm' = \textrm` a <\# [B] \#^*> b \textrm'\).
* Rule A4. If the first entry in the angle brackets is zero, and there exists a non-zero entry after it:
*:\(\textrm` a \langle 0 [x_1 \#_1] 1 [x_2 \#_2] \cdots 1 [x_n \#_n] c \# \rangle b \textrm' = \textrm` a \langle b \langle x_1-1 \#_1 \rangle b [x_1 \#_1] b \langle x_2-1 \#_2 \rangle b [x_2 \#_2] \cdots b \langle x_n-1 \#_n \rangle b [x_n \#_n] c-1 \# \rangle b \textrm'\)
An and B are arrays and Ai-1 is identical to Ai, except the first entry is reduced by one.
==== Algorithm for ranking two separators ====
For rules A3 and M2, it is important to determine what separator has higher level. First, let the number of arrays that nested one another is the nested level of array. We can notate that Lev(A). For example, A = \(\{3,3 [1 [1 [2] 2] 2] 2\}\), then Lev(A) = 3, since there [2] nested in [1 [2] 2], which is nested in [1 [1 [2] 2] 2], which is nested in the main array. Informally speaking, Lev(A) is the number that we need to say "nested" to get to main array. The other function, Num(H,A) is defined to be number of separators [H] in the array A, e.g. A = \(\{3,3 [1 [2] 1 [2] 1 [2] 2] 2\}\), then Num(2,A) = 3.
Suppose we want to determine what separator has higher level, [A] or [B]. Formally, it can be described as follows:
# For the further purposes, let [A1]=[A], [A2]=[A1] and [B1]=[B], [B2]=[B1].
# If Lev(A)>Lev(B), then conclude that [A]>[B], if Lev(A)<Lev(B), then [A]<[B]. If Lev(A)=Lev(B)>0, then go to step 3, otherwise go to step 6.
# Let [A*] and [B*] are highest ranking separators in the arrays A2 and B2 respectively. If [A*]>[B*] then [A]>[B], if [A*]<[B*] then [A]<[B], otherwise take [H]=[A*]=[B*] and go to step 4.
# If Num(H,A2)>Num(H,B2), then [A]>[B], if Num(A)>Num(B), if Num(H,A2)<Num(H,B2), then [A]<[B], otherwise go to step 5.
# In strings A2 and B2, delete [H] separator and remove all entries before it.
# Under all rules above, the strings A2 and B2 must be in form [a] and [b], where a and b are single numbers. So, if ab, then [A]>[B], otherwise go to step 7.
# In the strings A1 and B1 remove the very last entry and separator before it. If A1 and B1 are empty, then we conclude that [A]=[B], otherwise return to step 2.
== Hyper-Nested Arrays ==
=== Backslash arrays ===
To continue beyond Nested Array Notation, Bird defined a special separator, [1 \ c], as follows:
* \(\{a,b [1 \backslash c \#] 2\} = \{a \langle 0 \backslash c \# \rangle b\} =\)
\(\{a \langle b \langle b \langle b \langle \cdots b \langle b \backslash c-1 \# \rangle b \backslash c-1 \# \cdots \rangle b \backslash c-1 \# \rangle b \backslash c-1 \# \rangle b \backslash c-1 \# \rangle b\}\) (with b b's from the centre to right).
* \(\{a,b [A \backslash 1] 2\} = \{a,b [A] 2\}\) (if A is an arbitrary array)
This notation allows us to make arrays preceding backslash like [1 [2] 2 \ 2] or [1 [1 \ 2] 2 \ 2]. Placing the backslash on the base level (without at least one pair of square brackets), such as {3, 3 \ 2}, is illegal.
Bird extended it so that it can handle not only arrays with single backslash, but also multiple backslashes and even backslash-arrays. He used the notation [A]\ to indicate array A around backslash. There are new set of 3 rules that handles backslash-arrays:
* Rule B1. Backslash-dimensional level is either 0 or 1:
** \(\textrm`a \langle 0 \rangle\backslash b\textrm' = \textrm`a\textrm'\)
** \(\textrm`a \langle 1 \rangle\backslash b\textrm' = \textrm`a \backslash a \backslash \cdots \backslash a \backslash a\textrm'\) (with b a's)
* Rule B2. First entry of backslash angle brackets is not 0:
** \(\textrm`a \langle c \# \rangle\backslash b\textrm' = \textrm`a \langle c-1 \# \rangle\backslash b [c \#]\backslash a \langle c-1 \# \rangle b \cdots [c \#]\backslash a \langle c-1 \# \rangle b\textrm'\) (with b \(a \langle c-1 \# \rangle b\)'s)
* Rule B3. First non-zero entry is prior to a single backslash:
** \(\textrm`a \langle 0 [A_1]\backslash 1 [A_2]\backslash \cdots 1 [A_n]\backslash 1 \backslash c \# \rangle b\textrm'\)\(= \textrm`a \langle b \langle A_1' \rangle\backslash b [A_1]\backslash b \langle A_2' \rangle\backslash b [A_2]\backslash \cdots b \langle A_n' \rangle\backslash b [A_n]\backslash R_b \backslash c-1 \# \rangle b\textrm'\)
** \(R_n = \textrm`b \langle b \langle A_1' \rangle b [A_1]\backslash b \langle A_2' \rangle b [A_2]\backslash \cdots b \langle A_n' \rangle\backslash b [A_n]\backslash R_{n-1} \backslash c-1 \# \rangle b\textrm'\)
** \(R_1 = \textrm`0\textrm'\)
* Rule B4. Otherwise:
** \(\textrm`a \langle 0 [A_1]\backslash 1 [A_2]\backslash \cdots 1 [A_m]\backslash 1 [B_1] 1 [B_2] \cdots 1 [B_n] c \# \rangle b\textrm'\)\(= \textrm`a \langle b \langle A_1' \rangle\backslash b [A_1]\backslash b \langle A_2' \rangle\backslash [A_2]\backslash \cdots b \langle A_n' \rangle\backslash [A_n]\backslash b \langle B_1' \rangle b [B_1] b \langle B_2' \rangle b [B_2] \cdots b \langle B_n' \rangle b [B_n] c-1 \# \rangle b\textrm'\)
The limit of the notation introduced so far is the Feferman-Schütte ordinal.
== Nested Hyper-Nested Arrays ==
=== 2-hyperseparators ===
For now, we need a separator that will be powerful than any level of nesting around backslash-arrays. At the end of his document "Beyond Bird's Nested Arrays I", Bird proposed to use the forward slash as follows:
\(\{a,b [1 / 2] 2\} = \{a \langle 0 / 2 \rangle b\} = \{a \langle b \langle b \langle b \cdots b \langle b \rangle\backslash b \cdots b \rangle\backslash b \rangle\backslash b \rangle b\}\) (with b b's from the center to right, it leads to b-2 appended backslashes)
Next, Bird noted that separator [A]\ (backslash-array A) can be rewritten as \([A \neg 2]\), which allows us to rewrite forward slash as \([1 \neg 3]\). However, it will be more useful (for further purposes) to define \([1 \neg 3]\) in the following manner:
\(\{a,b [1 [1 \neg 3] 2] 2\} = \{a \langle 0 [1 \neg 3] 2 \rangle b\} = \{a \langle b \langle b \langle b \cdots b \langle b \rangle\backslash b \rangle\backslash b \cdots b \rangle\backslash b \rangle\backslash b \rangle b\}\) (with b+1 b's from the center to right, b-1 appended backslashes).
Then we can construct the arrays \([A \neg 3]\) around \([1 \neg 3]\) with the same manner as with backslash and \([1 A \neg 3]\). Note that backslash is \([1 \neg 2]\) separator.
So, we can create nested arrays with \(\neg 3\) appended to it, and the limit of all this will be \([1 \neg 4]\). It's not so hard to see the general pattern and define the \([1 \neg n]\) separator:
\(\{a,b [1 [1 \neg n] 2] 2\} = \{a \langle 0 [1 \neg n] 2 \rangle b\} = \{a \langle b \langle b \langle b \cdots b \langle b \neg n-1\rangle b \neg n-1\rangle b \cdots b \neg n-1\rangle b \neg n-1\rangle b \rangle b\}\) (with b+1 b's from the center to right, b-1 appearances of \(\neg n-1\)).
Generally, we need to define the set of rules that allows us to handle \([A \neg n]\). We don't need to rewrite Main Rules because they will be the same starting from Nested Array Notation. Only Angle Bracket Rules will be changed.
*Rule A1. Number inside angle brackets is 0:
*:\(\textrm`a \langle 0 \rangle b\textrm' = \textrm`a\textrm'\)
*Rule A2. b = 1:
*:\(\textrm`a \langle A \rangle 1\textrm' = \textrm`a\textrm'\)
*Rule A3. [A] < [B]:
*:\(\textrm`a \langle\# [A] 1 [B] \#\rangle b\textrm' = \textrm`a \langle\# [B] \#\rangle b\textrm'\)
*Rule A4. First entry is 0, c immediately after normal separator (not in the form \([1 \neg n]\) with n > 1):
*:\(\textrm`a \langle 0 [A_1] 1 [A_2] \cdots 1 [A_m] c \# \rangle b\textrm' = \textrm`a \langle b \langle A_1-1 \rangle b [A_1] b \langle A_2-1 \rangle b [A_2] \cdots b \langle A_m-1 \rangle b [A_m] c-1 \# \rangle b\textrm'\)
*Rule A5. First entry is 0, c immediately after backslash:
**\(\textrm`a \langle 0 [A_1] 1 [A_2] \cdots 1 [A_m] 1 \backslash c \# \rangle b\textrm' =\)
\(\textrm`a \langle b \langle A_1-1 \rangle b [A_1] b \langle A_2-1 \rangle b [A_2] \cdots b \langle A_m-1 \rangle b [A_m] b \langle R_b \rangle b \backslash c-1 \# \rangle b\textrm'\)
:*\(R_n = \textrm`b \langle A_1-1 \rangle b [A_1] b \langle A_2-1 \rangle b [A_2] \cdots b \langle A_m-1 \rangle b [A_m] b \langle R_{n-1} \rangle b \backslash c-1 \# \rangle b\textrm'\) (n>1)
:*\(R_1 = \textrm`0\textrm'\)
*Rule A6. First entry is 0, c immediately after \([1 \neg n]\) (n > 2):
**\(\textrm`a \langle 0 [A_1] 1 [A_2] \cdots 1 [A_m] 1 [1 \neg n] c \# \rangle b\textrm' =\)
\(\textrm`a \langle b \langle A_1-1 \rangle b [A_1] b \langle A_2-1 \rangle b [A_2] \cdots b \langle A_m-1 \rangle b [A_m] b \langle R \rangle b [1 \neg n] c-1 \# \rangle b\textrm'\)
:*\(R = \textrm`b \langle A_1-1 \rangle b [A_1] b \langle A_2-1 \rangle b [A_2] \cdots b \langle A_m-1 \rangle b [A_m] R_b [1 \neg n] c-1 \# \rangle b\textrm'\)
:*\(R_n = \textrm`b \langle A_1-1 \rangle b [A_1] b \langle A_2-1 \rangle b [A_2] \cdots b \langle A_m-1 \rangle b [A_m] b \langle R_{b-1} \rangle b [1 \neg n] c-1 \# \neg n-1 \rangle b\textrm'\) (n>1)
:*\(R_1 = \textrm`0\textrm'\)
*Rule A7. Rules A1-A6 don't apply:
*:\(\textrm`a \langle c \# \rangle b\textrm' = \textrm`a \langle c-1 \# \rangle b [c \#] a \langle c \# \rangle b-1\textrm'\).
This notation has strength at \(\theta(\Omega^\omega)\), the small Veblen ordinal.
== Arrays of 2-hyperseperators ==
We define \(\textrm`a \langle 0 [1 \neg 1,2] 2 \rangle b\textrm' = \textrm`a \langle b [b \neg b] b \rangle b\textrm'\).
*Rule A1. Base rule:
:*\(\textrm`a \langle 0 \rangle b\textrm' = \textrm`a\textrm'\)
:*\(\textrm`a \langle 0 \neg \# \rangle b\textrm' = \textrm`a\textrm'\)
*Rule A2. b = 1:
*:\(\textrm`a \langle A \rangle 1\textrm' = \textrm`a\textrm'\)
*Rule A3. Remove traling 1's and low seperators:
:*\(\textrm`a \langle \# 1 \rangle b\textrm' = \textrm`a \langle \# \rangle b\textrm'\)
:*\(\textrm`a \langle \# [A] 1 [B] \#^* \rangle b\textrm' = \textrm`a \langle \# [B] \#^* \rangle b\textrm'\)(when [A] < [B])
== Nested Hyper Nested Array Notation ==
Angle Bracket Rules A2 and A3 now read as follows:-
Rule A2 (only 1 entry of either 0 or 1 prior to 2-hyperseparator or higher order hyperseparator):
‘a ‹0 #› b’ = ‘a’,
‘a ‹1 #› b’ = ‘a [1 #] a [1 #] ... [1 #] a’ (with b a’s),
‘a ‹1 ¬ 2› b’ = ‘a \ a \ ... \ a’ (with b a’s),
‘a ‹1 ♦ 2› b’ = ‘a ¬ a ¬ ... ¬ a’ (with b a’s),
where # begins with a 2- or higher order hyperseparator (¬ under no layers of square brackets, or ♦
under less than 2 layers of square brackets).
Rule A3 (last entry in any 1-space or higher dimensional space of array is 1):
‘a ‹# [A] 1› b’ = ‘a ‹#› b’.
When [A] is an m-hyperseparator, [B] is an n-hyperseparator and m < n, or m = n and level of [A] is less than level of [B],
‘a ‹# [A] 1 [B] #*› b’ = ‘a ‹# [B] #*› b’.
Remove trailing 1’s.
Rules A5a and A5c are modified as follows: -
Rule A5a ([Ai,pi] = [1 [Bi,1♦2] 1 [Bi,2♦2] ... 1 [Bi,qi♦2] 1 [Ai+1,1] 1 [Ai+1,2] ... 1 [Ai+1,pi+1] ci+1 #i+1],
where pi+1 ≥ 1, qi ≥ 1):
Si = ‘b ‹Ai,1’› b [Ai,1] b ‹Ai,2’› b [Ai,2] ... b ‹Ai,pi-1’› b [Ai,pi-1] b ‹Ti› b [Ai,pi] ci-1 #i’,
Ti = ‘b ‹Bi,1’♦2› b [Bi,1♦2] b ‹Bi,2’♦2› b [Bi,2♦2] ... b ‹Bi,qi’♦2› b [Bi,qi♦2] Si+1’.
Increment i by 1 and repeat Rules A5a-d.
Rule A5c (Rules A5a-b do not apply, [Ai,pi] = [1 [Bi,1♦2] 1 [Bi,2♦2] ... 1 [Bi,qi-1♦2] 1 ¬ di #*i],
where qi ≥ 1):
Si = ‘b ‹Ai,1’› b [Ai,1] b ‹Ai,2’› b [Ai,2] ... b ‹Ai,pi-1’› b [Ai,pi-1] b ‹Rb› b [Ai,pi] ci-1 #i’,
Rn = ‘b ‹Bi,1’♦2› b [Bi,1♦2] b ‹Bi,2’♦2› b [Bi,2♦2] ... b ‹Bi,qi-1’♦2› b [Bi,qi-1♦2] b ‹Ai,1’› b [Ai,1] b ‹Ai,2’› b [Ai,2] ... b ‹Ai,pi-1’› b [Ai,pi-1] b ‹Rn-1› b [Ai,pi] ci-1 #i ¬ di-1 #*i’ (n > 1),
R1 = ‘0’.
The old Rule A5d becomes Rule A5e (Rules A5a-d do not apply) and a new Rule A5d is created as follows: -
Rule A5d (Rules A5a-c do not apply, [Ai,pi] = [1 [Bi,1♦2] 1 [Bi,2♦2] ... 1 [Bi,qi♦2] di #*i],
where qi ≥ 1 and [Bi,qi♦2] is above [1♦2] or ¬ in level):
Si = ‘b ‹Ai,1’› b [Ai,1] b ‹Ai,2’› b [Ai,2] ... b ‹Ai,pi-1’› b [Ai,pi-1] b ‹T› b [Ai,pi] ci-1 #i’,
T = ‘b ‹Bi,1’♦2› b [Bi,1♦2] b ‹Bi,2’♦2› b [Bi,2♦2] ... b ‹Bi,qi’♦2› b [Bi,qi♦2] di-1 #*i’.
The new Rule A5d is necessary owing to the fact that if the old Rule A5d (now A5e) applied, the string T would become Ai,pi’ = ‘0 [Bi,1♦2] 1 [Bi,2♦2] ... 1 [Bi,qi♦2] di #*i’,
which means that ‘b ‹T› b’ = ‘b ‹ 0 [Bi,1♦2] 1 [Bi,2♦2] ... 1 [Bi,qi♦2] di #*i › b’
= ‘b’, by the revised Rule A2, since [Bi,1♦2] is a 2-hyperseparator (start of the #0 string).
Take the simple example of N = {a, b [1 [1 [2♦2] 2] 2] 2}
= {a ‹0 [1 [2♦2] 2] 2› b},
with c1 = 2, d1 = 2, p1 = 1, q1 = 1, all #-strings blank,
[A1,1] = [1 [2♦2] 2],
[B1,1♦2] = [2♦2].
Under the old Rule A5d,
N = {a ‹S› b}
= {a ‹b ‹T› b› b}
= {a ‹b› b},
whereas under the new Rule A5d,
N = {a ‹S› b}
= {a ‹b ‹T› b› b}
= {a ‹b ‹b ‹B1,1’♦2› b› b› b}
= {a ‹b ‹b ‹1♦2› b› b› b},
and, by the revised Rule A2,
N = {a ‹b ‹ b ¬ b ¬ ... ¬ b › b› b} (with b b’s within inner angle brackets),
as originally defined.
If [A1,p1] is a backslash (\), Rule A5b is executed. 
If [A1,p1] is any other nesting separator, A5c is processed. Rule A5c now has three subrules. (The i-subscripts have been removed.)
Rule A5c1 ([Ap] = [1 [B1] 1 [B2] ... 1 [Bq-1] 1 ¬ d #*],
where q ≥ 1, d ≥ 2):
S = ‘b ‹A1’› b [A1] b ‹A2’› b [A2] ... b ‹Ap-1’› b [Ap-1] b ‹Rb› b [Ap] c-1 #’,
Rn = ‘b ‹B1’› b [B1] b ‹B2’› b [B2] ... b ‹Bq-1’› b [Bq-1]
b ‹A1’› b [A1] b ‹A2’› b [A2] ... b ‹Ap-1’› b [Ap-1] b ‹Rn-1› b [Ap] c-1 # ¬ d-1 #*’ (n > 1),
R1 = ‘0’.
Rule A5c2 ([Ap] = [1 [B1] 1 [B2] ... 1 [Bq] d #*],
where [Bq] = [1 [C1] 1 [C2] ... 1 [Cr-1] 1 ♦ e #**]
and q ≥ 1, r ≥ 1, d ≥ 2, e ≥ 2):
S = ‘b ‹A1’› b [A1] b ‹A2’› b [A2] ... b ‹Ap-1’› b [Ap-1] b ‹Rb› b [Ap] c-1 #’,
Rn = ‘b ‹B1’› b [B1] b ‹B2’› b [B2] ... b ‹Bq-1’› b [Bq-1] b ‹Tn› b [Bq] d-1 #*’ (n > 1),
Tn = ‘b ‹C1’› b [C1] b ‹C2’› b [C2] ... b ‹Cr-1’› b [Cr-1]
b ‹A1’› b [A1] b ‹A2’› b [A2] ... b ‹Ap-1’› b [Ap-1] b ‹Rn-1› b [Ap] c-1 # ♦ e-1 #**’ (n > 1),
R1 = ‘0’.
Rule A5c3 ([Ap] = [1 [B1] 1 [B2] ... 1 [Bq] d #*],
where [Bq] = [1 [C1] 1 [C2] ... 1 [Cr] e #**],
where [Cr] = [1 ☼ k #***]
and q ≥ 1, r ≥ 1, d ≥ 2, e ≥ 2, k ≥ 2):
S = ‘b ‹A1’› b [A1] b ‹A2’› b [A2] ... b ‹Ap-1’› b [Ap-1] b ‹Rb› b [Ap] c-1 #’,
Rn = ‘b ‹B1’› b [B1] b ‹B2’› b [B2] ... b ‹Bq-1’› b [Bq-1] b ‹Tn› b [Bq] d-1 #*’ (n > 1),
Tn = ‘b ‹C1’› b [C1] b ‹C2’› b [C2] ... b ‹Cr-1’› b [Cr-1] b ‹Un› b [Cr] e-1 #**’ (n > 1),
Un = ‘b ‹A1’› b [A1] b ‹A2’› b [A2] ... b ‹Ap-1’› b [Ap-1] b ‹Rn-1› b [Ap] c-1 # ☼ k-1 #***’ (n > 1),
R1 = ‘0’.
Rule A5d splits into two subrules – A5d1 for the first set (2-plugging separators) and A5d2 for the
latter (3-plugging separators). (The i-subscripts have been removed as in Rules A5c1-3.)
Rule A5d1 ([Ap] = [1 [B1] 1 [B2] ... 1 [Bq] d #*],
where [Bq] = [X [C1] Y], X ≠ ‘1’, Y ≠ ‘1’
and q ≥ 1, d ≥ 2):
S = ‘b ‹A1’› b [A1] b ‹A2’› b [A2] ... b ‹Ap-1’› b [Ap-1] b ‹T› b [Ap] c-1 #’,
T = ‘b ‹B1’› b [B1] b ‹B2’› b [B2] ... b ‹Bq’› b [Bq] d-1 #*’.
Rule A5d2 ([Ap] = [1 [B1] 1 [B2] ... 1 [Bq] d #*],
where [Bq] = [1 [C1] 1 [C2] ... 1 [Cr] e #**],
where [Cr] = [X☼Y], X ≠ ‘1’, Y ≠ ‘1’
and q ≥ 1, r ≥ 1, d ≥ 2, e ≥ 2):
S = ‘b ‹A1’› b [A1] b ‹A2’› b [A2] ... b ‹Ap-1’› b [Ap-1] b ‹T› b [Ap] c-1 #’,
T = ‘b ‹B1’› b [B1] b ‹B2’› b [B2] ... b ‹Bq-1’› b [Bq-1] b ‹U› b [Bq] d-1 #*’,
U = ‘b ‹C1’› b [C1] b ‹C2’› b [C2] ... b ‹Cr’› b [Cr] e-1 #**’.
Branching separators (Rule A5a) now come in three sets. The first set contains hyperseparators of
the form
[1 [B1] 1 [B2] ... 1 [Bq] 1 [A1] 1 [A2] ... 1 [Ap] k #*].
The second set comprises hyperseparators of the form
[1 [B1] 1 [B2] ... 1 [Bq] d #*],
where [Bq] = [1 [C1] 1 [C2] ... 1 [Cr] 1 [A1] 1 [A2] ... 1 [Ap] k #**].
The third set comprises hyperseparators of the form
[1 [B1] 1 [B2] ... 1 [Bq] d #*],
where [Bq] = [1 [C1] 1 [C2] ... 1 [Cr] e #**],
where [Cr] = [1 ☼ 1 [A1] 1 [A2] ... 1 [Ap] k #***].
In all three sets, each of the [Aj] are either normal separators or 1-hyperseparators, each of the [Bj]
are 2-hyperseparators, each of the [Cj] are 3-hyperseparators, p ≥ 1, q ≥ 1, r ≥ 1, d ≥ 2, e ≥ 2, k ≥ 2
and #*, #** and #*** are rest of their respective arrays.
Rule A5a now has three subrules, with subrule n for n-branching separators (nth set of the three
shown above). Note that i is initially set to 1.
Rule A5a1 ([Ai,pi] = [1 [Bi,1] 1 [Bi,2] ... 1 [Bi,qi] 1 [Ai+1,1] 1 [Ai+1,2] ... 1 [Ai+1,pi+1] ci+1 #i+1],
where pi+1 ≥ 1, qi ≥ 1):
Si = ‘b ‹Ai,1’› b [Ai,1] b ‹Ai,2’› b [Ai,2] ... b ‹Ai,pi-1’› b [Ai,pi-1] b ‹Ti› b [Ai,pi] ci-1 #i’,
Ti = ‘b ‹Bi,1’› b [Bi,1] b ‹Bi,2’› b [Bi,2] ... b ‹Bi,qi’› b [Bi,qi] Si+1’.
Increment i by 1 and repeat Rules A5a-e.
19
Rule A5a2 ([Ai,pi] = [1 [Bi,1] 1 [Bi,2] ... 1 [Bi,qi] di #*i],
where [Bi,qi] = [1 [Ci,1] 1 [Ci,2] ... 1 [Ci,ri] 1 [Ai+1,1] 1 [Ai+1,2] ... 1 [Ai+1,pi+1] ci+1 #i+1]
and pi+1 ≥ 1, qi ≥ 1, ri ≥ 1):
Si = ‘b ‹Ai,1’› b [Ai,1] b ‹Ai,2’› b [Ai,2] ... b ‹Ai,pi-1’› b [Ai,pi-1] b ‹Ti› b [Ai,pi] ci-1 #i’,
Ti = ‘b ‹Bi,1’› b [Bi,1] b ‹Bi,2’› b [Bi,2] ... b ‹Bi,qi-1’› b [Bi,qi-1] b ‹Ui› b [Bi,qi] di-1 #*i’,
Ui = ‘b ‹Ci,1’› b [Ci,1] b ‹Ci,2’› b [Ci,2] ... b ‹Ci,ri’› b [Ci,ri] Si+1’.
Increment i by 1 and repeat Rules A5a-e.
Rule A5a3 ([Ai,pi] = [1 [Bi,1] 1 [Bi,2] ... 1 [Bi,qi] di #*i],
where [Bi,qi] = [1 [Ci,1] 1 [Ci,2] ... 1 [Ci,ri] ei #**i],
where [Ci,ri] = [1 ☼ 1 [Ai+1,1] 1 [Ai+1,2] ... 1 [Ai+1,pi+1] ci+1 #i+1]
and pi+1 ≥ 1, qi ≥ 1, ri ≥ 1):
Si = ‘b ‹Ai,1’› b [Ai,1] b ‹Ai,2’› b [Ai,2] ... b ‹Ai,pi-1’› b [Ai,pi-1] b ‹Ti› b [Ai,pi] ci-1 #i’,
Ti = ‘b ‹Bi,1’› b [Bi,1] b ‹Bi,2’› b [Bi,2] ... b ‹Bi,qi-1’› b [Bi,qi-1] b ‹Ui› b [Bi,qi] di-1 #*i’,
Ui = ‘b ‹Ci,1’› b [Ci,1] b ‹Ci,2’› b [Ci,2] ... b ‹b ☼ Si+1› b [Ci,ri] ei-1 #**i’.
Angle Bracket Rule A5 is modified as follows:-
Rule A5 (Rules A1-4 do not apply, first entry is 0, separator immediately prior to next non-1 entry (c1,1)
is [A1,1,p1,1]):
‘a ‹ 0 [A1,1,1] 1 [A1,1,2] ... 1 [A1,1,p1,1] c1,1 #1,1 #* › b’ = ‘a ‹S1,1 #*› b’,
where p1,1 ≥ 1, each of [A1,1,i*] is either normal separator or 1-hyperseparator, #1,1 contains no 2- or
higher order hyperseparators in its base layer and #* is either an empty string or begins with a 2- or
higher order hyperseparator.
Set i = 1 and follow Rules A5a-e (b-e are terminal, a is not).
Rule A5a (separator
[Ai,j,pi,j] = [1 [Ai,j+1,1] 1 [Ai,j+1,2] ... 1 [Ai,j+1,pi,j+1] ci,j+1 #i,j+1] (1 ≤ j < k)
= [1 [Ai,j+1,1] 1 [Ai,j+1,2] ... 1 [Ai,j+1,pi,j+1]
1 [Ai+1,1,1] 1 [Ai+1,1,2] ... 1 [Ai+1,1,pi+1,1] ci+1,1 #i+1,1] (j = k),
where pi,j+1 ≥ 1, pi+1,1 ≥ 1, ci+1,1 ≥ 2, each of [Ai+1,1,i*] is either a normal separator or 1-hyperseparator,
and each of [Ai,j+1,i*] is a (j+1)-hyperseparator):
Si,j = ‘b ‹Ai,j,1’› b [Ai,j,1] b ‹Ai,j,2’› b [Ai,j,2] ... b ‹Ai,j,pi,j-1’› b [Ai,j,pi,j-1]
b ‹Si,j+1› b [Ai,j,pi,j] ci,j-1 #i,j’ (1 ≤ j < k+1)
= ‘b ‹Ai,j,1’› b [Ai,j,1] b ‹Ai,j,2’› b [Ai,j,2] ... b ‹Ai,j,pi,j’› b [Ai,j,pi,j] Si+1,1’ (j = k+1).
Increment i by 1 and repeat Rules A5a-e.
23
Rule A5b (separator [Ai,1,pi,1] = [1 \2 2] = \):
Si,1 = ‘Rb’,
Rn = ‘b ‹Ai,1,1’› b [Ai,1,1] b ‹Ai,1,2’› b [Ai,1,2] ... b ‹Ai,1,pi,1-1’› b [Ai,1,pi,1-1]
b ‹Rn-1› b \ ci,1-1 #i,1’ (n > 1),
R1 = ‘0’.
Rule A5c (Rules A5a-b do not apply, separator
[Ai,j,pi,j] = [1 [Ai,j+1,1] 1 [Ai,j+1,2] ... 1 [Ai,j+1,pi,j+1] ci,j+1 #i,j+1] (1 ≤ j < k)
= [1 \ j+1 2] = \ j (j = k),
where pi,j+1 ≥ 1, ci,j+1 ≥ 2 and each of [Ai,j+1,i*] is a (j+1)-hyperseparator):
Si,1 = ‘b ‹Ai,1,1’› b [Ai,1,1] b ‹Ai,1,2’› b [Ai,1,2] ... b ‹Ai,1,pi,1-1’› b [Ai,1,pi,1-1]
b ‹Rb,1› b [Ai,1,pi,1] ci,1-1 #i,1’,
Rn,j = ‘b ‹Ai,j+1,1’› b [Ai,j+1,1] b ‹Ai,j+1,2’› b [Ai,j+1,2] ...
b ‹Ai,j+1,pi,j+1-1’› b [Ai,j+1,pi,j+1-1] b ‹Rn,j+1› b [Ai,j+1,pi,j+1] ci,j+1-1 #i,j+1’ (n > 1, 1 ≤ j < k-1)
= ‘b ‹Ai,j+1,1’› b [Ai,j+1,1] b ‹Ai,j+1,2’› b [Ai,j+1,2] ... b ‹Ai,j+1,pi,j+1-1’› b [Ai,j+1,pi,j+1-1]
b ‹Ai,1,1’› b [Ai,1,1] b ‹Ai,1,2’› b [Ai,1,2] ... b ‹Ai,1,pi,1-1’› b [Ai,1,pi,1-1]
b ‹Rn-1,1› b [Ai,1,pi,1] ci,1-1 #i,1 \ j+1 ci,j+1-1 #i,j+1’ (n > 1, j = k-1),
R1,1 = ‘0’.
Rule A5d (Rules A5a-c do not apply, separator
[Ai,j,pi,j] = [1 [Ai,j+1,1] 1 [Ai,j+1,2] ... 1 [Ai,j+1,pi,j+1] ci,j+1 #i,j+1] (1 ≤ j < k)
= [X [Ai,j+1,1] Y], X ≠ ‘1’, Y ≠ ‘1’ (j = k ≥ 2),
where pi,j+1 ≥ 1, ci,j+1 ≥ 2, each of [Ai,j+1,i*] is a (j+1)-hyperseparator and X does not contain any 2- or
higher order hyperseparators in its ‘base layer’):
Si,j = ‘b ‹Ai,j,1’› b [Ai,j,1] b ‹Ai,j,2’› b [Ai,j,2] ... b ‹Ai,j,pi,j-1’› b [Ai,j,pi,j-1]
b ‹Si,j+1› b [Ai,j,pi,j] ci,j-1 #i,j’ (1 ≤ j < k)
= ‘b ‹Ai,j,1’› b [Ai,j,1] b ‹Ai,j,2’› b [Ai,j,2] ... b ‹Ai,j,pi,j’› b [Ai,j,pi,j] ci,j-1 #i,j’ (j = k).
Rule A5e (Rules A5a-d do not apply):
Si,1 = ‘b ‹Ai,1,1’› b [Ai,1,1] b ‹Ai,1,2’› b [Ai,1,2] ... b ‹Ai,1,pi,1’› b [Ai,1,pi,1] ci,1-1 #i,1’.
Rules A5a, A5c and A5d process k-branching, (k-1)-nesting and k-plugging separators respectively
(for a given value of k). These rules can be simplified by considering each individual layer separately
(as well as each individual branch), and iterating j in the same manner as i. The possible base-layer
scenarios of the [Ai,j,pi,j] separator fall into five sets or categories (each to be served by different
subrules), these are as follows:-
Set 1: [1 \2 2] = \ (j = 1).
Set 2: [1 \ j+1 2] = \ j (j ≥ 2).
Set 3: [1 [Ai,j+1,1] 1 [Ai,j+1,2] ... 1 [Ai,j+1,pi,j+1] 1 [Ai+1,1,1] 1 [Ai+1,1,2] ... 1 [Ai+1,1,pi+1,1] ci+1,1 #i+1,1].
Set 4: [1 [Ai,j+1,1] 1 [Ai,j+1,2] ... 1 [Ai,j+1,pi,j+1] ci,j+1 #i,j+1].
Set 5: All other scenarios.
In Sets 3 and 4, pi,j+1 ≥ 1, each of [Ai,j+1,i*] is a (j+1)-hyperseparator and the # strings represent the rest
of the separator array (which may be null strings). Additionally, in Set 3, pi+1,1 ≥ 1, ci+1,1 ≥ 2, and each
of [Ai+1,1,i*] is either a normal separator or 1-hyperseparator; in Set 4, ci,j+1 ≥ 2.
Set 1 covers 1-nesting separators (trivial case), Set 2 covers the top layers of nesting separators
(other than Set 1), Set 3 covers the top layers of branching separators, Set 4 covers the lower layers
of all three types of special separators and Set 5 covers all other (or non-special) separators
(including the top layers of plugging separators).
=== Angle Bracket Rules (BNA3) ===
The modified and complete Angle Bracket Rules – including the revised subrules of Rule A5 – are as
follows:-
Rule A1 (only 1 entry of either 0 or 1):
‘a ‹0› b’ = ‘a’,
‘a ‹1› b’ = ‘a, a, ... , a’ (with b a’s).
Rule A2 (only 1 entry of either 0 or 1 prior to 2-hyperseparator or higher order hyperseparator):
‘a ‹0 #› b’ = ‘a’,
‘a ‹1 #› b’ = ‘a [1 #] a [1 #] ... [1 #] a’ (with b a’s),
where # begins with a 2- or higher order hyperseparator.
When n ≥ 2,
‘a ‹1 \n 2› b’ = ‘a \n-1 a \n-1 ... \n-1 a’ (with b a’s).
Rule A3 (last entry in any 1-space or higher dimensional space of array is 1):
‘a ‹# [A] 1› b’ = ‘a ‹#› b’.
When [A] is an m-hyperseparator, [B] is an n-hyperseparator and m < n, or m = n and level of [A] is
less than level of [B],
‘a ‹# [A] 1 [B] #*› b’ = ‘a ‹# [B] #*› b’.
Remove trailing 1’s.
Rule A4 (number to right of angle brackets is 1):
‘a ‹A› 1’ = ‘a’.
Rule A5 (Rules A1-4 do not apply, first entry is 0, separator immediately prior to next non-1 entry (c1,1)
is [A1,1,p1,1]):
‘a ‹ 0 [A1,1,1] 1 [A1,1,2] ... 1 [A1,1,p1,1] c1,1 #1,1 #* › b’ = ‘a ‹S1,1 #*› b’,
where p1,1 ≥ 1, each of [A1,1,i*] is either normal separator or 1-hyperseparator, #1,1 contains no 2- or
higher order hyperseparators in its base layer and #* is either an empty string or begins with a 2- or
higher order hyperseparator.
Set i = 1 and j = 1, and follow Rules A5a-e (a, b and e are terminal, c and d are not).
Rule A5a (separator [Ai,1,pi,1] = [1 \2 2] = \):
Si,1 = ‘Rb’,
Rn = ‘b ‹Ai,1,1’› b [Ai,1,1] b ‹Ai,1,2’› b [Ai,1,2] ... b ‹Ai,1,pi,1-1’› b [Ai,1,pi,1-1]
b ‹Rn-1› b \ ci,1-1 #i,1’ (n > 1),
R1 = ‘0’.
Rule A5b (Rule A5a does not apply, separator [Ai,j,pi,j] = [1 \ j+1 2] = \ j, where j ≥ 2):
Si,j = ‘Rb,j-1’,
Rn,j-1 = ‘b ‹Ai,j,1’› b [Ai,j,1] b ‹Ai,j,2’› b [Ai,j,2] ... b ‹Ai,j,pi,j-1’› b [Ai,j,pi,j-1]
b ‹Ai,1,1’› b [Ai,1,1] b ‹Ai,1,2’› b [Ai,1,2] ... b ‹Ai,1,pi,1-1’› b [Ai,1,pi,1-1]
b ‹Rn-1,1› b [Ai,1,pi,1] ci,1-1 #i,1 \ j ci,j-1 #i,j’ (n > 1),
Rn,k = ‘b ‹Ai,k+1,1’› b [Ai,k+1,1] b ‹Ai,k+1,2’› b [Ai,k+1,2] ...
b ‹Ai,k+1,pi,k+1-1’› b [Ai,k+1,pi,k+1-1] b ‹Rn,k+1› b [Ai,k+1,pi,k+1] ci,k+1-1 #i,k+1’ (n > 1, 1 ≤ k < j-1),
R1,1 = ‘0’.
25
Rule A5c (Rules A5a-b do not apply, separator
[Ai,j,pi,j] = [1 [Ai,j+1,1] 1 [Ai,j+1,2] ... 1 [Ai,j+1,pi,j+1] 1 [Ai+1,1,1] 1 [Ai+1,1,2] ... 1 [Ai+1,1,pi+1,1] ci+1,1 #i+1,1],
where pi,j+1 ≥ 1, pi+1,1 ≥ 1, ci+1,1 ≥ 2, each of [Ai+1,1,i*] is either a normal separator or 1-hyperseparator,
and each of [Ai,j+1,i*] is a (j+1)-hyperseparator):
Si,j = ‘b ‹Ai,j,1’› b [Ai,j,1] b ‹Ai,j,2’› b [Ai,j,2] ... b ‹Ai,j,pi,j-1’› b [Ai,j,pi,j-1] b ‹Ti› b [Ai,j,pi,j] ci,j-1 #i,j’,
Ti = ‘b ‹Ai,j+1,1’› b [Ai,j+1,1] b ‹Ai,j+1,2’› b [Ai,j+1,2] ... b ‹Ai,j+1,pi,j+1’› b [Ai,j+1,pi,j+1] Si+1,1’.
Increment i by 1, reset j = 1, and repeat Rules A5a-e.
Rule A5d (Rules A5a-c do not apply, separator
[Ai,j,pi,j] = [1 [Ai,j+1,1] 1 [Ai,j+1,2] ... 1 [Ai,j+1,pi,j+1] ci,j+1 #i,j+1],
where pi,j+1 ≥ 1, ci,j+1 ≥ 2 and each of [Ai,j+1,i*] is a (j+1)-hyperseparator):
Si,j = ‘b ‹Ai,j,1’› b [Ai,j,1] b ‹Ai,j,2’› b [Ai,j,2] ... b ‹Ai,j,pi,j-1’› b [Ai,j,pi,j-1] b ‹Si,j+1› b [Ai,j,pi,j] ci,j-1 #i,j’.
Increment j by 1 and repeat Rules A5a-e.
Rule A5e (Rules A5a-d do not apply):
Si,j = ‘b ‹Ai,j,1’› b [Ai,j,1] b ‹Ai,j,2’› b [Ai,j,2] ... b ‹Ai,j,pi,j’› b [Ai,j,pi,j] ci,j-1 #i,j’.
Rule A6 (Rules A1-5 do not apply):
‘a ‹n #› b’ = ‘a ‹n-1 #› b [n #] a ‹n-1 #› b [n #] ... [n #] a ‹n-1 #› b’
(with b ‘a ‹n-1 #› b’ strings).
=== Hierarchical Hyper Nested Array Notation (Part 2) ===
Angle Bracket Rule A5 (excluding A5a*) now reads as follows:-
Rule A5 (Rules A1-4 do not apply, first entry is 0, separator immediately prior to next non-1 entry (c1)
is [A1,p1]):
‘a ‹ 0 [A1,1] 1 [A1,2] ... 1 [A1,p1] c1 #1 #* › b’ = ‘a ‹S1 #*› b’,
where p1 ≥ 1, each of [A1,j] is either a normal separator or 1-hyperseparator, #1 contains no 2- or
higher order hyperseparators in its base layer and #* is either an empty string or begins with a 2- or
higher order hyperseparator.
Set i = 1 and follow Rules A5a-c (a, a* and c are terminal, b is not).
Rule A5a (separator [Ai,pi] = [1 /2 2] = /):
Si = ‘Rb,i’.
For n > 1 and 1 ≤ k < i,
Rn,i = ‘b ‹Ai,1’› b [Ai,1] b ‹Ai,2’› b [Ai,2] ... b ‹Ai,pi-1’› b [Ai,pi-1] b ‹Rn-1,1› b / ci-1 #i’,
Rn,k = ‘b ‹Ak,1’› b [Ak,1] b ‹Ak,2’› b [Ak,2] ... b ‹Ak,pk-1’› b [Ak,pk-1] b ‹Rn,k+1› b [Ak,pk] ck-1 #k’,
R1,1 = ‘0’.
Rule A5b (Rules A5a-a* do not apply, separator [Ai,pi] = [1 [Ai+1,1] 1 [Ai+1,2] ... 1 [Ai+1,pi+1] ci+1 #i+1],
which is a 1- or higher order hyperseparator, where pi+1 ≥ 1 and ci+1 ≥ 2):
Si = ‘b ‹Ai,1’› b [Ai,1] b ‹Ai,2’› b [Ai,2] ... b ‹Ai,pi-1’› b [Ai,pi-1] b ‹Si+1› b [Ai,pi] ci-1 #i’.
Increment i by 1 and repeat Rules A5a-c.
Rule A5c (Rules A5a-b do not apply):
Si = ‘b ‹Ai,1’› b [Ai,1] b ‹Ai,2’› b [Ai,2] ... b ‹Ai,pi’› b [Ai,pi] ci-1 #i’
The ‘super-rule’ Angle Bracket Rule A5 effectively has three subrules, according to the composition of
the [Ai,pi] separator:
A5a: [Ai,pi] = [1 /m+1 2] = /m (m ≥ 1).
A5b: [Ai,pi] = [1 [Ai+1,1] 1 [Ai+1,2] ... 1 [Ai+1,pi+1] ci+1 #i+1],
which is an m-hyperseparator (pi+1 ≥ 1, ci+1 ≥ 2, m ≥ 1).
A5c: All other scenarios of [Ai,pi].
The revised Rule A5a reads as follows:-
Rule A5a (separator [Ai,pi] = [1 /m+1 2] = /m, where m ≥ 1):
s = i-tm,
Si = ‘Rb,i’.
For n > 1 and s ≤ k < i,
Rn,i = ‘b ‹Ai,1’› b [Ai,1] b ‹Ai,2’› b [Ai,2] ... b ‹Ai,pi-1’› b [Ai,pi-1] b ‹Rn-1,s› b /m ci-1 #i’,
Rn,k = ‘b ‹Ak,1’› b [Ak,1] b ‹Ak,2’› b [Ak,2] ... b ‹Ak,pk-1’› b [Ak,pk-1] b ‹Rn,k+1› b [Ak,pk] ck-1 #k’,
R1,s = ‘0’.
The initial part of Rule A5 ends with the line:-
Set i to 1 and t1, t2, ... , tx to 0 (where x is the highest subscript to a forward slash within [A1,p1]), and
follow Rules A5a-c (a and c are terminal, b is not). (Note that i = t1+1 throughout.)
In Rule A5b, [Ai,pi] is an m-hyperseparator, where m ≥ 1. This rule ends with the line:-
Increment i, t1, t2, ... , tm by 1; reset tm+1, tm+2, ... , tx to 0 and repeat Rules A5a-c. (i = t1+1.)
The Bachmann-Howard level separator can now be verified using the revised Rule A5:
{a, b [1 [1~3] 2] 2} = {a ‹0 [1~3] 2› b}
= {a ‹S1› b}.
Since p1 = 1, c1 = 2, #1 = #* = ‘’ (blank),
[A1,1] = [1~3] (1-hyperseparator),
p2 = 1, c2 = 3, #2 = ‘’ (blank),
[A2,1] = ~ (= /2) (2-hyperseparator),
by Rule A5b (m = 1),
S1 = ‘b ‹S2› b’,
t1 = 1, t2 = 0,
and by Rule A5a (m = 2, s = 2),
S2 = ‘Rb,2’,
Rn,2 = ‘b ‹Rn-1,2› b ~2’,
R1,2 = ‘0’.
It follows that,
{a, b [1 [1~3] 2] 2} = {a ‹b ‹Rb› b› b},
where Rn = ‘b ‹Rn-1› b ~2’,
R1 = ‘0’.
=== Bird’s Hierarchical Hyper-Nested Array Notation – Angle Bracket Rules ===
Rule A1 (only 1 entry of either 0 or 1):
‘a ‹0› b’ = ‘a’,
‘a ‹1› b’ = ‘a, a, ... , a’ (with b a’s).
Rule A2 (only 1 entry of either 0 or 1 prior to 2-hyperseparator or higher order hyperseparator):
‘a ‹0 #› b’ = ‘a’,
‘a ‹1 #› b’ = ‘a [1 #] a [1 #] ... [1 #] a’ (with b a’s),
where # begins with a 2- or higher order hyperseparator.
When n ≥ 2,
‘a ‹1 /n 2› b’ = ‘a /n-1 a /n-1 ... /n-1 a’ (with b a’s).
Rule A3 (last entry in any 1-space or higher dimensional space of array is 1):
‘a ‹# [A] 1› b’ = ‘a ‹#› b’.
When [A] is an m-hyperseparator, [B] is an n-hyperseparator and m < n, or m = n and level of [A] is
less than level of [B],
‘a ‹# [A] 1 [B] #*› b’ = ‘a ‹# [B] #*› b’.
Remove trailing 1’s.
Rule A4 (number to right of angle brackets is 1):
‘a ‹A› 1’ = ‘a’.
Rule A5 (Rules A1-4 do not apply, first entry is 0, separator immediately prior to next non-1 entry (c1)
is [A1,p1]):
‘a ‹ 0 [A1,1] 1 [A1,2] ... 1 [A1,p1] c1 #1 #* › b’ = ‘a ‹S1 #*› b’,
where p1 ≥ 1, each of [A1,j] is either a normal separator or 1-hyperseparator, #1 contains no 2- or
higher order hyperseparators in its base layer and #* is either an empty string or begins with a 2- or
higher order hyperseparator.
Set i to 1 and t1, t2, ... , tx to 0 (where x is the highest subscript to a forward slash within [A1,p1]), and
follow Rules A5a-c (a and c are terminal, b is not). (Note that i = t1+1 throughout.)
Rule A5a (separator [Ai,pi] = [1 /m+1 2] = /m, where m ≥ 1):
s = i-tm,
Si = ‘Rb,i’.
For n > 1 and s ≤ k < i,
Rn,i = ‘b ‹Ai,1’› b [Ai,1] b ‹Ai,2’› b [Ai,2] ... b ‹Ai,pi-1’› b [Ai,pi-1] b ‹Rn-1,s› b /m ci-1 #i’,
Rn,k = ‘b ‹Ak,1’› b [Ak,1] b ‹Ak,2’› b [Ak,2] ... b ‹Ak,pk-1’› b [Ak,pk-1] b ‹Rn,k+1› b [Ak,pk] ck-1 #k’,
R1,s = ‘0’.
Rule A5b (Rule A5a does not apply, separator [Ai,pi] = [1 [Ai+1,1] 1 [Ai+1,2] ... 1 [Ai+1,pi+1] ci+1 #i+1],
which is an m-hyperseparator, where pi+1 ≥ 1, ci+1 ≥ 2 and m ≥ 1):
Si = ‘b ‹Ai,1’› b [Ai,1] b ‹Ai,2’› b [Ai,2] ... b ‹Ai,pi-1’› b [Ai,pi-1] b ‹Si+1› b [Ai,pi] ci-1 #i’.
Increment i, t1, t2, ... , tm by 1; reset tm+1, tm+2, ... , tx to 0 and repeat Rules A5a-c. (i = t1+1.)
Rule A5c (Rules A5a-b do not apply):
Si = ‘b ‹Ai,1’› b [Ai,1] b ‹Ai,2’› b [Ai,2] ... b ‹Ai,pi’› b [Ai,pi] ci-1 #i’.
Rule A6 (Rules A1-5 do not apply):
‘a ‹n #› b’ = ‘a ‹n-1 #› b [n #] a ‹n-1 #› b [n #] ... [n #] a ‹n-1 #› b’
(with b ‘a ‹n-1 #› b’ strings).
Notes:
1. A, B, Ai,1, Ai,2, ... , Ai,pi are strings of characters within separators.
2. Ai,1’, Ai,2’, ... , Ai,pi’ are strings of characters within angle brackets that are identical to the strings
Ai,1, Ai,2, ... , Ai,pi respectively except that the first entries of each have been reduced by 1. If Ai,j
(for some 1 ≤ j ≤ pi) begins with 1, Ai,j’ begins with 0.
3. Si and Rn,k are string building functions which create strings of characters. The R functions involve
nesting the same string of characters around itself n-1 times before being replaced by the string
‘0’.
4. #, #* and #i are strings of characters representing the remainder of the array (can be null or
empty).
5. A /n symbol is an n-hyperseparator, /n enclosed by m pairs of square brackets (with no /k symbols
enclosed by fewer than k+m-n pairs of square brackets, for any k) is an (n-m)-hyperseparator
(when n > m) and a normal separator (or 0-hyperseparator) otherwise. A separator containing no
slashes whatsoever is a normal separator.
6. The comma is used as shorthand for the [1] separator.
7. /n is used as shorthand for the [1 /n+1 2] separator.
== Hierarchical Hyper Nested Array Notation ==
Rule A5a2 (separator [Ai,pi] = //):
s = i-tω,
h = EndSub(‘#s’) (subscript at the end of #s, this is 1 by default),
#*s = DelEndSub(‘#s’) (identical to #s but with the end subscript (h) deleted),
#n,s = ‘#*s h+b-n’ (1 < n < b),
#n,k = ‘#k’ (1 < n ≤ b, s < k ≤ i),
Si = ‘Rb,i’.
For 1 < n ≤ b and s ≤ k < i,
Rn,i = ‘b ‹Ai,1’› b [Ai,1] b ‹Ai,2’› b [Ai,2] ... b ‹Ai,pi-1’› b [Ai,pi-1] b ‹Rn-1,s› b // ci-1 #n,i’,
Rn,k = ‘b ‹Ak,1’› b [Ak,1] b ‹Ak,2’› b [Ak,2] ... b ‹Ak,pk-1’› b [Ak,pk-1] b ‹Rn,k+1› b [Ak,pk] ck-1 #n,k’,
R1,s = ‘0’.
Rule A5a2 (separator [Ai,pi] = //m, where m ≥ 1):
s = i-tω+m-1,
h = EndSub(‘#s’) (subscript at the end of #s, this is 1 by default),
#*s = DelEndSub(‘#s’) (identical to #s but with the end subscript (h) deleted),
#n,s = ‘#*s h+b-n’ (1 < n < b, m = 1),
#n,k = ‘#k’ (1 < n ≤ b and either s < k ≤ i or k = s, m ≥ 2),
Si = ‘Rb,i’.
For 1 < n ≤ b and s ≤ k < i,
Rn,i = ‘b ‹Ai,1’› b [Ai,1] b ‹Ai,2’› b [Ai,2] ... b ‹Ai,pi-1’› b [Ai,pi-1] b ‹Rn-1,s› b //m ci-1 #n,i’,
Rn,k = ‘b ‹Ak,1’› b [Ak,1] b ‹Ak,2’› b [Ak,2] ... b ‹Ak,pk-1’› b [Ak,pk-1] b ‹Rn,k+1› b [Ak,pk] ck-1 #n,k’,
R1,s = ‘0’.
Take [Xk] = [1 [1 [ ... [1 [1 //k 3] 2] ... ] 2] 2] (with k pairs of square brackets).
The θ(ε(Ωω+k-2+1)) level separator (k ≥ 2)
{a, b [1 [Xk] 2] 2} = {a ‹0 [Xk] 2› b}
= {a ‹S1› b}.
Since p1 = 1, c1 = 2, #1 = #* = ‘’ (blank),
[A1,1] = [Xk] (1-hyperseparator),
pj = 1, cj = 2, #j = ‘’ (blank),
[Aj,1] = [1 [1 [ ... [1 [1 //k 3] 2] ... ] 2] 2]
((ω+j-2)-hyperseparator, with k-j+1 pairs of square brackets),
for 2 ≤ j ≤ k, and
pk+1 = 1, ck+1 = 3, #k+1 = ‘’ (blank),
[Ak+1,1] = //k ((ω+k-1)-hyperseparator),
by the jth of k applications of Rule A5b (m = 1 when j = 1 and m = ω+j-2 when 2 ≤ j ≤ k),
Sj = ‘b ‹Sj+1› b’,
t1 = j, tω = j-1, tω+1 = j-2, tω+2 = j-3, ... , tω+j-2 = 1, tω+j-1 = tω+j = ... = tω+k-1 = 0
16
(t-counters finish on t1 = k, tω = k-1, tω+1 = k-2, tω+2 = k-3, ... , tω+k-2 = 1, tω+k-1 = 0),
and by Rule A5a2 (m = k, s = k+1; the Rn,k string is disregarded as s = i; #n,s = ‘#s’ as m ≥ 2),
Sk+1 = ‘Rb,k+1’,
Rn,k+1 = ‘b ‹Rn-1,k+1› b //k 2’,
R1,k+1 = ‘0’.
It follows that,
{a, b [1 [Xk] 2] 2} = {a ‹b ‹b ‹ ... ‹b ‹S› b› ... › b› b› b}
(with k pairs of angle brackets),
where S = ‘b ‹b ‹b ‹ ... ‹b ‹b //k 2› b //k 2› ... › b //k 2› b //k 2› b’
(with b-1 pairs of angle brackets and //k’s).
Rules A5a, A5a2 and A5a3 can actually be combined into a revised Rule A5a now. The complete
Rule A5 is as follows:-
Rule A5 (Rules A1-4 do not apply, first entry is 0, separator immediately prior to next non-1 entry (c1)
is [A1,p1]):
‘a ‹ 0 [A1,1] 1 [A1,2] ... 1 [A1,p1] c1 #1 #* › b’ = ‘a ‹S1 #*› b’,
where p1 ≥ 1, each of [A1,j] is either a normal separator or 1-hyperseparator, #1 contains no 2- or
higher order hyperseparators or subscript in its base layer and #* is either an empty string or subscript
or begins with a 2- or higher order hyperseparator.
Set i to 1 and t1 to 0 and follow Rules A5a-c (a, a* and c are terminal, b is not).
26
Rule A5a (separator [Ai,pi] = /m,m*, where m ≥ 1 and m* ≥ 1):
Set r to 1. For each j from 1 to i-1, increment r by 1 when either mj* < m*, or mj* = m* and mj < m.
s = i-tr,
h = EndSub(‘#s’) (subscript at the end of #s, this is 1 by default),
#*s = DelEndSub(‘#s’) (identical to #s but with the end subscript (h) deleted),
#n,s = ‘#*s h+b-n’ (1 < n < b, m = 1, m* ≥ 2),
#n,k = ‘#k’ (1 < n ≤ b, s ≤ k ≤ i, except k = s, m = 1, m* ≥ 2),
Si = ‘Rb,i’.
For 1 < n ≤ b and s ≤ k < i,
Rn,i = ‘b ‹Ai,1’› b [Ai,1] b ‹Ai,2’› b [Ai,2] ... b ‹Ai,pi-1’› b [Ai,pi-1] b ‹Rn-1,s› b /m,m* ci-1 #n,i’,
Rn,k = ‘b ‹Ak,1’› b [Ak,1] b ‹Ak,2’› b [Ak,2] ... b ‹Ak,pk-1’› b [Ak,pk-1] b ‹Rn,k+1› b [Ak,pk] ck-1 #n,k’,
R1,s = ‘0’.
Rule A5a* (separator [Ai,pi] = [d #H m], where d ≥ 2 and #H contains a (1, k)-hyperseparator as the
highest order hyperseparator in its base layer, where k ≥ 2):
Si = ‘b ‹Ai,1’› b [Ai,1] b ‹Ai,2’› b [Ai,2] ... b ‹Ai,pi-1’› b [Ai,pi-1] Rb [d #H m] ci-1 #i’,
Rn = ‘b ‹Rn-1› b’ (n > 1),
R1 = ‘b [d-1 #H m+b-1] b’.
Rule A5b (Rule A5a does not apply, separator [Ai,pi] = [1 [Ai+1,1] 1 [Ai+1,2] ... 1 [Ai+1,pi+1] ci+1 #i+1],
which is an (mi, mi*)-hyperseparator, where pi+1 ≥ 1, ci+1 ≥ 2, mi ≥ 1 and mi* ≥ 1):
Si = ‘b ‹Ai,1’› b [Ai,1] b ‹Ai,2’› b [Ai,2] ... b ‹Ai,pi-1’› b [Ai,pi-1] b ‹Si+1› b [Ai,pi] ci-1 #i’.
Set r to 1 and f to 0. For each j from 1 to i-1, increment r by 1 when either mj* < mi*, or mj* = mi* and
mj ≤ mi; and set f to 1 when mj* = mi* and mj = mi.
Increment t1, t2, ... , tr by 1; set tr to tr-1 if f = 1; reset tr+1, tr+2, ... , ti to 0; set ti+1 to 0; increment i by 1
(so that i = t1+1) and repeat Rules A5a-c.
Rule A5c (Rules A5a-b do not apply):
Si = ‘b ‹Ai,1’› b [Ai,1] b ‹Ai,2’› b [Ai,2] ... b ‹Ai,pi’› b [Ai,pi] ci-1 #i’.
The θ(Ωω^Ω3) level separator on page 11 has a sequence of five [Ai,pi] separators, as follows:
[A1,1] = [1 [1 [1 [1 /3 2 /2,2 2] 2 2] 2 /2,2 2] 2], [m1, m1*] = [1],
[A2,1] = [1 [1 [1 /3 2 /2,2 2] 2 2] 2 /2,2 2], [m2, m2*] = [1, 2],
[A3,1] = [1 [1 /3 2 /2,2 2] 2 2], [m3, m3*] = [2],
[A4,1] = [1 /3 2 /2,2 2], [m4, m4*] = [1, 2],
[A5,1] = /3, [m5, m5*] = [3].
We start with i = 1 and t1 = 0. By the first application of Rule A5b, we have r = 1 and f = 0, and so,
t1 = 1 ([1] counter), t2 = 0 (new counter).
By the second application of Rule A5b (i = 2), we have r = 2 and f = 0, and so,
t1 = 2 ([1] counter), t2 = 1 ([1, 2] counter), t3 = 0 (new counter).
By the third application of Rule A5b (i = 3), we have r = 2 and f = 0, and so,
t1 = 3 ([1] counter), t2 = 2 ([2] counter), t3 = 0 ([1, 2] counter), t4 = 0 (new counter).
By the fourth application of Rule A5b (i = 4), we have r = 4 and f = 1, and so,
t1 = 4 ([1] counter), t2 = 3 ([2] counter), t3 = t4 = 1 ([1, 2] counters), t5 = 0 (new counter).
By Rule A5a (i = 5), we have m = 3, m* = 1, r = 3 and s = i-tr = 4 (s is unchanged). The t1 counter is
always a [1] counter (as [m1, m1*] is always [1]), while the tr counter is the first counter to count
[m, m*] or beyond.
Rule A5b (Rule A5a does not apply, separator [Ai,pi] = [1 [Ai+1,1] 1 [Ai+1,2] ... 1 [Ai+1,pi+1] ci+1 #i+1],
which is an (mi,1, mi,2, ... , mi,qi)-hyperseparator, where pi+1 ≥ 1, ci+1 ≥ 2, qi ≥ 1, mi,j ≥ 1 (for all 1 ≤ j ≤ qi)
and mi,qi ≥ 2 (qi ≥ 2)):
Si = ‘b ‹Ai,1’› b [Ai,1] b ‹Ai,2’› b [Ai,2] ... b ‹Ai,pi-1’› b [Ai,pi-1] b ‹Si+1› b [Ai,pi] ci-1 #i’.
Set r to 1 and f to 0. For each j from 1 to i-1, increment r by 1 when either qj < qi or qj = qi and there
exists a number n such that mj,n < mi,n and mj,k = mi,k (for all n < k ≤ qi); and increment r by 1 and set f
to 1 when qj = qi and mj,k = mi,k (for all 1 ≤ k ≤ qi).
35
Increment t1, t2, ... , tr by 1; set tr to tr-1 if f = 1; reset tr+1, tr+2, ... , ti to 0; set ti+1 to 0; increment i by 1
(so that i = t1+1) and repeat Rules A5a-c.
Rules A5a and A5a* are modified as follows:-
Rule A5a (separator [Ai,pi] = /m1,m2,...,mq, where q ≥ 1 and mq ≥ 2 (q ≥ 2)):
Set r to 1. For each j from 1 to i-1, increment r by 1 when either qj < q or qj = q and there exists a
number n such that mj,n < mn and mj,k = mk (for all n < k ≤ q).
s = i-tr,
H = EndSub(‘#s’) (subscript array at the end of #s, this is 1 by default),
hk = Sub(H, k) (kth subscript of subscript array H = ‘h1,h2,...’),
#*s = DelEndSub(‘#s’) (identical to #s but with the end subscript array (H) deleted),
#n,s = ‘#*s h1,h2,...,hk-1,(hk+b-n),hk+1,hk+2,...’
(1 < n < b, mj = 1 (for all 1 ≤ j ≤ k), mk+1 ≥ 2),
#n,k = ‘#k’ (1 < n ≤ b, s ≤ k ≤ i, except k = s, m1 = 1, q ≥ 2),
Si = ‘Rb,i’.
36
For 1 < n ≤ b and s ≤ k < i,
Rn,i = ‘b ‹Ai,1’› b [Ai,1] b ‹Ai,2’› b [Ai,2] ... b ‹Ai,pi-1’› b [Ai,pi-1] b ‹Rn-1,s› b /m1,m2,...,mq ci-1 #n,i’,
Rn,k = ‘b ‹Ak,1’› b [Ak,1] b ‹Ak,2’› b [Ak,2] ... b ‹Ak,pk-1’› b [Ak,pk-1] b ‹Rn,k+1› b [Ak,pk] ck-1 #n,k’,
R1,s = ‘0’.
Rule A5a* (separator [Ai,pi] = [d #H m1,m2,...], where d ≥ 2 and #H contains a (1, 1, ... , 1, r1, r2, ...)-
hyperseparator (with k 1’s) as the highest order hyperseparator in its base layer, where k ≥ 1 and
r1 ≥ 2):
Si = ‘b ‹Ai,1’› b [Ai,1] b ‹Ai,2’› b [Ai,2] ... b ‹Ai,pi-1’› b [Ai,pi-1] Rb [d #H m1,m2,...] ci-1 #i’,
Rn = ‘b ‹Rn-1› b’ (n > 1),
R1 = ‘b [d-1 #H 1,...,1,mk+b-1] b’ (with k-1 1’s in subscript).
In Rule A5a*, any of the mj for 1 ≤ j ≤ k and rj for j ≥ 2 may take the value 1 (mj = 1 for all j > k).
Subscripts and hyperlevels are written with trailing 1’s removed. For example, if nk ≥ 2 but ni = 1 for all
i > k, then /n1,n2,... = /n1,n2,...,nk, [X n1,n2,...] = [X n1,n2,...,nk] and ‹X n1,n2,...› = ‹X n1,n2,...,nk› for a string X, and an
(n1, n2, ...)-hyperseparator would be an (n1, n2, ... , nk)-hyperseparator. If ni = 1 for all i, then
/n1,n2,... = /, [X n1,n2,...] = [X] and ‹X n1,n2,...› = ‹X› for a string X, and an (n1, n2, ...)-hyperseparator would
be a 1-hyperseparator.
Note that Rule A5a* with #H containing the lowest (1, 1, ... , 1, r1, r2, ...)-hyperseparator (with k 1’s), as
follows,
[Ai,pi] = [2 /1,1,...,1,r1,r2,... 2 m1,m2,...] (with k 1’s after slash and mj = 1 for all j > k)
would mean that
R1 = ‘b [1 /1,1,...,1,r1,r2,... 2 1,...,1,mk+b-1] b’ (with k 1’s on left subscript and k-1 1’s on right)
= ‘b /1,...,1,mk+b-1,r1-1,r2,... b’ (with k-1 1’s after slash),
which is how the (k+1)th subscript of the slash symbol is reduced by 1. (The kth subscript becomes
mk+b-1; all other subscripts remain unchanged.)
Rule A3 is changed as follows:-
Rule A3 (last entry in any 1-space or higher dimensional space of array is 1):
‘a ‹# [A] 1 n1,n2,...,nk› b’ = ‘a ‹# n1,n2,...,nk› b’.
When [A] is an (m1, m2, ... , mp)-hyperseparator, [B] is an (n1, n2, ... , nq)-hyperseparator and either
p < q; p = q and there exists a number k such that mk < nk and mi = ni (for all k < i ≤ p); or p = q,
mi = ni (for all 1 ≤ i ≤ p) and level of [A] is less than level of [B],
‘a ‹# [A] 1 [B] #*› b’ = ‘a ‹# [B] #*› b’.
Remove trailing 1’s.
The θ(Ωω^ω^2) level separator
{a, b [1 [2 /1 [3] 2 2] 2] 2} = {a ‹0 [2 /1 [3] 2 2] 2› b}
= {a ‹b ‹b ‹ ... ‹b ‹b /1 ‹2› b (←b) b› b› ... › b› b› b}
(with b pairs of angle brackets outside subscript),
where the (←b) means replace the final entry by b. Since
‘1 ‹2› b (←b)’ = ‘1 ‹1› b [2] 1 ‹1› b [2] ... 1 ‹1› b [2] 1 ‹1› b (←b)’ (with b-1 [2]’s)
= ‘1,1,..,1 [2] 1,1,..,1 [2] .... 1,1,..,1 [2] 1,1,..,1,b’ (b-1 1’s after final [2])
= ‘1 [2] 1 [2] ... 1 [2] 1,1,...,1,b’ (remove trailing 1’s),
it follows that
{a, b [1 [2 /1 [3] 2 2] 2] 2} = {a ‹b ‹b ‹ ... ‹b ‹b /1 [2] 1 [2] ... 1 [2] 1,1,...,1,b b› b› ... › b› b› b}
(b pairs of angle brackets, b-1 ‘1 [2]’s and b-1 1’s in 1,1,...,1,b).
In the case of the θ(Ωω^ω) level separator in {a, b [1 [2 /1 [2] 2 2] 2] 2}, the slash subscript array
between the pair of b’s inside the innermost angle brackets on the right-hand side would be /1 ‹1› b (←b)
as this gives /1,1,...,1,b with b-1 1’s. The introduction of the ‘left arrow’ in Rule A5a* means that a few
modifications to Rules A1, A2 and A4 are necessary in order to get rid of the arrow when the angle
brackets disappear.
The following additions are made to Rule A1:
‘a ‹0› b (←c)’ = ‘c’,
‘a ‹1› b (←c)’ = ‘a, a, ... , a, c’ (with b-1 a’s).
The following additions are made to Rule A2:
‘a ‹0 #› b (←c)’ = ‘c’,
‘a ‹1 #› b (←c)’ = ‘a [1 #] a [1 #] ... a [1 #] c’ (with b-1 a’s),
where # begins with a 2- or higher order hyperseparator.
The following addition is made to Rule A4:
‘a ‹A› 1 (←c)’ = ‘c’.
The θ(Ωω^ω^ω) level separator
{a, b [1 [2 /1 [1,2] 2 2] 2] 2} = {a ‹0 [2 /1 [1,2] 2 2] 2› b}
= {a ‹b ‹b ‹ ... ‹b ‹b /1 ‹0,2› b (←b) b› b› ... › b› b› b}
= {a ‹b ‹b ‹ ... ‹b ‹b /1 ‹b› b (←b) b› b› ... › b› b› b}
(with b pairs of angle brackets outside subscript),
where ‘1 ‹b› b (←b)’ = ‘1 ‹b-1› b [b] 1 ‹b-1› b [b] ... 1 ‹b-1› b [b] 1 ‹b-1› b (←b)’ (with b-1 [b]’s)
= ‘1 [b] 1 [b] ... 1 [b] 1 [b-1] 1 [b-1] ... 1 [b-1] ...... 1 [2] 1 [2] ... 1 [2] 1,1,...,1,b’
(b-1 each of [b]’s, [b-1]’s, ... , [2]’s and b-1 1’s after final [2]).
=== Bird’s Nested Hierarchical Hyper-Nested Array Notation – Angle Bracket Rules ===
Rule A1 (only 1 entry of either 0 or 1):
‘a ‹0› b’ = ‘a’,
‘a ‹1› b’ = ‘a, a, ... , a’ (with b a’s),
‘a ‹0› b (←c)’ = ‘c’,
‘a ‹1› b (←c)’ = ‘a, a, ... , a, c’ (with b-1 a’s).
Rule A2 (only 1 entry of either 0 or 1 prior to 2-hyperseparator or higher order hyperseparator):
‘a ‹0 # N› b’ = ‘a’,
‘a ‹1 # N› b’ = ‘a [1 # N] a [1 # N] ... [1 # N] a’ (with b a’s),
‘a ‹0 # N› b (←c)’ = ‘c’,
‘a ‹1 # N› b (←c)’ = ‘a [1 # N] a [1 # N] ... a [1 # N] c’ (with b-1 a’s),
where # begins with a 2- or higher order hyperseparator.
43
Rule A3 (last entry in any 1-space or higher dimensional space of array is 1):
‘a ‹# [A] 1 N› b’ = ‘a ‹# N› b’.
When [A] is an M1-hyperseparator, [B] is an M2-hyperseparator and M1 < M2, or M1 = M2 and [A] < [B],
‘a ‹# [A] 1 [B] #* N› b’ = ‘a ‹# [B] #* N› b’.
Remove trailing 1’s.
Rule A4 (number to right of angle brackets is 1):
‘a ‹A N› 1’ = ‘a’,
‘a ‹A N› 1 (←c)’ = ‘c’.
Rule A5 (Rules A1-4 do not apply, first entry is 0, separator immediately prior to next non-1 entry (c1)
is [A1,p1]):
‘a ‹ 0 [A1,1] 1 [A1,2] ... 1 [A1,p1] c1 #1 #* N1› b’ = ‘a ‹S1 #* N1› b’,
where p1 ≥ 1, each of [A1,j] is either a normal separator or 1-hyperseparator, #1 contains no 2- or
higher order hyperseparators in its base layer and #* is either an empty string or begins with a 2- or
higher order hyperseparator.
Set i to 1 and t1 to 0 and follow Rules A5a-f (a-d and f are terminal, e is not). (Note that i = t1+1
throughout.)
Rule A5a (separator [Ai,pi] = /M,
where M = ‘1 [B1] 1 [B2] ... [Bp-1] 1, m1 [C1] m2 [C2] ... [Cq-1] mq’,
where p ≥ 1, q ≥ 1, m1 ≥ 2, mq ≥ 2 and each of [Bj] (1 ≤ j < p) and [Cj] (1 ≤ j < q) are normal
separators):
Set r to 1. For each j from 1 to i-1, increment r by 1 when Mj < M.
s = i-tr.
The subscript array Ns = ‘n1 [D1] n2 [D2] ... [Dh-1] nh’,
where h ≥ 1, nh ≥ 2 (h ≥ 2) and each of [Dj] (1 ≤ j < h) is a normal separator.
Follow 3-step algorithm (below) until the Nn,s string (for 1 < n < b) is determined.
Step 1: Set x and y to 1 and go to Step 2.
Step 2: If x = p and y = h then Nn,s = ‘n1 [D1] n2 [D2] ... nh-1 [Dh-1] nh+b-n’.
If x = p and y < h then Nn,s = ‘n1 [D1] n2 [D2] ... ny-1 [Dy-1] ny+b-n [Dy] ny+1 [Dy+1] ... nh-1 [Dh-1] nh’.
If x < p and y = h then Nn,s = ‘n1 [D1] n2 [D2] ... nh-1 [Dh-1] nh [Bx] 1 [Bx+1] ... 1 [Bp-1] b+1-n’.
If x < p and y < h then go to Step 3.
Step 3: If [Bx] > [Dy] then increment y by 1 and go to Step 2.
If [Bx] = [Dy] then increment x and y by 1 and go to Step 2.
If [Bx] < [Dy] then Nn,s = ‘n1 [D1] n2 [D2] ... ny-1 [Dy-1] ny [Bx] 1 [Bx+1] ... 1 [Bp-1]
b+1-n [Dy] ny+1 [Dy+1] ... nh-1 [Dh-1] nh’.
We then obtain
Nb,i = ‘Ni’,
Nn,k = ‘Nk’ (1 < n < b, s < k ≤ i),
Si = ‘Rb,i’.
For 1 < n ≤ b and s ≤ k < i,
Rn,i = ‘b ‹Ai,1’› b [Ai,1] b ‹Ai,2’› b [Ai,2] ... b ‹Ai,pi-1’› b [Ai,pi-1] b ‹Rn-1,s› b /M ci-1 #i Nn,i’,
Rn,k = ‘b ‹Ak,1’› b [Ak,1] b ‹Ak,2’› b [Ak,2] ... b ‹Ak,pk-1’› b [Ak,pk-1] b ‹Rn,k+1› b [Ak,pk] ck-1 #k Nn,k’,
R1,s = ‘0’.
44
Rule A5b (Rule A5a does not apply, separator [Ai,pi] = /M,
where M = ‘1 [B1] 1 [B2] ... [Bp-1] 1 [Bp] m1 [C1] m2 [C2] ... [Cq-1] mq’,
where p ≥ 1, q ≥ 1, m1 ≥ 2, mq ≥ 2, [Bp] ≥ [2] and each of [Bj] (1 ≤ j < p) and [Cj] (1 ≤ j < q) are normal
separators):
Si = ‘b ‹Ai,1’› b [Ai,1] b ‹Ai,2’› b [Ai,2] ... b ‹Ai,pi-1’› b [Ai,pi-1] b /M* ci #i /M ci-1 #i Ni’,
where M* = ‘1 [B1] 1 [B2] ... [Bp-1] 1 ‹Bp’› b (←2) [Bp] m1-1 [C1] m2 [C2] ... [Cq-1] mq’.
Rule A5c (Rules A5a-b do not apply, separator [Ai,pi] = /M,
where M = ‘m1 [B1] m2 [B2] ... [Bq-1] mq’,
where q ≥ 1, m1 ≥ 2 (q ≥ 2), mq ≥ 2 (q ≥ 2) and each of [Bj] (1 ≤ j < q) is a normal separator):
Set r to 1. For each j from 1 to i-1, increment r by 1 when Mj < M.
s = i-tr,
Si = ‘Rb,i’.
For 1 < n ≤ b and s ≤ k < i,
Rn,i = ‘b ‹Ai,1’› b [Ai,1] b ‹Ai,2’› b [Ai,2] ... b ‹Ai,pi-1’› b [Ai,pi-1] b ‹Rn-1,s› b /M ci-1 #i Ni’,
Rn,k = ‘b ‹Ak,1’› b [Ak,1] b ‹Ak,2’› b [Ak,2] ... b ‹Ak,pk-1’› b [Ak,pk-1] b ‹Rn,k+1› b [Ak,pk] ck-1 #k Nk’,
R1,s = ‘0’.
Rule A5d (Rules A5a-c do not apply, separator [Ai,pi] = [d #H M], where d ≥ 2 and #H contains a
H-hyperseparator as the highest order hyperseparator in its base layer,
where H = ‘1 [H1] 1 [H2] ... 1 [Hk] h #H*’,
where h ≥ 2, k ≥ 1 and each of [Hj] (1 ≤ j ≤ k) is a normal separator):
Si = ‘b ‹Ai,1’› b [Ai,1] b ‹Ai,2’› b [Ai,2] ... b ‹Ai,pi-1’› b [Ai,pi-1] Rb [d #H M] ci-1 #i Ni’,
Rn = ‘b ‹Rn-1› b’ (n > 1),
R1 = ‘b [d-1 #H 1 [H1] 1 [H2] ... 1 [Hk-1] 1 ‹Hk’› b (←m+b-1)] b’,
where m (which may be 1) is the kth and final entry in the subscript array M when written as
M = ‘m1 [H1] m2 [H2] ... mk-1 [Hk-1] m’.
Rule A5e (Rules A5a-d do not apply, separator [Ai,pi] = [1 [Ai+1,1] 1 [Ai+1,2] ... 1 [Ai+1,pi+1] ci+1 #i+1 Ni+1],
which is an Mi-hyperseparator, where pi+1 ≥ 1, ci+1 ≥ 2 and Mi ≥ ‘1’):
Si = ‘b ‹Ai,1’› b [Ai,1] b ‹Ai,2’› b [Ai,2] ... b ‹Ai,pi-1’› b [Ai,pi-1] b ‹Si+1› b [Ai,pi] ci-1 #i Ni’.
Set r to 1 and f to 0. For each j from 1 to i-1, increment r by 1 when Mj ≤ Mi and set f to 1 when
Mj = Mi.
Increment t1, t2, ... , tr by 1; set tr to tr-1 if f = 1; reset tr+1, tr+2, ... , ti to 0; set ti+1 to 0; increment i by 1
(so that i = t1+1) and repeat Rules A5a-f.
Rule A5f (Rules A5a-e do not apply):
Si = ‘b ‹Ai,1’› b [Ai,1] b ‹Ai,2’› b [Ai,2] ... b ‹Ai,pi’› b [Ai,pi] ci-1 #i Ni’.
Rule A6 (Rules A1-5 do not apply):
‘a ‹n # N› b’ = ‘a ‹n-1 # N› b [n # N] a ‹n-1 # N› b [n # N] ... [n # N] a ‹n-1 # N› b’
(with b ‘a ‹n-1 # N› b’ strings).
Notes:
1. A, B, Ai,1, Ai,2, ... , Ai,pi, Bj, Cj, Dj and Hj are strings of characters within separators. In Rules A3
and A5, the strings A, B, Ai,1, Ai,2, ... , Ai,pi (i ≥ 2) may include subscripts at the end.
45
2. Ai,1’, Ai,2’, ... , Ai,pi’, Bp’ and Hk’ are strings of characters within angle brackets that are identical to
the strings Ai,1, Ai,2, ... , Ai,pi, Bp and Hk respectively except that the first entries of each have been
reduced by 1. If Ai,j (for some 1 ≤ j ≤ pi) begins with 1, Ai,j’ begins with 0.
3. M, M*, N, Ni and Nn,k are strings of characters that make up subscript arrays.
4. Mi and H are strings of characters that describe hyperlevels (hyperseparator levels).
5. Si, Rn and Rn,k are string building functions which create strings of characters. The R functions
involve nesting the same string of characters around itself n-1 times before being replaced by the
string ‘0’.
6. #, #*, #i, #H and #H* are strings of characters representing the remainder of the array (can be null
or empty), excluding any subscripts at the end. Here, the H and H* subscripts are labels and not
variables or strings of characters.
7. In Rules A5b and A5d, a ‘left arrow’ is created, which is shown within brackets next to a number
and placed to the right of an angle bracket array (with 1 and b either side), namely ‘1 ‹Bp’› b (←2)’
within M* in the former subrule and ‘1 ‹Hk’› b (←m+b-1)’ within the subscript array within R1 in the
latter. The angle brackets resolve to a string of 1’s and separators (of descending level with b-1 of
each level down to the [1] separator or comma), and the final entry of 1 is replaced by the number
next to the ‘left arrow’. The arrow is finally removed along with the angle brackets immediately to
its left, using Rules A1, A2 or A4.
8. A /N symbol is an N-hyperseparator. A recursive definition of hyperseparators is given on page 41.
A separator that contains no 2- or higher order hyperseparators in its ‘base layer’ is a normal
separator (or 0-hyperseparator).
9. The comma is used as shorthand for the [1] separator.
10. When a separator [A] = /N and it is necessary to find the string A’ (identical to A but for the first
entry being reduced by 1), the /N is used as shorthand for the [1 /N* 2] separator, where N* is
identical to N except that the first entry has been increased by 1. In this case, A’ = ‘0 /N* 2’, which
means that ‘b ‹A’› b’ = ‘b ‹0 /N* 2› b’ = ‘b’ (by Rule A2).
11. Any 2- or higher hyperseparator may carry a subscript.
12. The [1 /M 2 N] separator (M ≠ ‘1’) reduces to a /X symbol, for a subscript array X, according to a
special rule (see below).
Whenever we encounter a separator of the form [1 /X 2 Y] (with a slash symbol between the only two
entries of 1 and 2), where X and Y are subscript arrays and X ≠ ‘1’, this separator ‘drops down’ to a
simple slash symbol of the form /Z, where Z is another subscript array. This special rule is known as
the Dropping Down Rule.
Dropping Down Rule (separator is of the form [1 /M 2 N] with M ≠ ‘1’, i.e. has only two entries of 1 and
2 to left and right respectively of slash subscript array, which is a 2- or higher order hyperseparator):
[1 /1 [A1] 1 [A2] ... 1 [Am] nm+1 # 2 n1 [A1] n2 [A2] ... [Ak-1] nk]
= /n1 [A1] n2 [A2] ... nk [Ak] 1 [Ak+1] 1 [Ak+2] ... 1 [Am] nm+1-1 #,
where 0 ≤ k ≤ m, nm+1 ≥ 2, each of [Ai] is a normal separator and # represents the remainder of the
slash subscript array.
When k = m, the Dropping Down Rule becomes:
[1 /1 [A1] 1 [A2] ... 1 [Am] nm+1 # 2 n1 [A1] n2 [A2] ... [Am-1] nm]
= /n1 [A1] n2 [A2] ... nm [Am] nm+1-1 #.
When k = 0, the Dropping Down Rule becomes:
[1 /1 [A1] 1 [A2] ... 1 [Am] nm+1 # 2]
= /1 [A1] 1 [A2] ... 1 [Am] nm+1-1 #.
46
When k = m = 0, the Dropping Down Rule becomes:
[1 /n1 # 2] = /n1-1 #.
Trailing 1’s in subscript arrays are removed as with separator arrays and angle bracket arrays. For
example,
/# [A] 1 = /# and [X # [A] 1] = [X #].
When [A] < [B],
/# [A] 1 [B] #* = /# [B] #* and [X # [A] 1 [B] #*] = [X # [B] #*].
This is my complete Nested Hierarchical Hyper-Nested Array Notation. The limit ordinal of this
notation is θ(ΩΩ). The Extended Kruskal Theorem (Kruskal’s Tree Theorem extended to labelled
trees) and Buchholz Hydras with finite numbers as labels gets us as far as the θ(Ωω) level in the
fast-growing hierarchy. However, if we use trees as labels for trees, then use those trees as labels for
even larger trees, and so on, we also reach a limit of θ(ΩΩ) in the hierarchy of fast-growing functions!
This notation works for simple nested arrays up to ε0 level without requiring Rules A2 and A5a-e.
These rules only become necessary when one wishes to travel beyond the following ordinals or use
the associated separators, as shown below:
Ordinal Separator Rule
ε0 [1 / 2] A5c
φ(ω, 0) [1 [2 /2 2] 2] A2
Γ0 [1 [1 / 2 /2 2] 2] A5e
θ(Ωω) [1 [2 /1,2 2] 2] A5d
θ(Ωω+1) [1 [1 /1,2 3] 2] A5a
θ(Ωω^ω+1) [1 [1 /1 [2] 2 3] 2] A5b
In Rule A5a, the 3-step algorithm begins initially with Step 1 (set x and y to 1), then shuttles between
the other two steps until a solution for the Nn,s subscript array is found. In Step 2, Nn,s is determined
when either x = p or y = h (reached end of either [Dj] separators or [Bj] preceding final 1 and comma
prior to first non-1 entry), otherwise it moves to Step 3. In Step 3, Nn,s is immediately found when the
xth B-separator of M is of lower level than the yth D-separator of Ns, or [Bx] < [Dy] (as [Bj] < [Dy] for all
x < j < p), otherwise y is increased by 1 (and also x if [Bx] and [Dy] are identical) before jumping back
to Step 2.
== See also ==
* H function
* S function
* U function
* BEAF
* Introduction to Bird's array notation
== Sources ==
ja:バードの配列表記
zh:鳥數陣記號
Category:Notations
Category:Functions
Category:Array Notations