A transducer is a finite automaton equipped with an output tape, scanned in one direction by a write-only output head. At each step of the computation, a word associated with the chosen transition is appended on to the output tape. Such a device accepts a relation on words,
i.e., a subset of Σ* × Γ* where Σ (
resp. Γ) is the input (
resp. output) alphabet. The model admits different variants, namely one-way deterministic (
1DT), one-way nondeterministic (
1NT), two-way deterministic (
2DT), and two-way nondeterministic (
2NT). Contrary to the case of finite automaton, each version accepts a distinct family of relations. Until now and despite the simplicity of the model, no characterization of the most general variant, namely the
2NT, has been established.
I will introduce all these devices, and additional operations on relations. Then I will give an algebraic characterization of the relations accepted by
2NT, in the particular case of unary input and output alphabets, that is, when both Σ and Γ are reduced to a single letter. Then I will show with some provable examples that these strong assumptions are required. Finally, I will give some general remarks and corollaries.