pith. sign in

arxiv: 2607.01007 · v1 · pith:FDLBJDZ7new · submitted 2026-07-01 · 💻 cs.DS

Tighter Bounds for Wheeler Determinization

Philip Bille , Inge Li G{\o}rtz , M\'aximo P\'erez-L\'opez , Simon R. Tarnow This is my paper

Pith reviewed 2026-07-02 04:13 UTC · model grok-4.3

classification 💻 cs.DS
keywords Wheeler automatadeterminizationNFA to DFA conversionlinear-time algorithmstight complexity boundsautomata theorydata structures
0
0 comments X

The pith

Wheeler determinization runs in time linear in the sizes of input NFA and output DFA when the Wheeler order is given.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper gives an algorithm that builds the equivalent Wheeler DFA from a Wheeler NFA in O(n_A + m_A + n_D + m_D) time once the Wheeler order on the NFA states is supplied. This replaces an earlier cubic-time method and improves the bound by a factor of n_A squared over sigma. The new running time is shown to be tight by exhibiting a family of inputs where the produced DFA reaches its maximum possible size of Theta(n sigma) for any n and sigma.

Core claim

Given a Wheeler NFA A together with its Wheeler order, the equivalent Wheeler DFA D can be constructed in O(n_A + m_A + n_D + m_D) time, and there exist families of inputs for which this output size is Theta(n sigma) and therefore the bound is tight.

What carries the argument

A single forward pass over the states of A in the supplied Wheeler order that merges equivalent transitions to produce each state of D exactly once.

If this is right

  • For constant alphabet size the problem admits a linear-time solution.
  • The output DFA size is bounded by Theta(n sigma) on the worst-case inputs constructed in the paper.
  • The algorithm improves the prior O(n_A^3) bound by a factor of n_A^2 over sigma.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Integrating an efficient Wheeler-order computation directly into the determinization pass may remove the separate O(m_A log n_A) preprocessing step.
  • The same linear-time traversal technique could apply to other ordered automata problems that rely on a total order on states.
  • Compressed string indexes built from Wheeler automata would inherit the improved construction time.

Load-bearing premise

The Wheeler order on the states of the input NFA is supplied as part of the input.

What would settle it

A Wheeler NFA with its Wheeler order for which any correct algorithm that outputs D must examine more than a constant number of edges or states beyond the total size n_A + m_A + n_D + m_D.

Figures

Figures reproduced from arXiv: 2607.01007 by Inge Li G{\o}rtz, M\'aximo P\'erez-L\'opez, Philip Bille, Simon R. Tarnow.

