Repository navigation
Description
Severity: Critical · Effort: Medium (the default switch alone is Small once #734 lands) · Expected effect: removes exponential blow-up on DFA input; >1,000,000× on a measured 50-state probe; 2–20× target on ordinary deterministic minimization
Scope: the minimize() dispatcher, minimize_brzozowski, minimize_hopcroft, the "brzozowski" defaults in nfa.hh, plumbing.hh and the Python wrapper, and determinize() with its macrostate_discover callback.
Already filed
- minimize() with algorithm "hopcroft" returns a wrong language on NFAs and a non-minimal DFA on untrimmed input #734: in the explicit
"hopcroft"branch, determinize when!is_deterministic(), trim, then run Hopcroft; replace the determinism assertion inminimize_hopcroft()with a check that throws; document both algorithms and their preconditions innfa.hhand the Python docstring; remove the unusedNfa result;.
This issue is only about the rest: which algorithm runs when the caller does not choose one, bounding the subset construction, and checking minimality in tests.
Problem
The default is {"algorithm", "brzozowski"} in nfa.hh#L987, plumbing.hh#L47 and nfa.pyx#L1282. minimize_brzozowski is determinize(revert(determinize(revert(aut)))) for every input, including an automaton that is already a trimmed DFA. The reverse of an accessible DFA is an NFA, and determinizing it yields the minimal DFA of the reversed language, which can be exponentially larger than the input. minimize_hopcroft (Valmari and Lehtinen, partial transition functions) runs in O(a·n·log n) on the same DFA, as algorithms.hh documents.
A local Release probe (GCC 15.2, -O3 -DNDEBUG, commit bb63f4e) used a reachable, co-accessible, complete 50-state DFA over four symbols. Hopcroft took 0.017–0.027 ms (about 0.018 ms). Brzozowski did not finish within 30 s, and a run capped at 5 s had reached 1.95 GB RSS. minimize_brzozowski, minimize_hopcroft and determinize are unchanged on devel. The probe is adversarial, but it shows a strategy error, and a better constant factor would not fix it.
After #734, the "hopcroft" branch is already the pipeline an automatic choice needs: determinize if the input is not a DFA, trim, Hopcroft. Callers still get Brzozowski unless they know to ask for it.
Nothing bounds the subset construction either. determinize() accepts a macrostate_discover callback that can stop discovery, but it then returns "the determinized NFA constructed so far" with no sign that it is partial. minimize_brzozowski passes no callback, so a blow-up runs until memory runs out.
is_deterministic() (operations.cc#L479-L490) is one O(n + number of symbol posts) scan: one initial state and exactly one target per symbol post. Like determinize() and both minimizations, it treats EPSILON as an ordinary symbol.
Proposed change
"auto"as the default. Add"auto"tominimize()and make it the default innfa.hh,plumbing.hhandnfa.pyx. It callsis_deterministic()once:- DFA: trim, then Hopcroft. Hopcroft supports partial transition functions, so do not complete the DFA first.
- otherwise: determinize once, trim, then Hopcroft.
Keep"brzozowski"and"hopcroft"with the meaning minimize() with algorithm "hopcroft" returns a wrong language on NFAs and a non-minimal DFA on untrimmed input #734 gives them.complement(…, {"algorithm", "brzozowski"})keeps callingminimize_brzozowskidirectly.
- Empty language. After trimming, an empty language gives 0 states, where Brzozowski returns 1 state (minimize() with algorithm "hopcroft" returns a wrong language on NFAs and a non-minimal DFA on untrimmed input #734). Choose one result for
"auto"and document it, for example one non-final initial state with no transitions. - Subset budget. Accept optional
"max_states"and"max_transitions"keys in theParameterMapofminimize()(and in the internal determinization it calls). Count discovered macrostates and emitted transitions, stop when a limit is exceeded, and throw a dedicated exception type (or return an error through an internalexpected-style result). Never return the partial automaton. A first version can count through the existingmacrostate_discovercallback. A later one can check between symbols as well. - Strategy record for benchmarks. Have the internal implementation return which path ran, input and output sizes, and the number of discovered subsets, so the benchmark harness can print them. The public
minimize()signature stays. - Brzozowski only with evidence. Auto never picks Brzozowski unless a benchmark family shows it winning. Dense random NFAs are the usual candidate (
builder::create_random_nfa_tabakov_vardigenerates them). If one does win, add a conservative pre-scan rule for that family and test it. - Minimality oracle. Add a table-filling distinguishability check for small DFAs to the tests. Language equivalence alone does not prove that a result is minimal.
Explanation and worked example
Two very different algorithms. Brzozowski minimizes by reverse, determinize, reverse, determinize. It handles NFAs directly, but either determinization can create exponentially many subsets. Hopcroft refines a partition of an already deterministic automaton in O(a·n·log n). Sending a DFA through two subset constructions wastes work that Hopcroft never does.
Worked example. Let L = (a|b)ⁿ a (a|b)*: the (n+1)-th letter is a. Its partial DFA has n + 2 states: states 0…n count letters, n -a-> n+1, and state n+1 loops on both letters. The reverse language (a|b)* a (a|b)ⁿ needs 2ⁿ⁺¹ DFA states. Checked on devel: for n = 16, determinize(revert(dfa)) produces 131,072 states from the 18-state input before the second pass brings it back to 18. minimize_hopcroft works on the 18 states only.
| Input | Auto strategy | Preparation |
|---|---|---|
| DFA (one initial state, one target per symbol post) | Hopcroft | Trim; do not complete |
| Partial DFA | Hopcroft on the partial transition function | Do not add a sink |
| NFA | Determinize once, trim, Hopcroft | Subset budget |
Explicit "brzozowski" |
Brzozowski | Honour the choice; budget if given |
Why not always run Hopcroft directly. Hopcroft's refinement assumes one successor per symbol, so an NFA must be determinized first. Completing a DFA before Hopcroft is not needed either: the partial-function version handles missing transitions, and a sink state only adds work.
Budgets. Subset construction can legitimately explode. A budget turns an out-of-memory kill into an error the caller can handle, for example by falling back to reduce(). Because the callback-based stop returns a partial automaton, the budget layer must remember that it stopped and must not hand that automaton back.
Why a separate minimality check. Two DFAs can accept the same language and differ in size. For small DFAs, table filling marks every distinguishable pair; the result is minimal if and only if no two of its states are equivalent.
Step-by-step execution plan
Read first: minimize(), minimize_brzozowski, minimize_hopcroft and its RefinablePartition helper in src/nfa/operations.cc, is_deterministic(), trim(), determinize() with its callback, the minimization tests in tests/nfa/nfa.cc, and #734. Keep the explicit strategy names and change only the default.
- Add regression fixtures with timeouts: the (a|b)ⁿ a (a|b)* family above, a complete random DFA, a partial DFA, empty and universal languages, unreachable and dead states, several initial states, ε used as a letter, and small NFAs where Brzozowski is competitive. Record states, transitions, time and RSS for both algorithms.
- Implement
"auto"on top of minimize() with algorithm "hopcroft" returns a wrong language on NFAs and a non-minimal DFA on untrimmed input #734's branch: oneis_deterministic()scan, then trim and Hopcroft, or determinize once, trim and Hopcroft. Switch the default in C++,plumbing.hhand Python, and update the docs. - Settle the empty-language result and add a test for it.
- Add the
"max_states"/"max_transitions"keys. Implement counting throughmacrostate_discoverfirst, throw a dedicated exception, and test that no partial automaton escapes, including from Python. - Return the strategy record from the internal implementation and print it from the benchmark harness.
- Add the table-filling oracle for DFAs up to a few dozen states. Use it together with
are_equivalentin randomized tests of"auto","hopcroft"and"brzozowski"on NFAs fromcreate_random_nfa_tabakov_vardi(Add seeded randomized differential tests for the NFA and NFT algorithms #770). - Benchmark classification, determinization, trimming and Hopcroft separately, with peak subsets, output size, RSS and timeout count. Run
tests-integrationand Z3-Noodler workloads that callminimize(). Consider a Brzozowski niche only if a family shows it winning.
Dependencies and hand-off: #734 lands first. Certified DFA fast paths (#801) and Delta metadata (#805) can later replace the is_deterministic() scan with a cached certificate. Trim with a reverse index (#786), the revert rewrite in #751, determinization in #738 and macrostate interning (#783) make the individual steps faster. None of them is needed for the dispatch itself.
Definition of done: the default never sends a DFA through Brzozowski, partial DFAs are minimized without completion, budgets stop explosion with an error and no partial result, small outputs pass the minimality oracle, the explicit strategies behave as documented, and the adversarial probe finishes in bounded memory.
Expected result and validation
Target 2–20× on ordinary deterministic minimization, and removal of the exponential cases for DFA input. The measured adversarial case is over 1,000,000× at the 30-second lower bound. Validate language equivalence and minimality (oracle) on partial DFAs, empty languages, unreachable states, several initial states and sparse symbols. The acceptance set must contain both cases where Brzozowski is competitive and cases that trigger subset explosion. Record timeout count and peak RSS next to median times.
Related: #496 (closed; Hopcroft and Brzozowski produced different automata because the input was not a trimmed DFA), #770 (randomized differential tests).
Activity
nfa: +fix Choose the minimization algorithm from the input
nfa: +fix Choose the minimization algorithm from the input
nfa: +fix Choose the minimization algorithm from the input
nfa: +fix Choose the minimization algorithm from the input (#909)