Vincent Carnino
email: vincent.carnino@univ-mlv.fr

Sylvain Lombardy
email: sylvain.lombardy@labri.fr

On Determinism and Unambiguity of Weighted Two-way Automata

In this paper, we first study the conversion of weighted two-way automata to one-way automata. We show that this conversion preserves the unambiguity but does not preserve the determinism. Yet, we prove that the conversion of an unambiguous weighted one-way automaton into a two-way automaton leads to a deterministic two-way automaton. As a consequence, we prove that unambiguous weighted two-way automata are equivalent to deterministic weighted two-way automata in commutative semirings.

Introduction

A classical question in automata theory concerns the expressive power of a device and especially the difference between one-way devices and two-way devices. It is well known that two-way automata may be reduced to one-way automata and therefore recognize the same language family [START_REF] Shepherdson | The reduction of two-way automata to one-way automata[END_REF][START_REF] Rabin | Finite automata and their decision problems[END_REF].

In this paper, we deal with the weighted versions of these two devices. We describe the conversion of a two-way automaton over a commutative sering into a one-way automaton. Such an algorithm has already be stated in [START_REF] Anselmo | Two-way Automata with Multiplicity[END_REF]; our construction is close, but we are mainly interested here in proving that this conversion preserves the unambiguity of automata; it does not preserve the determinism.

We then present a construction for the conversion of any unambiguous one-way automaton into a deterministic two-way automaton; this part does not require that the semiring is commutative.

A consequence of these two procedure is that, on commutative semirings, opposite to the case of one-way automata, unambiguous two-way automata are not more powerful than deterministic ones.

Weighted Two-way Automata

Automata and runs

A semiring K is a set endowed with two binary associative operations, ⊕ and ⊗, such that ⊕ is commutative and ⊗ distributes over ⊕. The set K contains two particular elements, 0 K and 1 K that are respectively neutral for ⊕ and ⊗; moreover, 0 K is an annihilator for ⊗.

For every alphabet A, we assume that there exist two fresh symbols ⊢ and ⊣ that are marks at the beginning and the end of the tapes of automata. We denote A ⊢ ⊣ the alphabet A ∪ {⊢, ⊣}. For every word w in A, w ⊢ ⊣ is the word in A ⊢ ⊣ equal to ⊢ w ⊣.

One-way and two-way K-automata share a part of their definition. A K-automaton is a tuple A = (Q, A, E, I, T ) where Q is a finite set of states, A is a finite alphabet, and I and T are partial functions from Q to K. The support of I, I, is the set of initial states of A , and the support of T , T , is the set of final states of A . The definition of transitions differ. In a two-way K-automaton, E is a partial function from Q × (A ⊢ ⊣ × {-1, +1}) × Q into K and the support of E, E, is the set of transitions of A . Moreover, the intersection of E and Q × ({⊢} × {-1} ∪ {⊣} × {1}) × Q must be empty. Let t be a transition in E; if t = (p, a, d, q), we denote σ (t) = p, τ(t) = q, λ (t) = a, δ (t) = d. On figures, the value of δ is represented by a left (-1) or right (+1) arrow. For instance, if t = (p, a, -1, q) and E t = k, we draw p a,←|k ----→ q. In a one-way K-automaton, E is a partial function from Q × A × Q into K, and the support of E, E, is the set of transitions of A . Let t be a transition in E; if t = (p, a, q), we denote σ (t) = p, τ(t) = q, λ (t) = a. Example 1. Let A 1 be the two-way N -automaton of Figure 1, where N = (N ∪ {∞}, min, +) is the tropical semiring; since the multiplication law in this semiring is the usual sum, the weight of a path in this automaton is the sum of the weights of its transitions. This automaton is deterministic (cf. Definition 9) and thus there is only one computation for each accepted word. The behaviour of this automaton is quite easy. For each block of ′ a ′ it checks through a left-right reading, whether the length of the block is odd; if it is, a right-left reading computes the length of the block; otherwise the automaton goes to the next block of ′ a ′ . Definition 1. Let w = w 1 . . . w n be a word of A * , we set w 0 = ⊢ and w n+1 = ⊣. A configuration of A on w is a pair (p, i) where i is in [0; n + 1] and p is a state of A . A computation (or run) ρ of A on w is a finite sequence of configurations ((p 0 , i 0 ), . . . , (p k , i k )) such that :

