0-Y

0-Y是一种Worm型序数记号，它是PrSS的一种扩展。

定义

合法表达式

一个合法的 0-Y 表达式是以 1 开头的正整数序列，即形如

$(a_1,a_2,\cdots ,a_n)(n,a_1,a_2,\cdots ,a_n\in \mathbb{\mathbb{N}},a_1=1)$

的序列。

例如：$(1,4,6,4)$和$(1,1,4,5,1,4)$都是合法的 0-Y 表达式，而$(1,2,\pi )$不是。

结构

0-Y的合法表达式可分为零表达式、后继表达式和极限表达式。

• 零表达式指$n=0$的表达式，即空序列；
• 后继表达式指$n>0,a_n=1$的表达式，即末项为1的非空序列；
• 极限表达式指$n>0,a_n>1$的表达式，末项不为1的非空序列。

对于 0-Y 的一个极限表达式$(a_1,a_2,\cdots ,a_n)$，定义以下术语：

行标与列标

设想我们在一个无限大的矩阵下工作，从左往右是第1,2,...列，从下往上是第0,1,...行。第$i$行第$j$列的项记为$x_{i,j}$。

初始时，我们有$x_{0,j}=a_j$，$1\le j\le n$。

父项与阶差项

等于1的项没有父项。对于大于1的项$x_{i,j}$，它的父项与它位于同一行，且是满足以下条件的最右侧项$x_{i,k}$：

• $k<j$且$x_{i,k}<x_{i,j}$。
• 如果$i>0$，还要求$x_{i-1,k}$是$x_{i-1,j}$的祖先项。

这里“祖先项”的定义类似于BMS：一个元素自己，以及它的父项、父项的父项、父项的父项的父项......共同构成它的祖先项。

对于$x_{i,j}$，如果它有父项$x_{i,k}$，则它的阶差项为$x_{i+1,j}=x_{i,j}-x_{i,k}$；如果$x_{i,j}=1$，则它的阶差项$x_{i+1,j}=1$。

由于第$i$行的项的阶差项构成了第$i+1$行，称第$i+1$行的序列是第$i$行的序列的阶差序列。

末列与坏根

第$n$列称为末列。

对于末列的某一项$x_{i,n}$，它的父项设为$x_{i,r}$。如果在计算到某行(第$p$行)时有$x_{p,n}-x_{p,r}=1$，则称$a_r$为坏根，称第$r$列为根列，并且不再计算第$p+1$行及之后的行。

以上给出了 0-Y 极限表达式$(a_1,a_2,\cdots ,a_n)$的完整寻找坏根流程。

山脉图

要描述0-Y的展开规则，需要用到山脉图的辅助。对于 0-Y 的一个极限表达式$(a_1,a_2,\cdots ,a_n)$，它的山脉图的画法如下：

先按照寻找坏根的规则画出第0到$p$行。现在你有了一个$p\times n$的“矩阵”(第0至第$p$行，第1至第$n$列)，接下来，对于第$i$行，$0\le i\le p-1$进行如下操作：

对于每个$x_{i,j}$，用竖直线段连接$x_{i+1,j}$的下端与$x_{i,j}$的上端。这些竖直线段称为右腿，$x_{i,j}$称为它的端点。

对于每个大于1的$x_{i,j}$，设$x_{i,j}$有父项$x_{i,k}$，用斜线段连接$x_{i+1,j}$的下端与$x_{i,k}$的上端。这些斜线段称为左腿，$x_{i,k}$称为它的端点。

对第1到第$p$行各执行一次上述操作，就得到了$(a_1,a_2,\cdots ,a_n)$的山脉图。

注意：有些情况下，山脉图只包含一行，即第0行。

注：由于山脉图的某一行只和其下的项有关，你也可以在逐行往上填写阶差序列的同时画出山脉图。许多常见的0-Y教程都采用这个方法。

(待补充附有配图的0-Y山脉图绘制例子,以及绘制0-Y山脉图的网站(有吗))

展开

