Minimization of Rational Word Functions
Christophe Reutenauer, Marcel-Paul Schützenberger · SIAM Journal on Computing · 1991
Rational functions from a free monoid into another are characterized by the finiteness of the index of some congruence naturally associated with the function. A sequential bimachine is constructed computing the function, which is completely canonical, and in some sense minimal. This generalizes the Nerode criterion and the minimal automaton of a rational language, and similar results for sequential functions.