A categorical interpretation of state merging algorithms for DFA inference
Juan Miguel Vilar · Pattern Recognition · 2024
We use Category Theory to interpret the family of algorithms for inference of DFAs that work by merging states. This interpretation allows us to characterize the structure of the search space and to define criteria for the convergence of these algorithms to the correct DFA. We also prove that the well-known EDSM algorithm does not identify DFAs in the limit.