{"id":"09b77696-45b2-4d7d-8414-ab42e0e00d28","arxiv_id":"2607.01007","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"An O(n_A + m_A + n_D + m_D) algorithm for Wheeler determinization given the order, shown tight via a family of minimum-size maximum-output instances for any n and sigma.","lead":"This paper gives an algorithm that turns a Wheeler NFA into an equivalent Wheeler DFA in time linear in the combined size of the input and output automata, provided the Wheeler order on states is already known. The result improves on a prior cubic-time method and includes a matching lower-bound construction that holds for any alphabet size.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.3","headline":"No significant objection identified","rationale":"The reader's weakest assumption matches the paper's explicit framing of the result as conditional on the Wheeler order. The tightness construction and claimed improvement over the prior O(n_A^3) bound are internally coherent; no adjustment to the CONDITIONAL verdict is required.","tokens_in":1804,"tokens_out":256,"duration_ms":27707,"concrete_test":"Re-derive the running-time summation in the main algorithm section by enumerating every operation performed on each state and edge of A and each generated state and edge of D; confirm the total is strictly linear in n_A + m_A + n_D + m_D with no additional factors.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim—an O(n_A + m_A + n_D + m_D)-time algorithm for Wheeler determinization given the order, with tightness via an explicit family of inputs producing a minimum D of size Theta(n sigma) for arbitrary n and sigma—contains no detectable internal inconsistency, unsubstantiated step, or hidden superlinear cost once the order is supplied. The separation of order computation (O(m_A log n_A)) is stated explicitly and does not affect the main bound.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","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.","tokens_in":1893,"tokens_out":291,"duration_ms":18159,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":null}],"recommendation":"accept","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"grok-4.3","letter":"The paper improves Wheeler determinization to O(nA + mA + nD + mD) time once the Wheeler order is supplied, beating the prior cubic bound, and backs it with a family of inputs that force an output DFA of size Theta(n sigma) while remaining minimal. The lower-bound construction works for arbitrary n and sigma and does not rely on the algorithm itself.\n\nThe algorithmic part counts the work in a direct construction, which keeps the bound clean. For constant sigma this yields the first linear-time result. The separation of order computation (O(mA log nA)) is stated up front, so the main claim stays internally consistent.\n\nThe main limitation is that the linear bound assumes the order is already known; without it the log factor appears. The tightness argument is explicit rather than asymptotic only, which strengthens the result.\n\nThis is useful for people building string indexes or compressed automata where Wheeler NFAs appear. A reader focused on automata construction would find the improved bound and the matching construction worth checking.\n\nSend it to peer review. The claims are specific, the improvement is measurable, and the lower bound is separate from the algorithm.","headline":"Paper gives O(nA + mA + nD + mD) Wheeler determinization given the order, with explicit tightness for any n and sigma.","tokens_in":2385,"tokens_out":313,"would_cite":false,"duration_ms":18088,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"Wheeler determinization runs in time linear in the sizes of input NFA and output DFA when the Wheeler order is given.","keywords":["Wheeler automata","determinization","NFA to DFA conversion","linear-time algorithms","tight complexity bounds","automata theory","data structures"],"falsifier":"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.","tokens_in":2720,"feed_emoji":"","tokens_out":593,"duration_ms":36856,"temperature":0.7,"pith_summary":"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.","feed_headline":"Wheeler determinization in linear time with given order","feed_subtitle":"New algorithm runs in O(n_A + m_A + n_D + m_D) and is tight at Theta(n sigma) output size for any n and sigma","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":[],"cache_read_input_tokens":64,"weakest_assumption_plain":"The Wheeler order on the states of the input NFA is supplied as part of the input.","fun_headline_variants_meta":{"error":"xAI API error (429): The model is currently at capacity due to high demand. Please try again in a few minutes, or use a higher service tier for priority processing: https://docs.x.ai/developers/advanced-api-usage/priority-processing"},"cache_creation_input_tokens":0},"created_at":"2026-07-02T04:13:48.632336+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"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.","supporting_citations":[],"review_version":1}