# 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.

• Not directly related to the class of transductions in the question, but you might be interested in the recent paper of Bojanczyk on characterizations of rational transductions: Transducers with Origin Information Commented Dec 22, 2014 at 23:33
• Thank you, this looks very useful! Incidentally, I am currently working on characterizing non-deterministic FST transductions as a restricted type of the streaming transducer used by Bojanczyk. Hopefully, this might point in the direction of a machine-independent characterization. Commented Jan 5, 2015 at 14:16

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^*$.
1. (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.