• i 0 = 1, i k = n + 1, p 0 is in I and p k is in T ;
• for every j in [0; k -1], there exists t j , such that σ (t j ) = p j , τ(t j ) = p j+1 , λ (t j ) = a i j , and i j+1 = i j + δ (t j ).

The weight of such a computation, denoted by |ρ|, is

I(p 0 ) ⊗ k-1 j=0 E(t j ) ⊗ T (p k ).
The weight of w in A , denoted by |A |, w , is the addition of the weights of all the runs with label w in A . Notice that there may be an infinite number of computations with the same label w. The definition of the behaviour of A in this case requires to study the definition of infinite sums. This can be done, like for one-way K-automata with ε-transitions, for instance with complete semirings or topological semirings [START_REF] Lombardy | The validity of weighted automata[END_REF]. This is not the purpose of this paper, since we mainly deal with two-way automata where the number of computations is finite for every word. Example 2. A run of the N -automaton A 1 over the word abaaba is represented on Figure 2. The weight of this run is equal to 2. Definition 2. Let ρ = ((p 0 , i 0 ), . . . , (p k , i k )) be a run over w. If there exists m, n in [1, k], with m < n such that (p m , i m ) = (p n , i n ), then we say that ((p m , i m ), . . . , (p n , i n )) is an unmoving circuit of ρ. If ρ does not contain any unmoving circuit, it is reduced. Lemma 1. If a two-way K-automaton admits a run ρ which is not reduced, it admits a reduced run with the same label.

⊢ a b a a b a ⊣ p q r s q p p q p p q r s q p → |0 ← |0 ← |1 → |0 → |0 → |0 → |0 → |0 → |0 → |0 ← |0 ← |1 → |0 → |0
Proof. We consider a shortest non reduced run ρ = ((p 0 , i 0 ), . . . , (p m , i m ), . . . , (p n , i n ), . . . , (t k , i k )), with (p m , i m ) = (p n , i n ). Then ((p 0 , i 0 ), . . . , (p m-1 , i m-1 ), (p n , i n ), . . . , (p k , i k )) is a run; by minimality of ρ, this run is reduced.

Definition 3. A one-way or two-way automaton A is unambiguous if every word labels at most one computation.

Unambiguous automata have obviously only reduced computations.

Coverings

We extend here the notion of covering (cf. [START_REF] Sakarovitch | Elements of Automata Theory[END_REF]) to two-way automata. A = (Q,A,E,I,T ) and B = (R, A, F, J,U ) be two weighted two-way automata. E,I,T ) and B = (R, A, F, J,U ) be two weighted two-way automata. A is a covering of B if there exists a surjective morphism ϕ from A onto B such that

Definition 4. Let

A mapping ϕ from Q into R is a morphism if, i) ∀p ∈ I, J(ϕ(p)) = I(p); ii) ∀p ∈ T , U (ϕ(p)) = T (p); iii) ∀t = (p, a, δ , q) ∈ E, φ(t) = (ϕ(p), a, δ , ϕ(q)) ∈ F and F( φ(t ′ )) = E(t). The morphism is surjective if ϕ(Q) = R, ϕ(I) = J, ϕ(T ) = U , and φ(E) = F. Definition 5. Let A = (Q, A,
i) ∀r ∈ U , ϕ -1 (r) ⊆ T ii) ∀r ∈ J, ∃!p ∈ ϕ -1 (r) ∩ I iii) ∀t ∈ F, ∀p ∈ ϕ -1 (σ (t)), ∃!t ′ ∈ φ-1 (t), σ (t ′ ) = p.
A is an in-covering of B is there exists a surjective morphism ϕ from A onto B such that