对于 0-Y 的一个表达式$(a_1,a_2,\cdots ,a_n)$：

• 如果它是零表达式，它对应序数0。
• 如果它是后继表达式，它对应$(a_1,a_2,\cdots ,a_{n-1})$的后继。
• 如果它是极限表达式，它的基本列第$q$项如下确定：

1. 作出$p\times n$的山脉图。称位于根列右侧的结构(包括阶差项和其对应的山脉图中的左右腿，不包括根列)为坏部，其余为好部。
2. 删除坏部中第$p$行以下的所有项，并将$x_{p,n}$减1。
3. 接下来，保留山脉图的好部不动，将坏部平移并复制在山脉图末尾，复制$q-1$次。“坏部平移”是指左右腿及端点同时平移。
4. 特别地，如果某一条左腿的端点位于根列左侧，复制时左腿的端点不向右平移。
5. 接下来，你得到了根列右侧的一系列山脉图和第$p$行的一系列项。从根列右侧开始，从上到下，每一行从左到右，按照以下方式填入正整数：对于某个位置，向上通过右腿移动到值为$x$的项，然后向左下通过左腿移动到值为$y$的项，则回到初始位置并填上$x+y$。
6. 最后得到的第0行的序列，就是$(a_1,a_2,\cdots ,a_n)$展开的基本列第$q-1$项。

0-Y的极限基本列是$\{(1,2),(1,3),(1,4),\cdots \}$，从这个基本列中元素开始取前驱或取基本列所能得到的表达式是 0-Y 的标准式。

(待补充附有配图的0-Y展开例子,比如Y(1,4,6,4)和Y(1,4,6,3,7,9,7),后者有不平移的端点)

枚举

我们使用 BMS 对 0-Y 进行简单分析(左边是BMS，右边是0-Y)。

$(0)=1$

$(0)(1)=1,2$

$(0)(1)(1)=1,2,2$

$(0)(1)(2)=1,2,3$

$(0)(1)(2)(3)=1,2,3,4$

$(0)(1,1)=1,3$

$(0)(1,1)(1,0)=1,3,2$

$(0)(1,1)(1,0)(2,1)=1,3,2,4$

$(0)(1,1)(1,1)=1,3,3$

$(0)(1,1)(2,0)=1,3,4$

$(0)(1,1)(2,0)(3,1)=1,3,4,6$

$(0)(1,1)(2,1)=1,3,5$

$(0)(1,1)(2,1)(3,1)=1,3,5,7$

$(0)(1,1)(2,2)=1,3,6$

$(0)(1,1)(2,2)(3,3)=1,3,6,10$

$(0)(1,1,1)=1,4$

$(0)(1,1,1)(1,0,0)(2,1,1)=1,4,2,5$

$(0)(1,1,1)(1,1,0)=1,4,3$

$(0)(1,1,1)(1,1,0)(2,2,1)=1,4,3,7$

$(0)(1,1,1)(1,1,1)=1,4,4$

$(0)(1,1,1)(2,0,0)=1,4,5$

$(0)(1,1,1)(2,1,0)=1,4,6$

$(0)(1,1,1)(2,1,0)(1,1,1)=1,4,6,4$

$(0)(1,1,1)(2,1,0)(3,1,0)=1,4,6,8$

$(0)(1,1,1)(2,1,0)(3,2,1)=1,4,6,10$

$(0)(1,1,1)(2,1,1)=1,4,7$

$(0)(1,1,1)(2,1,1)(3,1,1)=1,4,7,10$

$(0)(1,1,1)(2,2,0)=1,4,8$

$(0)(1,1,1)(2,2,1)=1,4,9$

$(0)(1,1,1)(2,2,2)=1,4,10$

$(0)(1,1,1)(2,2,2)(3,3,3)=1,4,10,20$

$(0)(1,1,1,1)=1,5$

$(0)(1,1,1,1,1)=1,6$

$\cdots$

两者极限相等。

与BMS的互译

事实上，0-Y与BMS有十分简单的互译关系。

(等待更新)