Minimization
Now that we have coalgebra printing, we can turn to actual minimization. Given an Encoding
and a Partition
, the following steps should be taken:
-
Merging States, simply by walking through the encoding and replacing source and target states in all edges with the block number of the respective state. The symbol table has to be treated similarly, but requires some creativity for the names of merged states. -
Bundling Edges, by grouping the edges by (source, target). I.e edges with the same source and target state should end up in the same bucket. -
Merging Edges. This requires the introduction of a "Minimization Interface" akin to the refinement interface with a single function merge :: [Label f] -> [Label f]
. The implementation ofmerge
for all functors is mostly straightforward and given here.merge
should be called for each of the "edge bundles" of the previous step with more then one edge. -
Building an Encoding by flattening the list of edge bundles.
Edited by Hans-Peter Deifel