{"ID":5551629,"CreatedAt":"2026-07-02T01:54:51.863792489Z","UpdatedAt":"2026-07-04T14:41:19.486384794Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.01007","arxiv_id":"2607.01007","title":"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] show that we can solve this problem in $O(n_{\\mathcal{A}}^3)$ time. 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 given the Wheeler order of $\\mathcal{A}$ (which can be computed in $O(m_{\\mathcal{A}}\\log n_{\\mathcal{A}})$ with an algorithm by Becker et al. [ESA 2023]). Our running time is a factor $n_{\\mathcal{A}}^2/σ$ faster than the state of the art, where $σ$ is the size of the alphabet. Furthermore, for $σ=O(1)$ we have the first linear time algorithm for this problem. We show that our bound is tight for sorted inputs with any combination of $n$ and $σ$, by giving a family of inputs for which our output $\\mathcal{D}$ is minimum, and of maximum size $Θ(nσ)$.","short_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...","url_abs":"https://arxiv.org/abs/2607.01007","url_pdf":"https://arxiv.org/pdf/2607.01007v1","authors":"[\"Philip Bille\",\"Inge Li Gørtz\",\"Máximo Pérez-López\",\"Simon R. Tarnow\"]","published":"2026-07-01T14:45:29Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}