PaigeTarjanMinimization.minimizeDFA does not guarantee minimal result

[learnlib]

PaigeTarjanMinimization.minimizeDFA does not guarantee minimal result

[mtf90]

Dear @wytseoortwijn,
I think, this is more of a discussion between partial and total automata. For prefix-closed languages (your automaton accepts the prefix-closed language {epsilon}), the minimal, total automaton representation will always have a sink state that collects all rejected words. Technically, this representation can be further minimized by removing the sink state and relying on the semantics of undefined transitions (which usually reject words).

Your use-case is especially mean, because you have a partial automaton with two equivalent sink states s1 and s2. Unfortunately, AutomataLib has several places where the main algorithm is implemented for generic universal automata only which do not support special semantics such as "undefined transition" = "rejection". For generic automata, states/successors are often characterized structurally, e.g., via their state properties and transition properties of outgoing transitions, and differ from undefined successors. So this is not really an issue with the PaigeTarjan implementation but with the way the automaton structure is interpreted.

We are aware of this issue but haven't found a solution yet that doesn't require re-writing a lot of stuff.

For now, if you run into any issues with this, I would suggest you first decide which canonical representation you want (total vs. partial) and then either complete the automata beforehand (see, e.g. MutableDFAs) or remove any dead-ends afterwards (see, e.g., ShrinkableAutomaton#removeState).