i) ∀r ∈ J, ϕ -1 (r) ⊆ I ii) ∀r ∈ U , ∃!p ∈ ϕ -1 (r) ∩ T iii) ∀t ∈ F, ∀q ∈ ϕ -1 (τ(t)), ∃!t ′ ∈ φ-1 (t), τ(t ′ ) = q.
Proposition 1. Let A and B be two weighted two-way automata. If A is a covering (resp. an incovering) of B, the corresponding morphism ϕ induces a bijection between computations of A and B such that every computation of A and its image in B have the same label and the same weight.

Proof. Assume that A is a covering of B. Let w be a word and let ((p 0 , i 0 ), . . . , (p k , i k )) be a computation on w in A . For every j in [0; k], we set r j = ϕ(p j ); by definition of a morphism ((r 0 , i 0 ), . . . , (r k , i k )) is a computation on w in B with the same weight. Conversely, let ((r 0 , i 0 ), . . . , (r k , i k )) be a computation in B. Let p 0 be the unique initial state in ϕ -1 (r 0 ).For every j in [0; k -1], let δ j = i j+1 -i j ; the configuration (r j+1 , r j+1 ) is reached from configuration (r j , i j ) through the transition (r j , w j , δ j , r j+1 ); inductively, we define p j+1 as the unique state in ϕ -1 (r j+1 ) such that (p j , w j , δ j , p j+1 ) is a transition of A . Then, ((p 0 , i 0 ), . . . , (p k , i k )) is a computation on w in A . Hence, every computation ρ of B is lift up in a unique way into a computation of A whose image by ϕ is ρ.

The proof is similar for in-coverings.

This proposition implies that a two-way automaton and its covering (resp. in-covering) are equivalent; moreover, if a two-way automaton is unambiguous, so is every of its (in-)coverings.

δ -Locality Definition 6. Let A be a two-way K-automaton. If, for each state p of A , every transition outgoing from p has the same direction, then

A is δ -local.
If Q is the set of states of a two-way K-automaton, we denote Q + (resp. Q -) the set of states p such that, for every transition t outgoing from p, δ (t) = +1 (resp. δ (t) = -1); by convention, if p has no outgoing transition, p is in Q + . For every state

p of Q + (resp. Q -), we set δ (p) = 1 (resp. δ (p) = -1). If A is a δ -local automaton, {Q + , Q -} is a partition of Q.
Proposition 2. Every two-way K-automaton admits a δ -local in-covering.

Proof. In this proof, we denote ± = {-1, +1}. Let A = (R, A, F, J,U ) be a two-way K-automaton and let P = R \ (R + ∪ R -) be the set of states in A such that there are at least two transitions with different direction outgoing from each state. Let P + and P -be two copies of P and let

Q = R + ∪ R -∪ P + ∪ P -.
Let ϕ be the canonical mapping from Q onto R: it maps every element of P + or P -onto the corresponding element of P. Let φ be the mapping from E,I,T ) be the automaton defined by:

