# 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 – Denis Dec 22 '14 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. – Ulrik Rasmussen Jan 5 '15 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.