Figure 2
Figure 2. Figure 2: Its Wheeler determinization D Acknowledgments. This work was also supported by Independent Research Fund Denmark grants 10.46540/3105-00302B and 10.46540/4283-00129B. The third author also thanks Jarno N. Alanko for his introduction to the topic of this paper [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
read the original 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/\sigma$ faster than the state of the art, 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 for sorted inputs with any combination of $n$ and $\sigma$, by giving a family of inputs for which our output $\mathcal{D}$ is minimum, and of maximum size $\Theta(n\sigma)$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 1 minor

Summary. The paper claims an improved algorithm for Wheeler determinization: given a Wheeler NFA A with n_A states and m_A edges and its Wheeler order, construct the equivalent Wheeler DFA D in O(n_A + m_A + n_D + m_D) time (improving on the prior O(n_A^3) bound by a factor of n_A^2/sigma), with the order computable separately in O(m_A log n_A) time. It further shows tightness by exhibiting an explicit family of sorted inputs for which the minimum D has size Theta(n sigma) for arbitrary n and sigma.

Significance. If the claimed bounds hold, the result is significant: it yields the first linear-time algorithm for constant sigma and a near-linear (in input+output size) algorithm in general, with an explicit matching lower-bound family that demonstrates optimality across all parameter regimes. The separation of order computation from the main construction is stated explicitly and does not affect the central bound.

minor comments (1)
  1. The abstract states the O(m_A log n_A) order computation result but does not cite the specific Becker et al. reference in the provided text; adding the full citation in the introduction would improve traceability.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The claimed O(n_A + m_A + n_D + m_D) bound follows from direct counting of operations in an explicit construction of the determinized DFA (given the order as input). The matching lower bound is witnessed by a separate, explicitly constructed family of inputs that forces |D| = Theta(n sigma). No equation or step reduces by definition to its own output, no parameter is fitted and then renamed as a prediction, and all cited prior results (Alanko et al., Becker et al.) are by disjoint authors and concern independent subroutines. The derivation is therefore self-contained against external size measures.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The algorithm rests on standard graph-processing primitives and the domain assumption that a total Wheeler order is supplied; no numeric parameters are fitted and no new entities are postulated.

axioms (2)
  • standard math Standard graph traversal and adjacency-list scanning can be performed in linear time
    The claimed linear bound presupposes that each edge and state is examined a constant number of times.
  • domain assumption The supplied Wheeler order is consistent with the transition relation of the NFA
    The algorithm description relies on the order being a valid Wheeler order.

pith-pipeline@v0.9.1-grok · 5820 in / 1274 out tokens · 37548 ms · 2026-07-02T04:13:48.632336+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

22 extracted references

  1. [1]

    Alanko, J., Cenzato, D., Cotumaccio, N., Kim, S.H., Manzini, G., Prezza, N.: Computing the LCP Array of a Labeled Graph (2024)

    2024

  2. [2]

    In: 2022 Data Compression Conference (DCC)

    Alanko, J., Cotumaccio, N., Prezza, N.: Linear-time minimization of wheeler DFAs. In: 2022 Data Compression Conference (DCC). pp. 53–62

    2022

  3. [3]

    In: Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms

    Alanko, J., D’Agostino, G., Policriti, A., Prezza, N.: Regular languages meet prefix sorting. In: Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 911–930 (2020)

    2020

  4. [4]

    Informa- tion and Computation281, 104820 (2021)

    Alanko, J., D’Agostino, G., Policriti, A., Prezza, N.: Wheeler languages. Informa- tion and Computation281, 104820 (2021)

    2021

  5. [5]

    In: 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)

    Alanko, J.N., Pérez-López, M.: Computing k-mers in Graphs. In: 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026). vol. 369, pp. 3:1– 3:17 (2026)

    2026

  6. [6]

    In: 31st Annual European Symposium on Algorithms (ESA 2023)

    Becker, R., Cáceres, M., Cenzato, D., Kim, S.H., Kodric, B., Olivares, F., Prezza, N.: Sorting Finite Automata via Partition Refinement. In: 31st Annual European Symposium on Algorithms (ESA 2023). vol. 274, pp. 15:1–15:15 (2023)

    2023

  7. [7]

    In: LATIN 2000: Theoretical Informatics

    Bender, M.A., Farach-Colton, M.: The LCA Problem Revisited. In: LATIN 2000: Theoretical Informatics. pp. 88–94 (2000)

    2000

  8. [8]

    Clark, D.R.: Compact PAT trees. Ph.D. thesis (1996)

    1996

  9. [9]

    In: 2023 Data Compression Confer- ence (DCC)

    Conte, A., Cotumaccio, N., Gagie, T., Manzini, G., Prezza, N., Sciortino, M.: Com- puting matching statistics on Wheeler DFAs. In: 2023 Data Compression Confer- ence (DCC). pp. 150–159 (2023)

    2023

  10. [10]

    In: 34th Interna- tional Symposium on Algorithms and Computation (ISAAC 2023)

    Cotumaccio, N.: Prefix Sorting DFAs: A Recursive Algorithm. In: 34th Interna- tional Symposium on Algorithms and Computation (ISAAC 2023). vol. 283, pp. 22:1–22:15 (2023)

    2023

  11. [11]

    In: Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms

    Cotumaccio, N., Prezza, N.: On indexing and compressing finite automata. In: Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 2585–2599 (2021)

    2021

  12. [12]

    Theoretical Com- puter Science975, 114128 (2023)

    Equi, M., Mäkinen, V., Tomescu, A.I.: Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails. Theoretical Com- puter Science975, 114128 (2023)

    2023

  13. [13]

    In: LATIN 2010: Theoretical Informatics

    Fischer, J.: Optimal Succinctness for Range Minimum Queries. In: LATIN 2010: Theoretical Informatics. pp. 158–169 (2010)

    2010

  14. [14]

    Theoretical Computer Science698, 67–78 (2017)

    Gagie, T., Manzini, G., Sirén, J.: Wheeler graphs: A framework for BWT-based data structures. Theoretical Computer Science698, 67–78 (2017)

    2017

  15. [15]

    Nature Biotechnology36(9), 875–879 (2018)

    Garrison, E., Sirén, J., Novak, A.M., Hickey, G., Eizenga, J.M., Dawson, E.T., Jones,W.,Garg,S.,Markello,C.,Lin,M.F.,Paten,B.,Durbin,R.:Variationgraph toolkit improves read mapping by representing genetic variation in the reference. Nature Biotechnology36(9), 875–879 (2018)

    2018

  16. [16]

    Algorithmica84(3), 784–814 (2022)

    Gibney, D., Thankachan, S.V.: On the Complexity of Recognizing Wheeler Graphs. Algorithmica84(3), 784–814 (2022)

    2022

  17. [17]

    Acm Sigact News32(1), 60–65 (2001)

    Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to automata theory, lan- guages, and computation. Acm Sigact News32(1), 60–65 (2001)

    2001

  18. [18]

    Jacobson, G.J.: Succinct static data structures. Ph.D. thesis (1988)

    1988

  19. [19]

    In: 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)

    Kim, S.H., Olivares, F., Prezza, N.: Faster Prefix-Sorting Algorithms for Deter- ministic Finite Automata. In: 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). vol. 259, pp. 16:1–16:16 (2023)

    2023

  20. [20]

    Bioinfor- matics33(20), 3181–3187 (2017) 8 P

    Muggli, M.D., Bowe, A., Noyes, N.R., Morley, P.S., Belk, K.E., Raymond, R., Gagie, T., Puglisi, S.J., Boucher, C.: Succinct colored de Bruijn graphs. Bioinfor- matics33(20), 3181–3187 (2017) 8 P. Bille, I. L. Gørtz, M. Pérez-López, S. R. Tarnow

    2017

  21. [21]

    In: Pro- ceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms

    Muthukrishnan, S.: Efficient algorithms for document retrieval problems. In: Pro- ceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms. pp. 657–666 (2002)

    2002

  22. [22]

    Microbial Genomics7(11), 000691 (2021) A Colored Range Queries We review thecolored rangedata structure of Muthukrishnan [21]

    Mäklin, T., Kallonen, T., Alanko, J., Samuelsen, Ø., Hegstad, K., Mäkinen, V., Corander, J., Heinz, E., Honkela, A.: Bacterial genomic epidemiology with mixed samples. Microbial Genomics7(11), 000691 (2021) A Colored Range Queries We review thecolored rangedata structure of Muthukrishnan [21]. Given an arrayA[1, n]of elements from a universe of sizeu=O(n)...

    2021