查看“︁UPS”︁的源代码

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

== 定义 ==

=== 基础定义 ===
一个 UPS 表达式由一组有序排列的项组成。

项：一个自然数与一个星号标记 <math>\alpha_i = (v_i, s_i)</math> 。

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

正规化序列：一个序列 <math>S = [\alpha_0, \alpha_1, ..., \alpha_{L-1}]</math> 的正规化序列为 <math>\mathrm{norm}(S) = [\alpha'_0, \alpha'_1, ..., \alpha'_{L-1}]</math>, 其中 <math>\alpha'_i = (v_i - v_0, s_i)</math> 。

=== 直接集与直接段 ===
一个索引 <math>i</math> 的直接集定义为：

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

定义索引 <math>i</math> 的直接段为 <math>\mathrm{seg}(i) = [\alpha_i, ..., \alpha_{\mathrm{ed}(i)}]</math> 。