Extensional characterization of non-deterministic finite state transductions I recently became aware of the rather appealing characterization of deterministic word-to-word transductions as word functions with bounded variation (see e.g. [1]). This coincides with the set of functions that can be realized by subsequential transducers, which are deterministic finite state transducers with an output function defined on accepting states.

Not every function defined by a non-deterministic FST is subsequential, that is, even if the FST is single-valued, it might not be determinizable. I wondered if there are any extensional characterizations of the set of functions definable by (single-valued) FSTs?

Thanks!

[1] Bruyère, Véronique and Reutenauer, Christophe.  A proof of choffrut's theorem on subsequential functions. Theoretical Computer Science, 1999.
The best reference is probably the book Rational transductions and context-free languages by J. Berstel.

First recall that a function $f$ from $A^*$ to $B^*$ is realized by a transducer (= non-deterministic FST) if and only if it is rational, that is, if the set $\{(u, f(u)) \mid u \in A^* \}$ is a rational subset of $A^* \times B^*$.

You can find several other relevant characterizations of rational functions in Chapter 4 of Berstel's book.


(Eilenberg 1974. See Prop. 4.1 and Corollary 4.3) A function from $A^*$ to $B^*$ is rational if and only if it can be realized by a normalized unambiguous transducer.
(Schützenberger 1976. See theorem 4.5) A function is rational if and only if it admits a semimonomial representation.
(Elgot and Mezei 1965. See Theorem 5.2) A function is rational if and only if it is the composition of a left sequential transduction by a right sequential transducer.


See also A. Arnold and M. Latteux, A new proof of two theorems about rational transductions, Theoret. Comput. Sci. 2 (1979), 261–263.