在给定的 Wheeler NFA $A$ 中，Wheeler 确定化问题是构造一个接受与 $A$ 相同语言的 Wheeler DFA $B$。我们用 $n_{A}, m_{A}$ 表示 $A$ 的顶点和边的数量，等价地用 $n_{B}, m_{B}$ 表示 $B$。根据 Alanko 等人 [SODA 2020, Inf. Comp. 2021] 的研究，该问题的解决时间为 $O(n_{A}^3)$。
本文中，我们展示了在给定 $A$ 的 Wheeler 顺序时，如何将运行时间改进为 $O(n_{A} + m_{A} + n_{B} + m_{B})$，而该 Wheeler 顺序可以通过 Becker 等人的算法 [ESA 2023] 在 $O(m_{A}\log n_{A})$ 时间内计算得到。我们的运行时间比现有技术快了一个因子 $n_{A}^2/\sigma$，其中 $\sigma$ 是字母表的大小。
此外，对于 $\sigma=O(1)$ 的情况，我们提供了该问题的首个线性时间算法。我们还展示了对于任何组合的 $n$ 和 $\sigma$，我们的界限在已排序输入的情况下是紧的，通过提供一系列输入，确保我们的输出 $B$ 是最小的，且最大大小为 $\Theta(n\sigma)$。
博主点评： 本文在 Wheeler 确定化问题上提出了显著的时间复杂度改进，尤其是在给定 Wheeler 顺序的情况下，体现了算法优化的潜力。线性时间算法的出现为处理此类问题提供了新的视角，值得进一步研究其在实际应用中的表现。