Q × A ⊢ ⊣ × ± × Q into R × A ⊢ ⊣ × ± × R defined by φ(p, a, d, q) = (ϕ(p), a, d, ϕ(q)). Let A ′ = (Q, A,
I = ϕ -1 (J); T = ϕ -1 (U) \ P -; E = {(p, a, d, q) ∈ φ-1 (F) | (p, d) ∈ (P + ∪ R + ) × {+1} ∪ (P -∪ R -) × {-1}}; ∀p ∈ I, I(p) = J(ϕ(p)), ∀p ∈ T , T (p) = U (ϕ(p)), ∀t ∈ E, E(t) = F( φ(p)).
The automaton A ′ is δ -local and it is an in-covering of A . Example 3. The automaton A 1 of Figure 1 is not δ -local; from state q (resp. s), there are transitions leaving with δ = 1 and other ones with δ = -1. The automaton A ′ 1 of Figure 3 is a δ -local in-covering of A 1 . Notice that an in-covering of a deterministic automaton is not necessarily deterministic.

p q r s - s + b, →| 0 a, →| 0 a, →| 0 ⊣, ←| 0 b, ←| 0 a, ←| 1 a, ←| 1 a, ←| 1 b, →| 0 ⊢, →| 0
Actually, on A ′ 1 , transitions s + b,→|0 ----→ q -and s + ⊢,→|0
----→ q -do not belong to any computation, since the label of any trnasition that would follow one of these boths transitions should be the same as the label of the transition arriving at s -(a), and there is no transition outgoing from q -with label a.

Slices

In this section, we describe the conversion of two-way automata over commutative semirings into oneway automata. We give sufficient conditions to get finite one-way automata.

The Slice Automaton

Definition 7. Let A = (Q, A, E, I, T ) be a two-way K-automaton and let w = w 1 . . . w k be a word. ρ = ((p 0 , i 0 ), . . . (p n , i n )) be a run over w, and j in [1; k + 1]. Let h be the subsequence of all pairs (p r , i r ) such that (i r , i r+1 ) = ( j, j + 1) or (i r-1 , i r ) = ( j, j -1). The j-th slice of ρ is the vector s ( j) of states obtained by the projection of the first component of each pair of h. The signature S(ρ) of ρ is the sequence of its slices.

The slices we define here are not exactly the crossing sequences defined in [START_REF] Shepherdson | The reduction of two-way automata to one-way automata[END_REF]. Example 4. The vector q r p is the second (and the seventh) slice of the run of Figure 2. The signature of this run is:

p s q , q r p , p , q , p , p s q , q r p . ( 1
)
The signature of the (unique) run on the word abaaba in the automaton

A ′ 1 is p s + q + , q - r p , p , q + , p , p s + q + , q - r p . (2)
Let A = (Q, A, E, I, T ) be a δ -local two-way K-automaton. To define a one-way K-automaton from slices we consider the set X of subvectors of slices, that are vectors v in Q * with an odd length; let Y be the vectors v in Q * with an even length.

We define inductively two partial functions θ :

X × A × X → K and η : Y × A ×Y → K by: η(ε, a, ε) = 0 K , ∀p, q ∈ Q, δ (p) = 1 =⇒ ∀u, v ∈ Y, θ (pu, a, qv) = E(p, a, 1, q) + η(u, a, v), η(u, a, pqv) = E(p, a, 1, q) + η(u, a, v), δ (p) = -1 =⇒ ∀u, v ∈ X , θ (pqu, a, v) = E(p, a, -1, q) + θ (u, a, v), η(qu, a, pv) = E(p, a, -1, q) + θ (u, a, yv). ( 3
) Since A is δ -local, for every triple (u, a, v) in X × A × X , if θ (u, a, v
) is defined, it is uniquely defined.

For every vector pu in X , pu is initial if p is in I and (ε, ⊢, u) is in η; in this case, we set

I (pu) = I(p) + η(ε, ⊢, u). Likewise, every vector up in X is final if p is in T and (u, ⊣, ε) is in η; in this case, we set T (up) = η(u, ⊣, ε) + T (p).
Example 5. For instance, with slices from automaton A 1 ,

θ p s + q + , a, q - r p =E(p, a, 1, q -) + η s + q + , a, r p =E(p, a, 1, q -) + E(r, a, -1, s + ) + θ (q + , a, p) =E(p, a, 1, q -) + E(r, a, -1, s + ) + E(q + , a, 1, p). ( 4
)
The vector p s + q + is initial and

I p s + q + = I(p) + E(s + , ⊢, 1, q + ). (5)
Definition 8. Let A = (Q, A, E, I, T ) be a two-way K-automaton. With the above notations, the slice automaton of A is the infinite one-way K-automaton C = (X , A, θ , I , T ).

Proposition 3. Let K be a commutative semiring and let A be a δ -local two-way K-automaton. There is a bijection ϕ between the computations of A and the computations of the slice automaton of A such that, for every computation ρ of A , -ρ and ϕ(ρ) have the same label and the same weight; -the signature of ρ is the sequence of states of ϕ(ρ).

Proof. Let C be the slice automaton of A . Let π be a run in C with label w. Let π (k) be the prefix of length k of π and let (v (0) , . . . , v (k) ) be the sequence of states of π (k) . We show by induction on k that from π (k) , there is a unique way to retrieve the restriction of a run of A on w to the k first letters. Moreover, the weight of π (k) (including initial weight) is equal to the weight of this restriction. If k = 0, π (k) is reduced to an initial slice. By Equation 3, the restriction of the path in the two-way automaton is

uniquely defined: v (0)
1 is initial with weight I(v

(0)
1 ), and for every r in [1; (v (0) -1)/2], there is a transition

v (0) 2r ⊢,→|h r -----→ v (0)
2r+1 ; the weight of this restriction is actually the initial weight of v (0) in C . If k > 0, we consider the restriction built for k -1; this restriction corresponds to a disjoint union of parts of the

p q r 0, →| 1/2 1, →| 1/2 1, →| 1 2 0, →| 1 1, →| 1 0, ←| 1 1, ←| 1 ⊣, ←| 1 ⊢, →| 1 Figure 4: The two-way Q-automaton A 2 .
computations and there is only one way to connect them to the states of the slice v (k) (since A is δlocal). The weight of the transition between v (k-1) and v (k) is exacltly the sum of the weights of the new transitions involved in the restriction. Finally, from the restriction of length |w|, if we consider v (|w|) as a final state of C , by an argument similar to the initial state, we obtain that there is one and only one run in A that corresponds to a given run in C .

Reduced computations and one-way automata

In unweighted (or Boolean) automata, two-way automata describe exactly the same languages as oneway automata [START_REF] Shepherdson | The reduction of two-way automata to one-way automata[END_REF][START_REF] Rabin | Finite automata and their decision problems[END_REF]. It is not always the case with weighted automata. For instance, let K be the semiring of languages of the alphabet {x, y}. It is not difficult to design a deterministic two-way Kautomaton over the alphabet {a} such that the image of a n is x n y n (a first left-right traversal outputs an x for each a, then the automaton comes back to the beginning of the word and a second left-right traversal outputs a y for each a). This function is obviously not rational and can not be realized by a one-way K-automaton. Proposition 4. Let K be a commutative semiring and let A be a δ -local two-way K-automaton. There exists a (finite) one-way K-automaton B such that there is a bijection ϕ between the reduced computations of A and the computations of B such that, for every reduced computation ρ of A , -ρ and ϕ(ρ) have the same label and the same weight; -the signature of ρ is the sequence of states of ϕ(ρ).

Proof. Let A = (Q, A, E, I, T ) be a two-way K-automaton. We consider vectors of elements of Q such that no state of Q appears twice at positions with the same parity. For all k in N, we set

V k ={v ∈ Q 2k+1 | v i = v j ⇒ i = j mod 2} ={v ∈ Q 2k+1 | ∀p ∈ Q, ∀s ∈ [0; 1], |{i | v i = p and i = s mod 2}| 1} (6)
For every k larger than |Q| -1, V k is empty. Let V = k V k ; we define the one-way K-automaton with set of states V . It is straightforward that a run is reduced if and only if every slice of this run is in V . By Proposition 3, the restriction of the slice automaton to V gives a finite automaton that fulfils the proposition.

Actually, the sufficient condition for the finiteness of the trim part of the slice automaton can be weaken. If the number of slices of a two-way automaton is finite, it is equivalent to a one-way automaton. Unfortunately, this condition is not easy to check and is not a necessary condition. Example 6. The two-way Q-automaton A 2 computes for each word w over the alphabet {0, 1} the value x 1-x , where x = ∑ i∈ [1;|w|] w i 2 i . Although Q is commutative, this two-way automaton is not equivalent to any one-way Q-automaton; s 2 = |A 2 | is not a rational series.

On Determinism and Unambiguity of Weighted Two-way Automata Example 7. Let B ′ 1 be the trim part of the slice automaton of A ′ 1 (Figure 5). In this particular case, although A 1 is not δ -local, the slice automaton B 1 of A 1 (Figure 6) is also unambiguous. It has been shown in [START_REF] Klimann | Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton[END_REF] that there is no deterministic one-way distance automaton equivalent to these automata.

p q + p s + q + p s - q + q + r p q - r p b | 0 a | 0 a | 0 b | 0 a | 1 a | 1 b | 0 a | 1 a | 1 a | 1 b | 0
p q p s q q r p b | 0 a | 0 a | 0 b | 0 a | 1 a | 1 b | 0

Unambiguity and Determinism

Since every computation in an unambiguous two-way automaton is reduced, Proposition 4 implies the following statement.

Proposition 5. Let K be a commutative semiring. Every unambiguous two-way K-automaton is equivalent to an unambiguous one-way K-automaton.

A unambiguous one-way automaton can obviously be seen as a unambiguous two-way automaton. In this part, we show that an unambiguous one-way automaton can actually be converted into a determinstic two-way automaton.

From Unambiguous one-way to Deterministic two-way Automata Definition 9. A two-way automaton is deterministic if i) it has at most one initial state;

