Finite state transducer with infinitary outputs or without emphasis on acceptance?

Question

1) Is there a notion of (deterministic) finite state transducer (FST) that allows the possibility of producing an infinite stream of output symbols? In other words, one where the transduction relation is a subset of $\Sigma^* \times \Gamma^\omega$ (as opposed to $\Sigma^* \times \Gamma^*$)?

For example, the definition of an FST given on Wikipedia involves a transition relation $\delta \subseteq Q \times (\Sigma \cup \{\epsilon\}) \times (\Gamma \cup \{\epsilon\}) \times Q,ドル which might first seem to permit infinite streams of output. However, the transduction relation is defined inductively (basically, the reflexive-transitive closure of $\delta$), thereby ruling out infinitary outputs.

2) Relatedly, the definitions of FSTs that I've seen include a subset $F \subseteq Q$ of accepting states. Is there a name for the class of (deterministic) FSTs in which $F = Q,ドル i.e., in which all input strings are accepted and the emphasis is placed on the output?

Any references that you can point me to would be greatly appreciated!

• Michaël Cadilhac: Small remarks: 1) I cannot conceive Wikipedia's definition as infinitary in your sense, do you think of $\varepsilon$-cycles as producing $\omega$-words? 2) If you consider only deterministic FSTs, then $F = Q$ means that the underlying transduction function is total. I've seen a few papers where this term was used for the transducer itself.
• Henry DeYoung: @MichaëlCadilhac 1) Yes, I was thinking of something like $(q, \epsilon, b, q) \in \delta$ as describing a state $q$ that produces an infinite stream of $b$s. Does that make sense? 2) So, a "total deterministic FST" is what you would call the class I describe? Sorry if these questions are rudimentary. My background is in logic and programming languages, so I'm in unfamiliar territory. Thanks for your help!
• Michaël Cadilhac: 1) There are multiple problems with such an approach; the most obvious one is that $\omega$-words have to be construed to the ending portion of a produced word ($a^\omega b^\omega$ making no sense). The references of Prof. Pin should cover more sound alternatives. 2) I'm not a big fan of that term, but I've seen similar formulations. I'd go for something more lengthy, e.g., "a deterministic transducer inducing a total function."
• Henry DeYoung: @MichaëlCadilhac I could've missed it when reviewing J.-E. Pin's references, but would determinism resolve the $a^\omega b^\omega$ problem that you describe? To produce $a^\omega,ドル there must be an $\epsilon$-cycle starting from some $q$. But, to be deterministic, state $q$ can only have that one $\epsilon$-transition out of $q,ドル so producing $b^\omega$ is not possible. Perhaps?
• Michaël Cadilhac: Ah, my bad, I didn't see that you were requiring determinism in the first case. Then what you may want is some sort of subsequential transducer, that is, a sequential transducer with an added function $Q \to T^\omega$ that adds some extra $\omega$-word at the end of the process. I'm not sure this is covered by Prof. Pin's references—I'd definitely be interested if you could report on that after reading them.

Answer 1

There are several relevant references on the subject. I just indicate a few of them. I suggest you to browse the references of these articles to get more.

Early references include the work of Françoise Gire.

[1] F. Gire, "Relations rationnelles infinitaires", Thèse de 3ème cycle, Paris VII, 1981.

[2] F. Gire, Une Extension aux Mots Infinis de la Notion de Transduction Rationnelle, 6th GI Conf., Lect. Notes in Comp. Sci., Volume 145, 1983, p. 123-139.

[3] F. Gire, M. Nivat, Relations rationnelles infinitaires. [Infinitary rational relations] Calcolo 21 (1984), no. 2, 91--125.

Interesting results can be found in

[4] Latteux, M.; Timmerman, E. Rational $\omega$-transductions. Mathematical foundations of computer science (Banská Bystrica, 1990), 407--415, Lecture Notes in Comput. Sci., 452, Springer, Berlin, 1990.

Section 4.3 of [5] is also a very good reference.

[5] L. Staiger, ω-Languages, Vol 3, Chapter 6 of the Handbook of Formal languages edited by G. Rozenberg and A. Salomaa, (1997) 339-387. Springer-Verlag, Berlin.

Finally, here is a more recent paper, where you will find other relevant references.

[6] Finkel, Olivier. On the accepting power of 2-tape Büchi automata. STACS 2006, 301--312, Lecture Notes in Comput. Sci., 3884, Springer, Berlin, (2006).