Aggregation-based minimization of finite state automata (Q2035006)

The contribution investigates bisimulation minimization for nondeterministic finite-state automata (NFA) using a partition aggregation algorithm instead of the classical partition refinement algorithms. Minimization of NFA is a well-known difficult problem that is even hard to approximate (unless \(\mathrm{P} = \mathrm{PSpace}\)). Consequently, alternative efficient algorithms that reduce the size of NFA have been investigated. Bisimulation minimization algorithms utilize bisimulations, which are equivalence relations that respect the transitions (i.e., if one of two equivalent states permits an \(a\)-transition to another state \(q\), then the equivalent state has an \(a\)-transition to a state that is equivalent to \(q\)). Additionally, the equivalence needs to respect the distinction into final and nonfinal states. The standard algorithms to compute the coarsest bisimulation of a given NFA use partition refinement in the sense that they initially split the set of states into final and nonfinal states and then split equivalence classes if the transitions are not respected. The current contribution computes the same bisimulation using a partition aggregation approach, so it starts with each state in its own equivalence class and then merges equivalence classes if that is possible. The contribution claims that the benefit of the aggregation approach, despite of being asymptotocally slower than the refinement algorithms, is that the intermediate equivalences computed on the way to the coarsest bismulation can be used to reduce the input NFA as well and will always preserve the recognized language. This is due to the fact that states that are placed in the same equivalence class in the aggregation approach are guaranteed to be bisimilar, whereas this is not the case for the refinement approach since the initial partition for the refinement approach is potentially too aggressive. The logical characterization of the equivalence classes that can be merged might lead itself to optimizations from the area of computing maximal models. Finally, a detailed complexity analysis is provided together with an overall fair comparison to the existing algorithms that solve the same problem. Overall, the contribution is very well written and should be understandable by anyone with some background in basic automata theory. Examples and intuition are generously provided. The comparisons are fair and a lot of related research is addressed.