ii) for every state p and every letter a, there is at most one transition outgoing from p with label a; iii) for every final state p, there is no transition outgoing from p with label ⊣.

The last condition means that if a final state is reached at the end of the word, there is no nondeterministic choice between ending the computation and reading the right mark to continue. Theorem 1. Let K be a semiring. Every unambiguous one-way K-automaton is equivalent to a deterministic two-way K-automaton.

This result is an extension of [START_REF] Hopcroft | An Approach to a Unified Theory of Automata[END_REF], where it is proved that an unambiguous one-way automaton can be simulated by a deterministic two-way automaton. Our proof is inspired by [START_REF] Carton | Two-Way Transducers with a Two-Way Output Tape[END_REF], where it is proven that any rational function can be realized by a sequential two-way transducer. Other works on the conversion of two-way transducers to one-way transducers can be found in [START_REF] Engelfriet | Finitary Compositions of Twoway Finite-State Transductions[END_REF] or in [START_REF] Souza | Uniformisation of Two-Way Transducers[END_REF].

Proof. Let A = (I, E, T ) an unambiguous one-way K-automaton with set of states Q.

We consider the mapping µ from A into the Q × Q Boolean matrices defined by:

∀a ∈ A, ∀p, q ∈ Q, µ(a) p,q = 1 ⇐⇒ (p, a, q) ∈ E. ( 7
)
The monoid generated by {µ(a) | a ∈ A} is the transition monoid M of A . The mapping µ is naturally extended to a morphism of the monoid A * onto M. Every subset of Q can be interpreted as a vector in B Q ; for every word w, Iµ(w) is the set of states accessible from an initial state by a path with label w and conversely, µ(w)T is the set of states from which a terminal state can be reached by a path with label w. Since A is unambiguous, for every pair of words (u, v), Iµ(u) ∩ µ(v)T has at most one element (otherwise there would exist several computations accepting uv); likewise, for every letter, there exists at most one transition (p, a, q) in A with p in Iµ(u) and q in µ(v)T (otherwise there would exist several computations accepting uav).

