SIAM Journal on Computing · 1991 · 42 citations · 4 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsDiscrete MathematicsFinite AutomataRecursion TheoryAutomata MinimizationMonoid TheoryMonoidsRational Function ComputationRational Languages
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.
4
Transductions and Context-Free Languages
Jean Berstel · 1979 · 1.3K citations
A remark on finite transducers
M. P. Schützenberger · Information and Control · 1961 · 65 citations
Properties of Finite and Pushdown Transducers
Christian Choffrut, Karel Čulík · SIAM Journal on Computing · 1983 · 26 citations