1
$\begingroup$

For a project I'm working on, it would seem useful to have a normal form for deterministic (sub)sequential transducers in which the set of states, $Q$, is partitioned into states, $r \in Q_R$, that read a letter from the input tape (but do not write any output) and states, $w \in Q_W$, that write a letter to the output tape (but do not read any input). The goal is to have (inputs and) outputs occur one letter at a time.

In some proofs that I've seen, a similar kind of normal form is used for deterministic pushdown automata. What I'm looking for is papers that use this kind of normal form in the context of (sub)sequential transducers. Does anyone know of any references?

Specifically, in the normal form that I'm thinking about, there would be two transition functions, one for each part of the partition $Q = Q_R \cup Q_W$: $$\begin{eqnarray} \delta_R &:& Q_R \times \Sigma \to Q \\ \delta_W &:& Q_W \to \Gamma \times Q \\ \end{eqnarray}$$ To enforce finite output, each cycle in the state-transition graph must contain at least one state from $Q_R$. (For subsequential transducers, I think that one needs another class of "terminal write states" that can be entered from a "read state" only when the input has been completely read.)

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

I'm not sure what your question is. Tell me if I am mistaken. From what I understand: Given a subsequential transducer, you can easily transform it into your canonical form by replacing every transition $(q,a)\to (p,v)$ into a transition reading $a$ and producing nothing followed by a sequence of transitions reading nothing and producing $v$ one letter at a time.

On the other hand, given such a transducer with $\epsilon$ transitions where all loop read some letter, you can compress the finite $\epsilon$-paths to get to a classical sequential transducer.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Yes, that's what I'm thinking. I'm interested in references to any literature that use that canonical form for sequential, and especially subsequential, transducers. Do you know of any such references? $\endgroup$
    – Henry DeYoung
    Commented Feb 2, 2016 at 16:26
  • $\begingroup$ Extending this canonical form to subsequential transducers seems slightly inelegant in that I think that one needs another class of "terminal write states" that can be entered from a "read state" only when the input has been completely read. Do you know how this is handled in the literature? $\endgroup$
    – Henry DeYoung
    Commented Feb 2, 2016 at 16:29
  • $\begingroup$ Right now I can't think of a reference for this, but the construction seems quite standard and can be used directly. The two models are (with and without no-loop \epsilon transitions) are really equivalent. $\endgroup$
    – L. Dartois
    Commented Feb 3, 2016 at 9:40
  • $\begingroup$ Ok, thank you! Do you remember how subsequential transducers and their terminal suffix function is handled in this kind of "letter-at-a-time" canonical form? The only thing I can think of is the "class of terminal write states" that I mentioned earlier, but it seems a bit inelegant. I'm sorry if these questions are elementary or folklore in automata and languages. My research area is proof theory, so I'm a bit out of my element. Thanks again for your help! $\endgroup$
    – Henry DeYoung
    Commented Feb 3, 2016 at 18:01
  • $\begingroup$ I'm afraid it cannot be done elegantly and in a deterministic fashion. However, you can replace this function in the same way, with a sequence of espilon-transitions. This introduces nondeterminism (you can always take these epsilon transitions) but you have unambiguity, meaning that a given input word has only one accepting run. Another way to do it might be to add a final new letter #, depending on what you want to achieve. Can I ask why do you need this ? $\endgroup$
    – L. Dartois
    Commented Feb 4, 2016 at 8:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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