For every word w = w 1 . . . w k , for every i in [0; k], we set

X i (w) = Iµ(w 1 . . . w i ) and Y i (w) = µ(w i+1 . . . w k )T .
We build a deterministic two-way K-automaton B equivalent to A . B has the following property. If w is accepted by B, for every i in [1; k], the state reached after the last reading of w i contains the information (X i (w),Y i (w)):

X0,Y0 X1,Y1 Xk,Yk ⊢ w 1 w k From (X i-1 (w),Y i-1 (w)
) and (X i (w),Y i (w)), the transition labeled by w i in the run with label w can be deduced: it is the only transition (p, w i , q) with p in X i-1 (w) and q in Y i (w). Likewise (X 0 ,Y 0 ) determines the initial weight and (X k ,Y k ) determines the final weight.

The set X i can easily be deduced from X i-1 :

X i = X i-1 µ(w i ). the computation of Y i from Y i-1 is more subtle.
Let x and y be two elements of M. If there exists z in M such that x = zy, we say that x L y; this relation is a preorder. If there also exists t such that tx = y, we say that x and y are L-equivalent.

Let u be a factor of w that starts in w i+1 . It obviously holds µ(w i u) L µ(u). If µ(w i u) and µ(u) are L-equivalent, there exists y in M such that yµ(w i u) = µ(u). In this case, it also holds yµ(w i . . . w k ) = µ(w i+1 . . . w k ) and therefore, Y i = yY i-1 . The two-way automaton can perform these computations, since they lie in the transition monoid, which is finite. The automaton incrementally computes for each j in [i; k] the value of µ(w i+1 . . . w j ) until µ(w i . . . w j ) < L µ(w i+1 . . . w j ) and µ(w i . . . w j+1 ) ≡ L µ(w i+1 . . . w j+1 ). If it reaches j = k, then Y i = µ(w i+1 . . . w j )T , otherwise, Y i = yY i-1 where y is such that yµ(w i . . . w j+1 ) = µ(w i+1 . . . w j+1 ).

