8000 `minimize()`: make an input-aware `"auto"` strategy the default instead of Brzozowski · Issue #800 · VeriFIT/mata · GitHub
[go: up one dir, main page]

Skip to content

minimize(): make an input-aware "auto" strategy the default instead of Brzozowski #800

Open

Description

@koniksedy

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

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

  1. "auto" as the default. Add "auto" to minimize() and make it the default in nfa.hh, plumbing.hh and nfa.pyx. It calls is_deterministic() once:
  2. 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.
  3. Subset budget. Accept optional "max_states" and "max_transitions" keys in the ParameterMap of minimize() (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 internal expected-style result). Never return the partial automaton. A first version can count through the existing macrostate_discover callback. A later one can check between symbols as well.
  4. 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.
  5. 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_vardi generates them). If one does win, add a conservative pre-scan rule for that family and test it.
  6. 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.

  1. 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.
  2. 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: one is_deterministic() scan, then trim and Hopcroft, or determinize once, trim and Hopcroft. Switch the default in C++, plumbing.hh and Python, and update the docs.
  3. Settle the empty-language result and add a test for it.
  4. Add the "max_states"/"max_transitions" keys. Implement counting through macrostate_discover first, throw a dedicated exception, and test that no partial automaton escapes, including from Python.
  5. Return the strategy record from the internal implementation and print it from the benchmark harness.
  6. Add the table-filling oracle for DFAs up to a few dozen states. Use it together with are_equivalent in randomized tests of "auto", "hopcroft" and "brzozowski" on NFAs from create_random_nfa_tabakov_vardi (Add seeded randomized differential tests for the NFA and NFT algorithms #770).
  7. Benchmark classification, determinization, trimming and Hopcroft separately, with peak subsets, output size, RSS and timeout count. Run tests-integration and Z3-Noodler workloads that call minimize(). 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).

Metadata

Metadata

Assignees

No one assigned

    Labels

    For:libraryThe issue is related to library (c++ implementation)Module:nfaThe issue is related to Nondeterministic Finite Automatatype:optimizationThis issue is related to a possible optimization of an algorithm, improving the performance of Mata.

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions

      0