7
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – Denis Dec 22 '14 at 23:33
  • $\begingroup$ 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. $\endgroup$ – Ulrik Rasmussen Jan 5 '15 at 14:16
6
$\begingroup$

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.

  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, Theoret. Comput. Sci. 2 (1979), 261–263.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.