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.