Once Y i is computed, the automaton must come back to position i. The automaton is in some position j such that µ(w i . . . w j ) < L µ(w i+1 . . . w j ); a fortiori, for every r in [i + 1; j], µ(w i . . . w j ) < L µ(w r . . . w j ). The automaton therefore spans every position smaller than j until it arrives to some point s such that µ(w i . . . w j ) = µ(w s . . . w j ). It then holds s = i.

Let P be the powerset of Q. The set of states of B is the union of five kinds of states: -Q 0 = {i} is the initial state; in this state, the automaton read the input from left to right until it reached the right mark ⊣. It then goes to the state T in Q 1 .

-Q 1 ⊆ P; in this state, the automaton read the input w from right to left; after reading the suffix v, the state corresponds to µ(v)T . When the left mark ⊢ is reached, the automaton goes to the state (I, µ(w)T ) in Q 2 .

-Q 2 ⊆ P 2 ; these states corresponds to the pairs (X i ,Y i ); the incoming transitions on these states correspond to the transition of the one-way automaton; they are weighted by the corresponding weight. Likewise, a state in Q 2 may be terminal if it belongs to P × {T }. When the automaton is in one of these states, either it stops, or it starts to deal with a new letter; this letter is read and stored in the next state which belongs to Q 3 .

-Q 3 ⊆ A × M × P 2 ; the automaton stays in states Q 3 as long as it needs to compute Y i from Y i-1 . It stores the current letter a as well as the image in the transition monoid of the factor u that follows a and ends at the current position. If the state stores µ(u) that is L-larger than µ(au) and the read letter b is such that µ(aub) and µ(ub) are L-equivalent, there exists y such that yµ(aub) = µ(ub); then Y i = yY i-1 , the automaton stores µ(au) and jump to a state in Q 4 .

-Q 4 ⊆ M 2 × P 2 ; the automaton stays in a state of Q 4 while it reads from right to left the word u; it stores the image of the suffix v of u which is read; it holds µ(v) > L µ(au) until v = u; at this point, the automaton read the letter a and checks that µ(av) = µ(au); at this point, it knows both X i and Y i+1 , therefore, it can output the weigth of the unique transition compatible with a, X i and Y i+1 , and jump to the state (X i+1 = X i µ(a),Y i+1 ).

