Tighter Bounds for Wheeler Determinization

Abstract

Given a Wheeler NFA $\mathcal{A}$, the Wheeler determinization problem is to construct a Wheeler DFA $\mathcal{D}$ that accepts the same language as $\mathcal{A}$. We use the notation $n_{\mathcal{A}},m_{\mathcal{A}}$ for the number of vertices and edges of $\mathcal{A}$, and equivalently $n_{\mathcal{D}},m_{\mathcal{D}}$ for $\mathcal{D}$. Alanko et al. [SODA 2020, Inf. Comp. 2021] solve this problem in $O(n_{\mathcal{A}}^3)$ time, by constructing a $mathcalD$ that always satisfies $n_{\mathcal{D}}\le 2n_{\mathcal{A}}-1$. In this paper, we show how to improve the running time to $O(n_{\mathcal{A}}+m_{\mathcal{A}}+n_{\mathcal{D}}+m_{\mathcal{D}})$ when the Wheeler order of $\mathcal{A}$ is given. If the Wheeler order is not present, we achieve $O(n_{\mathcal{A}}+m_{\mathcal{A}}\log n_{\mathcal{A}}+n_{\mathcal{D}}+m_{\mathcal{D}})$ time by using an algorithm of Becker et al. [ESA 2023]). Our running time is a factor $n_{\mathcal{A}}^2/\sigma$ faster than the state of the art for sorted inputs, where $\sigma$ is the size of the alphabet. Furthermore, for $\sigma =O(1)$ we have the first linear time algorithm for this problem. We show that our bound is tight with any combination of $n_{\mathcal{A}}$ and $\sigma$, by giving a family of inputs for which our output $\mathcal{D}$ is minimum, and of maximum size $\Theta (n_{\mathcal{A}}\sigma )$.

6 pages main body, 1 figure