3
$\begingroup$

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!

Improve this question
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$ – Michaël Cadilhac Mar 3 '15 at 12:52
  • $\begingroup$ @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! $\endgroup$ – Henry DeYoung Mar 3 '15 at 17:09
  • $\begingroup$ 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." $\endgroup$ – Michaël Cadilhac Mar 3 '15 at 17:28
  • $\begingroup$ @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? $\endgroup$ – Henry DeYoung Mar 3 '15 at 18:17
  • $\begingroup$ 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. $\endgroup$ – Michaël Cadilhac Mar 3 '15 at 18:53
5
$\begingroup$

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

Improve this answer
$\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.