UPS

UPS（Upper Projection Sequence, 向上投影序列）是由 Optimism 最初创作，Alice 完善的记号，旨在以序列形式模拟向上投影。

定义

基础定义

一个 UPS 表达式由一组有序排列的项组成。

项：一个自然数与一个星号标记 ${\alpha }_i=(v_i,s_i)$ 。

父项：一个索引的父项 $p(i)$ 为最大的 $j<i$, 满足 $v_j<v_i$ 。

正规化序列：一个序列 $S=[{\alpha }_0,{\alpha }_1,...,{\alpha }_{L-1}]$ 的正规化序列为 $\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}(S)=[\alpha {\text{'}}_0,\alpha {\text{'}}_1,...,\alpha {\text{'}}_{L-1}]$, 其中 $\alpha {\text{'}}_i=(v_i-v_0,s_i)$ 。

直接集与直接段

一个索引 $i$ 的直接集定义为：

1. $i\in D(i)$;
2. 若 $p(j)\in D(i),s_{p(j)}=1$, 则 $j\in D(i)$ 。

定义直接段结尾：令 $M(i)=\max (t|t\in D(i))$若存在 $k$ 使得 $v_k=\min (v_j|j>M(i),p(j)\in D(i))$, 找到其中索引最小的 $k_0$ , 定义 $\mathrm{e}\mathrm{d}(i)=k_0$; 否则，定义 $\mathrm{e}\mathrm{d}(i)=M(i)$ 。

定义索引 $i$ 的直接段为 $\mathrm{s}\mathrm{e}\mathrm{g}(i)=[{\alpha }_i,...,{\alpha }_{\mathrm{e}\mathrm{d}(i)}]$ 。