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

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

CC BY-SA 3.0
2016-02-02T16:26:00.187Z
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?
Henry DeYoung
CC BY-SA 3.0
2016-02-02T16:29:02.717Z
Extending this canonical form to *sub*sequential 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?
Henry DeYoung
CC BY-SA 3.0
2016-02-03T09:40:13.787Z
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.
L. Dartois
CC BY-SA 3.0
2016-02-03T18:01:32.930Z
Ok, thank you!  Do you remember how *sub*sequential 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!
Henry DeYoung
CC BY-SA 3.0
2016-02-04T08:32:14.263Z
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 ?
L. Dartois
CC BY-SA 3.0
2016-02-08T16:45:36.593Z
I am trying to relate formal derivations in a proof theory to subsequential transducers -- a kind of Curry-Howard correspondence.  The proof theory strongly suggests that outputs be letter-at-a-time, which is why I'm asking about all of this.  Thanks for your help!
Henry DeYoung
CC BY-SA 3.0
2016-02-02T14:36:26.260Z
2016-02-02T14:36:26.260Z
L. Dartois
<p>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.</p>

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

<p>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 &amp;:&amp; Q_R \times \Sigma \to Q \\
\delta_W &amp;:&amp; 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 <em>sub</em>sequential 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.)</p>

<reference-request><automata-theory>
Normal form for deterministic (sub)sequential transducers with letter-by-letter outputs
Henry DeYoung
# Normal form for deterministic (sub)sequential transducers with letter-by-letter outputs

(Asked by: username_0 on 2016-02-01)

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 *sub*sequential 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.)

**Tags:** reference-request, automata-theory


---

## 1 answers

### Answer by username_1 on 2016-02-02. Score: 3

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.

> **Comments:**
> **username_0**: 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?  
> **username_0**: Extending this canonical form to *sub*sequential 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?  
> **username_1**: 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.  
> **username_0**: Ok, thank you!  Do you remember how *sub*sequential 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!  
> **username_1**: 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 ?  
> **username_0**: I am trying to relate formal derivations in a proof theory to subsequential transducers -- a kind of Curry-Howard correspondence.  The proof theory strongly suggests that outputs be letter-at-a-time, which is why I'm asking about all of this.  Thanks for your help!  

---

