Pith. sign in

REVIEW 1 minor 22 references

Tighter Bounds for Wheeler Determinization

T0 review · 0 major / 1 minor · reviewed 2026-07-02 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Wheeler determinization runs in time linear in the sizes of input NFA and output DFA when the Wheeler order is given.

desk verdict Paper gives O(nA + mA + nD + mD) Wheeler determinization given the order, with explicit tightness for any n and sigma. read the letter →

arxiv 2607.01007 v1 pith:FDLBJDZ7 submitted 2026-07-01 cs.DS

Philip Bille , Inge Li G{o}rtz , Máximo Pérez-López , Simon R. Tarnow This is my paper · ORCID
classification cs.DS
keywords WheelerautomatadeterminizationNFAtoDFAconversionlinear-timealgorithmstightcomplexityboundstheorydatastructures
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

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.

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.

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.

Watch

Extended reading notes

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.

Load-bearing premise

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

Editorial extensions

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.

Reading between the lines

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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

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 · score 0.0 of 10

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.

Assumptions & free parameters 0 free parameters · 2 assumptions · 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.

assumptions (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.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Tighter Bounds for Wheeler Determinization." pith.science (2026). https://pith.science/paper/FDLBJDZ7

@misc{pith2026260701007,
  author       = {Pith},
  title        = {Pith review of: Tighter Bounds for Wheeler Determinization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FDLBJDZ7}},
  note         = {Machine review of arXiv:2607.01007}
}
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)$.

Figures

Figures reproduced from arXiv: 2607.01007 by the authors.

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 ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages

  1. [1]

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

    work page 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

    work page 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)

    work page 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)

    work page 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)

    work page 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)

    work page 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)

    work page 2000

  8. [8]

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

    work page 1996

Show all 22 references
  1. [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

  2. [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

  3. [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

  4. [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

  5. [13]

    In: LATIN 2010: Theoretical Informatics

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

    2010

  6. [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

  7. [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

  8. [16]

    Algorithmica84(3), 784–814 (2022)

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

    2022

  9. [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

  10. [18]

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

    1988

  11. [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

  12. [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

  13. [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

  14. [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 Mu...

    2021

Pith tools

Reviewed July 2, 2026 · model on record in the stance chip above.