Two-way transducers are ordinary finite two-way automata that are provided with a one-way write-only tape. They perform a word to word transformation. Unlike one-way transducers, no characterization of these objects as such exists so far except for the deterministic case. We study the other particular case where the input and output alphabets are both unary but when the transducer is not necessarily deterministic. This yields a family which extends properly the rational relations in a very natural manner. We show that deterministic two-way unary transducers are no more powerful than one-way transducers.
In the theory of words, two different terms are more or less indifferently used to describe the same objects: transductions and binary relations. The former term distinguishes an input and an output, even when the input does not uniquely determine the output. In certain contexts it is a synonym for translation where one source and one target are understood. The latter term is meant to suggest pairs of words playing a symmetric role.
Transducers and two-tape automata are the devices that implement the
transductions and relations respectively. The concept of multitape- and thus
in particular two-tape automata was introduced by Rabin and Scott [
Our purpose is to define a structural characterization of these relations in the same way that the relations defined by multi-tape automata are precisely the rational relations. However we limit our investigation to the case where the input and output are words over a one letter alphabet, i.e., to the case where they both belong to the free monoid a∗ generated by the unique letter a. Our technique does not apply to non-unary alphabets. The input is written over one tape and is delimited by a left (. ) and a right (/) endmarker which prevents the reading head to fall off the input. An output is written on a second write-only tape. Formally a two-way transducer can be defined as a pair (A, φ ) where A is a two-way automaton of transition set δ and φ is a production function, mapping δ into output words.
We now state our main result more precisely. Let Σ and Δ be respectively the input and the output alphabets. Given a binary relation R ⊆ Σ ∗ × Δ ∗ and a word u in Σ ∗ we put R(u) = { v | (u, v) ∈ R} . We recall that R is rational if it belongs to the smallest family of subsets of Σ ∗ × Δ ∗ which contains the finite languages and which is closed under set union, componentwise concatenation and Kleene star. We are able to prove the following Theorem 1. A relation of the monoid a∗ × a∗ is defined by a two-way transducer if and only if it is a finite union of relations R satisfying the following condition: there exist two rational relations S, T ⊆ a∗ × a∗ such that for all x ∈ a∗ we have
R(x) = S(x)T (x)∗
The relation { (an, akn) | n, k ≥ 0} is a simple example. It is of the previous form, however it is not rational. Indeed, identifying a∗ with the additive monoid of integers N this relation denfies the relation “being a multiple of.” However rational subsets of N are first-order definable in Presburger arithmetics, i.e., arithmetics with addition only.
We now briefly mention the few results which to the best of our knowledge are
published on two-way transducers. Engelfriet and Hoogeboom showed links
between two-way transducers and logic [
As suggested in introduction by R(u) notation, a relation R ⊆ Σ ∗ × Δ ∗ can be considered as a function from Σ ∗ into P(Δ ∗ ) or, equivalently, as a series over Σ ∗ with its coefficient in P(Δ ∗ ). The set of such series is denoted by P(Δ ∗ ) hhΣ ∗ ii. This representation is the most convenient for our work. Thus, we will identify a relation R with its associated series fR : u → { v | (u, v) ∈ R} . In the same spirit we will speak of the series accepted by a two-way transducer. We use the traditional notation hs, ui in place of fR(u).
In addition to standard rational operations on series (sum, Cauchy product and Kleene star), we need two operations which we called Hadamard- or simply H-operations. The first one is the usual Hadamard product of two formal series: the coefficient of a word in a product is the product of the coefficients in the two series; the second happens to be new. – the Hadamard product (or H-product): s H t : ∀ u ∈ Σ ∗ , hs H t, ui = hs, ui ht, ui – the Hadamard star (or H-star): sH? : ∀ u ∈ Σ ∗ , sH?, u = hs, ui∗
Denoting by Id the series associated to the identity relation, the series associated to the relation (an, akn) | n, k ≥ 0 is equal to IdH?. The following is general but provides, when restricted to the case where Δ is unary, one direction of our main theorem 4.
Proposition 1. If s and t are series accepted by two-way transducers, so are the series s H t and sH?.
The family of rational series over the semiring K, denoted RatK hhΣ ∗ ii, is the
smallest family of series over Σ ∗ with coefficients in the semiring K which
contains the polynomials, i.e., series with finitely many non empty coefficients, and
which is closed under rational operations. The following result is classical [1,
Theorem III. 7.1][
The family RatK hhΣ ∗ ii is not closed under H-operations for an arbitrary semiring. However when K is commutative the following holds, [8, Thm III. 3.1] Theorem 3. If K is commutative then RatK hhΣ ∗ ii is closed under H-product. The H-star of a rational series is not necessarily rational, even when Σ is unary. Therefore the following defines a broader family.
Definition 1. The family of Hadamard series, denoted HadK hhΣ ∗ ii is the set of finite sums of Hadamard products of the form α H β H? with α, β ∈ RatK hhΣ ∗ ii.
Proposition 2. If K is commutative, the family HadK hhΣ ∗ ii is closed under finite sum, H-product and H-star. 3
From now on we concentrate on unary two-way transducers, i.e., on those with input and output alphabets reduced to the letter a and characterize the relations they define. We fix a transducer (A, φ ).
The following is a reformulation of Theorem 1 in terms of series. Theorem 4. Let K denote the semiring Rat(a∗ ). A series s ∈ P (a∗ ) hha∗ ii is accepted by some two-way finite transducer if and only if s ∈ HadK hha∗ ii, i.e., there exist a finite collection of rational series α i, β i ∈ RatK hha∗ ii such that: s =
X α i H β iH? i
The fact that the condition is sufficient is a direct consequence of Theorem 2 and Proposition 1. The other direction is more involved. We proceed as follows. We first show that if the transducer performs a unique hit, i.e., it never visits endmarkers except at the beginning and at the end of the computation, it defines a rational relation. Then we use the closure properties of Property 2 to prove that the full binary relation with the possibility of performing an arbitrary number of hits, belongs to HadK hha∗ ii.
We adapt a well-known construction based on crossing sequences, i.e., sequence of destination states of transitions performed between two successive tape positions, in chronological order (see [6, page 36-42] for details). Using the commutativity of Δ ∗ , we are able to simulate by a one-way transducer, any loopfree run of (A, φ ), i.e., run that never visit the same position twice in the same state. Then, using again the commutativity of Δ ∗ and the fact that Σ is unary we extend this result to any hit, with or without loops. It is then possible to restrict this simulation to hits whose first and last configuration matches some fixed border points, i.e., elements from Q × { ., / } (the second component is the endmarker associated to the side of the tape).
Lemma 1. Given a transducer, and two border points b0 and b1, there exists a computable one-way transducer that simulates any b0 to b1 hits.
We first adapt the matrix multiplication to the Hadamard product. Let N be an integer and let be given two matrices X, Y ∈ (K hhΣ ∗ ii)N× N . We define the H-product of X and Y and also the H-star of X as the matrices: X H Y = PN k=1 Xi,k H Yk,j k times (X)H? = P∞k=0 zX H · }·| · H X{ Proposition 3. If the matrix X is in (HadK hhΣ ∗ ii)N× N then so is (X)H?.
Proof (Theorem 4). In one direction this is an immediate consequence of the fact that the family of series associated with a two-way transducer is closed under sum, Hadamard product and Hadamard star, see Proposition 1.
It remains to prove the converse. Let T be a transducer. Consider a matrix X whose rows and columns are indexed by the pairs Q × { ., / } of border points. For all pairs of border points b0 and b1, its (b0, b1) entry is, by Lemma 1, the rational series associated to b0 to b1 hits of T . The series accepted by T is the sum of the entries of XH? in position ((q− , . ), (q, /)) for q an accepting state. Since all rational series are also Hadamard series, we conclude by Proposition 2.
Our main result of Theorem 1 gives a characterization of relations (series) accepted by two-way unary transducers. A key point is that crossing sequences of loop-free runs have bounded size. In consequence, any loop-free runs can be simulated by a one-way transducer. We point out that this simulation does not require any hypothesis on the size of the input alphabet.
We fix a transducer T = (A, φ ) accepting a relation R ⊆ Σ ∗ × Γ ∗ , with | Γ | = 1. If A is deterministic or unambiguous (i.e., for each input word u, there exists at most one accepting run of A on u), then every accepting run is loop-free. Therefore, by the previous remark, T is equivalent to some constructible one-way transducer. Another interesting case is when R is a function (T is functional). Then for each u, all the accepting runs on u produce the same output word. Hence, considering only loop-free runs preserves the acceptance of T . Corollary 1. Let R ⊆ Σ × Δ with | Δ | = 1 be accepted by some two-way transducer T = (A, φ ). If A is unambiguous or if R is a function then R is rational.
A rational uniformization of a relation R ⊆ Σ ∗ × Γ ∗ , is a rational function F ⊆ R, such that the domain of F is equal to the one of R. Under the hypothesis | Γ | = 1, it is possible to build a one-way transducer accepting such a F . Since the transducer obtained from our work is not necessary functional, the construction involves a result of Eilenberg [2, Prop. IX 8. 2] solving the rational uniformization problem for rational relations.
Corollary 2. There exists a computable one-way transducer accepting a rational uniformization of R.
As a consequence of Lemma 1, in the case of unary transducers, the change
of direction of the input head can be restricted to occur at the endmarkers only.
In the literature such machines are known as sweeping machines [