F = {i a,→ ---→ i ∈ Q 0 | a ∈ A} ∪ {i ⊣,← ---→ T ∈ Q 1 } ∪ {Y a,← ---→ µ(a)Y ∈ Q 1 | Y ∈ Q 1 , a ∈ A} ∪ {Y ⊢,→|I k ----→ (I,Y ) ∈ Q 2 | Y ∈ Q 1 , k ∈ I ∩Y } ∪ {(X ,Y ) a,→ ---→ (a, 1 K , X ,Y ) ∈ Q 3 | (X ,Y ) ∈ Q 2 , a ∈ A} ∪ {(a, x, X ,Y ) b,→ ---→ (a, xµ(b), X ,Y ) ∈ Q 3 | (a, x, X ,Y ) ∈ Q 3 , b ∈ A, µ(a)xµ(b) < L xµ(b)} ∪ {(a, x, X ,Y ) b,← ---→ (µ(a)x, 1, X , yY ) ∈ Q 4 | (a, x, X ,Y ) ∈ Q 3 , b ∈ A, y ∈ M, yµ(a)xµ(b) = xµ(b)} ∪ {(a, x, X ,Y ) ⊣,← ---→ (µ(a)x, 1, X , T ) ∈ Q 4 | (a, x, X ,Y ) ∈ Q 3 } ∪ {(x, y, X ,Y ) a,← ---→ (x, µ(a)y, X ,Y ) ∈ Q 4 | (x, y, X ,Y ) ∈ Q 4 , a ∈ A, x < L µ(a)y} ∪ {(x, y, X ,Y ) a,→|k ----→ (X µ(a),Y ) ∈ Q 2 | (x, y, X ,Y ) ∈ Q 4 , a ∈ A, x = µ(a)y, ∃(p, q) ∈ X ×Y, ∃p a|k --→ q ∈ A }.
For every X in P, if the state (X , T ) belongs to Q 2 , (X , T ) is final with weight T p , where p is the unique state in X ∩ T . Example 8. Let B 1 be the unambiguous one-way automaton of Figure 6. We number the states of this automaton: [p] = 1, [q] = 2, [p, s, q] = 3 and [q, r, p] = 4. The transition monoid is generated by the following matrices:

α = µ(a) =     0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0     , β = µ(b) =     1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0     . ( 8
)
The following identities hold : α 2 = 1, β 2 = β , β αβ = β . It then holds 1 ≡ L α, αβ ≡ L β and αβ α ≡ L β α, while β < L 1 and β α < L 1. Notice that β and β α are uncomparable. We can apply the proof of Theorem 1 to compute the equivalent deterministic two-way automaton D 1 of Figure 7.

Corollary 1. Let K be a commutative semiring. Every unambiguous two-way K-automaton is equivalent to a deterministic one.

Remark 1. This conversion can lead to a combinatorial blow-up. For instance, the deterministic twoway automaton built from the unambiguous one-way automato B 1 (Figure 6 (right)) has 27 states in its trim part.

A lower bound on the number of states can be computed. Let n be the number of states of the unambiguous one-way automaton.

• Q 0 has one state;

• Q 1 has at most 2 n -1 states;

• Q 2 is made of pairs of subset of Q which share exactly one element, hence Q 2 has at most n3 n-1 states;

• Q 3 is made of a pair of Q 2 endowed with a letter and an element of the transition monoid (that may have 2 n 2 elements); hence Q 3 has at most |A|n3 n-1 2 n 2 states;

• Q 4 is made of two (non empty) subsets of Q and two elements of the transition monoid; its size is bounded by 2 2n+2n 2 . i a, → b, → a, → a, →

β α, 1, 1 3 , 2 3
b, ←

β α, α, 1 3 , 2 3
a, ← a, ←

Figure 1 :

 1 Figure 1: The two-way N -automaton A 1 .

Figure 2 :

 2 Figure 2: A run of A 1 over the word abaaba.

Figure 3 :

 3 Figure 3: The δ -local two-way distance automaton A ′ 1 .

Figure 5 :

 5 Figure 5: The unambiguous one-way distance automata B 1 .

Figure 6 :

 6 Figure 6: The unambiguous one-way distance automata B 1 .

Figure 7 :

 7 Figure 7: The deterministic two-way distance automaton D 1 . The transitions or states in gray are not accessible. For sake of clearness, transitions outgoing from non accessible states are not drawn. Every column of numbers is the set of non-zero components of a Boolean vector of size 4. The weights are only written on transitions where it comes from the weight of a transition (or from an initial/final weight) of B 1 .