In a given Wheeler NFA $A$, the Wheeler determinization problem is to construct a Wheeler DFA $B$ that accepts the same language as $A$. We denote $n_{A}, m_{A}$ as the number of vertices and edges of $A$, and equivalently $n_{B}, m_{B}$ for $B$. Alanko et al. [SODA 2020, Inf. Comp. 2021] showed that this problem can be solved in $O(n_{A}^3)$ time.
In this paper, we demonstrate how to improve the running time to $O(n_{A} + m_{A} + n_{B} + m_{B})$ when given the Wheeler order of $A$, which can be computed in $O(m_{A}\log n_{A})$ with an algorithm by Becker et al. [ESA 2023]. Our running time is a factor $n_{A}^2/\sigma$ faster than the state of the art, where $\sigma$ is the size of the alphabet.
Furthermore, for $\sigma=O(1)$ we present the first linear time algorithm for this problem. We show that our bound is tight for sorted inputs with any combination of $n$ and $\sigma$, by providing a family of inputs for which our output $B$ is minimum and has a maximum size of $\Theta(n\sigma)$.
Blogger's Review: This paper presents a significant improvement in the time complexity of the Wheeler determinization problem, especially when the Wheeler order is given, showcasing the potential for algorithm optimization. The introduction of a linear time algorithm opens new avenues for addressing such problems, warranting further exploration of its performance in practical applications.