<p>The best reference is probably the book <a href="http://www-igm.univ-mlv.fr/~berstel/LivreTransductions/LivreTransductions14dec2009.pdf" rel="nofollow">Rational transductions and context-free languages</a> by J. Berstel.</p>

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

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

<ol>
<li>(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.</li>
<li>(Schützenberger 1976. See theorem 4.5) A function is rational if and only if it admits a semimonomial representation.</li>
<li>(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.</li>
</ol>

<p>See also A. Arnold and M. Latteux, <a href="http://dx.doi.org/10.1016/0304-3975%2879%2990049-5" rel="nofollow">A new proof of two theorems about rational transductions</a>, <em>Theoret. Comput. Sci</em>. <strong>2</strong> (1979), 261–263.</p>

CC BY-SA 3.0
2015-01-07T14:14:48.823Z
2015-01-08T16:35:52.227Z
2015-01-08T16:35:52.227Z
J.-E. Pin
<p>I recently became aware of the rather appealing characterization of deterministic word-to-word transductions as word functions with <em>bounded variation</em> (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.</p>

<p>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?</p>

<p>Thanks!</p>

<p>[1] Bruyère, Véronique and Reutenauer, Christophe.  A proof of choffrut's theorem on subsequential functions. Theoretical Computer Science, 1999.</p>

CC BY-SA 3.0
2014-12-22T23:33:25.850Z
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
CC BY-SA 3.0
2015-01-05T14:16:01.447Z
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
<reference-request><fl.formal-languages><automata-theory>
Extensional characterization of non-deterministic finite state transductions
Ulrik Rasmussen
# Extensional characterization of non-deterministic finite state transductions

(Asked by: username_0 on 2014-12-22)

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.

**Tags:** reference-request, fl.formal-languages, automata-theory

> **Comments:**
> **username_1**: 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  
> **username_0**: 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.  

---

## 1 answers

### Answer by username_2 on 2015-01-07. Score: 6 | Accepted answer

The best reference is probably the book [Rational transductions and context-free languages](http://www-igm.univ-mlv.fr/~berstel/LivreTransductions/LivreTransductions14dec2009.pdf) 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.

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.
2. (Schützenberger 1976. See theorem 4.5) A function is rational if and only if it admits a semimonomial representation.
3. (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](http://dx.doi.org/10.1016/0304-3975%2879%2990049-5), *Theoret. Comput. Sci*. **2** (1979), 261–263.


---

