Model reduction of finite state machines by contraction

This note discusses an approach to the model reduction of discrete event systems represented by finite-state machines. A set of good reduced-order approximations of a deterministic finite-state machine M can be efficiently computed by looking at its contractions, i.e., finite-state machines constructed from M by merging two states. In some particular case, it is also possible to prove that the approximations thus constructed are infimal, in the sense that there do not exist better approximations with the same number of states. This note also defines a merit function to choose, among a set of approximations, the best one with respect to a given observed behavior.