Bruno Guillon
email: bruno.guillon@uca.fr

Giovanni Pighizzini
email: pighizzini@di.unimi.it

Luca Prigioniero
email: prigioniero@di.unimi.it

Daniel Průša

Daniel Pr•²a

Converting nondeterministic two-way automata into small deterministic linear-time machines

Keywords: one-tape Turing machines, two-way automata, descriptional complexity, Sakoda-Sipser conjecture

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

One-way deterministic nite automata (1dfas) are the canonical acceptor for the class of regular languages. If one allows nondeterministic transitions (1nfas) or/and movements of the head in both directions on the input tape, so obtaining two-way deterministic and nondeterministic nite automata (2dfas/2nfas), the computational power does not increase [START_REF] Rabin | Finite automata and their decision problems[END_REF][START_REF] Shepherdson | The Reduction of Two-Way Automata to One-Way Automata[END_REF].

Other extensions of nite automata have been proved to capture the same class of languages, such as constant-height pushdown automata [START_REF] Geert | More concise representation of regular languages by automata and regular expressions[END_REF][START_REF] Guillon | Non-self-embedding grammars, constant-height pushdown automata, and limited automata[END_REF], straightline programs [START_REF] Geert | More concise representation of regular languages by automata and regular expressions[END_REF], 1-limited automata [START_REF] Wagner | Computational Complexity[END_REF][START_REF] Pighizzini | Limited Automata and Regular Languages[END_REF][START_REF] Pighizzini | Limited automata and unary languages[END_REF], or, as will be of interest for this work, linear-time one-tape Turing machines [START_REF] Pr•²a | Weight-reducing Hennie machines and their descriptional complexity[END_REF][START_REF] Guillon | Two-way automata and one-tape machines -read only versus linear time[END_REF][START_REF] Hennie | One-tape, o-line Turing machine computations[END_REF][START_REF] Guillon | Weight-reducing Turing machines[END_REF]. 3 A natural question concerning models that share the same computational power is the comparison of the sizes of their descriptions. In particular, the cost of the elimination of nondeterminism is a standard problem. For instance, it is a classical result that an exponential increase in size is sucient and, in the worst case, necessary for the conversion of 1nfas to 1dfas [START_REF] Rabin | Finite automata and their decision problems[END_REF]. 3 Actually, the model considered by Hennie was deterministic. Several extensions of this result, including that to the nondeterministic case and greater time lower bounds for nonregular language recognition, have been stated in the literature [START_REF] Trakhtenbrot | Turing machine computations with logarithmic delay[END_REF][START_REF] Hartmanis | Computational complexity of one-tape Turing machine computations[END_REF][START_REF] Michel | An NP-complete language accepted in linear time by a onetape Turing machine[END_REF][START_REF] Pighizzini | Nondeterministic one-tape o-line Turing machines[END_REF][START_REF] Tadaki | Theory of one-tape linear-time Turing machines[END_REF].

However, already for two-way automata, the famous Sakoda and Sipser question concerning the size blowups from 1nfas or 2nfas to 2dfas is a much more intricate problem. For both conversions, Sakoda and Sipser conjectured that the costs are exponential [START_REF] Sakoda | Nondeterminism and the size of two waynite automata[END_REF]. The question has been solved in some special cases that can be grouped in three classes: by considering restrictions on the simulating machines (e.g., sweeping [START_REF] Sipser | Lower Bounds on the Size of Sweeping Automata[END_REF], oblivious [START_REF] Hromkovic | Nondeterminism versus determinism for two-way nite automata: Generalizations of Sipser's separation[END_REF], few reversals 2dfas [START_REF] Kapoutsis | Nondeterminism is essential in small two-way nite automata with few reversals[END_REF]), by considering restrictions on languages (e.g., unary case [START_REF] Geert | Converting two-way nondeterministic unary automata into simpler automata[END_REF]), by considering restrictions on the simulated machines (e.g., outernondeterministic automata [START_REF] Geert | Two-way automata making choices only at the endmarkers[END_REF][START_REF] Kapoutsis | Two-way automata characterizations of L/poly versus NL[END_REF]). However, in spite of all attempts, in the general case the question remains open (for further references see [START_REF] Pighizzini | Two-way nite automata: Old and recent results, Fundam[END_REF]).

Here, we consider a dierent approach: in order to obtain a polynomial simulation, we enlarge the family of simulating machines. To this end, we study size blowups for the conversion of 1nfas and 2nfas into several variants of linear-time one-tape deterministic Turing machines, which all characterize regular languages. These variants and their properties have been investigated in [START_REF] Guillon | Two-way automata and one-tape machines -read only versus linear time[END_REF][START_REF] Guillon | Weight-reducing Turing machines[END_REF]. We now give a short description of them (see Figure 1).

As proven by Hennie, linear-time one-tape deterministic Turing machines recognize regular languages only [START_REF] Hennie | One-tape, o-line Turing machine computations[END_REF]. However, it cannot be decided whether or not a one-tape Turing machine actually works in linear time [START_REF] Pr•²a | Weight-reducing Hennie machines and their descriptional complexity[END_REF][START_REF] Guillon | Weight-reducing Turing machines[END_REF]. This negative result remains true in the restricted case of end-marked machines, namely one-tape deterministic Turing machines that do not have any extra space, besides the tape portion which initially contains the input. Endmarked machines working in linear time will be called deterministic Hennie machines. To overcome the above-mentioned negative results, a syntactical recurs ively enumera ble (type 0) regular (type 3) context -sensit ive (type 1) d e te rm in is ti c co n te xt -s en si ti ve weight-reducing dHms (wrdHms) deterministic Hennie machines (dHms) halting wrdTms end-marked dTms linear-time dTms weight-reducing dTms (wrdTms) one-tape deterministic Turing machines (dTms)

Figure 1: Variants of one-tape deterministic Turing machines and their expressive power confronted with the Chomsky hierarchy. In particular, end-marked dTms are known as deterministic linear bounded automata in the literature, and recognize the so-called deterministic context-sensitive languages, a subclass of context-sensitive languages, see [START_REF] Walters | Deterministic context-sensitive languages: Part II[END_REF]. It is still unknown if such inclusion is strict.

restriction on deterministic one-tape Turing machines, called weight-reducing machines, has been considered [START_REF] Pr•²a | Weight-reducing Hennie machines and their descriptional complexity[END_REF][START_REF] Guillon | Weight-reducing Turing machines[END_REF]. This restriction enforces computations to either be innite or halt within a linear number of steps in the input length.

In contrast to Hennie machines, this model benets from nice properties. In particular, it can be decided whether a one-tape Turing machine is weightreducing, and whether a weight-reducing Turing machine is halting (and hence works in linear time). Furthermore, haltingness of the model can always be obtained by paying only a polynomial size increase. However, in this model, space is not limited to the portion of the tape that contains the input at the beginning of the computation; namely the device is not end-marked.

By considering end-marked linear-time machines satisfying the syntactical restriction of weight-reducing machines, we obtain weight-reducing Hennie machines.

Our main result is that each 2nfa A can be simulated by a one-tape deterministic Turing machine that works in linear time (with respect to the input length) and which has polynomial size with respect to the size of A.

We point out that the resulting machine can use extra space, besides the tape segment which initially contains the input. Next, the machine is halting and weight-reducing, thus implying a linear execution time. Hence, nondeterminism can be eliminated with at most a polynomial size increase, obtaining a linear execution time in the input length, and provided the ability to rewrite tape cells and to use some extra space.

We then investigate what happens when the latter capability is removed, namely if the machine does not have any further tape storage, i.e., it is a Hennie machine. We prove that even under this restriction it is still possible to obtain a machine of polynomial size, that is each 2nfa can be transformed into an equivalent Hennie machine of polynomial size. However, the machine resulting from our construction is not weight reducing, unless we require that it agrees with the given 2nfa only on suciently long inputs. We do not have this problem in the unary case, namely for a one-letter input alphabet, where we prove that each unary 2nfa can be simulated by a weightreducing Hennie machine of polynomial size. Similar results are obtained for the transformation of 1nfas into variants of one-tape deterministic machines.

The paper is organized as follows. In Section 2 we present some fundamental notions and denitions, included those related to the computational models we are interested in, and we state some basic properties. In Section 3 we present our main simulation result: each n-state 2nfa can be transformed into an equivalent halting weight-reducing machine of size polynomial in n.

In Section 4 we discuss how the simulation changes if the resulting machine is required to be a Hennie machine. Finally, in Section 5 we revise the results of Sections 3 and 4 under the assumption that the simulated automata are one-way instead of being two-way.

Preliminaries

In this section we recall some basic denitions and notation. We also describe the main computational models considered in the paper and we give some preliminary results.

We assume the reader familiar with notions from formal languages and automata theory (see, e.g., [START_REF] Hopcroft | Introduction to Automata Theory, Languages and Computation[END_REF]). Given a set S, its cardinality is denoted by #S and the family of all its subsets 2 S . Given an alphabet Σ, the length of a string w ∈ Σ * is denoted by |w|, the i-th symbol of w is denoted by w i , i = 1, . . . , |w|, and the empty string is ε.

Finite automata are computational devices equipped with a nite control and a nite read-only tape which is scanned by an input head. A one-way nondeterministic nite automaton (1nfa) is dened as a quintuple A = Q, Σ, δ, q 0 , F , where Q is a nite set of states, Σ is a nite input alphabet, q 0 ∈ Q is the initial state, F ⊆ Q is a set of nal states, and δ :

Q × Σ → 2 Q is a nondeterministic transition function. At each step,
according to its current state p and the symbol σ scanned by the head, A enters one nondeterministically-chosen state from δ(p, σ) and moves the input head rightward to the next symbol. The machine accepts the input if there exists some computation starting from the initial state q 0 with the head on the leftmost input symbol and ending in a nal state q ∈ F after having read the whole input. A 1nfa A is said to be deterministic (1dfa), whenever #δ(q, σ) ≤ 1, for any q ∈ Q and σ ∈ Σ.

Providing 1nfas (resp., 1dfas) with the ability of moving the head back and forth, we obtain two-way nondeterministic (resp., deterministic) nite automata (2nfas , resp., 2dfas). They are dened by extending the transition function so that a left (-1) or right (+1) head direction is indicated in each instruction. Furthermore, to prevent the head to fall out the input, the device is end-marked, in the following sense. Two special symbols and not belonging to Σ, called the left and the right endmarker, respectively, surround each input word, and enforce the computation to stay between them (except at the end of computation when accepting, as described below). More precisely, on input w the tape contains w , the left endmarker being at position 0 and the right endmarker being at position |w| + 1. We let Σ , denote the set Σ ∪ { , }. Formally, the transition function of a two-way automaton is δ : Q × Σ , → 2 Q×{-1,+1} such that, for each transition (q, d) ∈ δ(p, σ), if σ = then d = +1, and if σ = then d = -1

or q ∈ F . In this way, the head cannot go past the endmarkers, except at the end of the computation to accept. The machine accepts the input if there exists a computation starting from the initial state q 0 with the head on the 0-th tape cell (i.e., scanning the left endmarker) and ending in a nal state q ∈ F after passing the right endmarker.

The other main computational model we consider is the deterministic one-tape Turing machine (dTm). Such a machine is a tuple Q, Σ, Γ, δ, q 0 , F where Q is the set of states, Σ is the input alphabet, Γ is the tape alphabet including both Σ and the special blank symbol, denoted by b, that cannot be written by the machine, q 0 ∈ Q is the initial state, F ⊆ Q is the set of nal states, and δ :

Q × Γ → Q × (Γ \ { b}) × {-1, +1}
is the partial deterministic transition function. In one step, depending on its current state p and on the symbol σ read by the head, a dTm changes its state to q, overwrites the corresponding tape cell with τ and moves the head one cell to the left when d = -1 or to the right when d = -1, if δ(p, σ) = (q, τ, d). Since δ is partial, it may happen that no transition can be applied. In this case, we say that the machine halts. At the beginning of computation the input string w resides on a segment of a bi-innite tape, called the initial segment, and the remaining innity of cells contain the blank symbol. The computation on input w starts in the initial state with the head scanning the leftmost nonblank symbol. The input is accepted if the machine eventually halts in a nal state.

Let A = Q, Σ, Γ, δ, q 0 , F be a dTm. A conguration of A is given by the current state, the tape contents, and the position of the head. If the head is scanning a non-blank symbol, we describe it by zqu where zu ∈ Γ * is the nite non-blank contents of the tape, u = ε, and the head is scanning the rst symbol of u. Otherwise, we describe it by q bz or zq according to whether the head is scanning the rst blank symbol to the left or to the right of the non-blank tape contents z, respectively. If, from a conguration zqu the device may enter a conguration z q u in one step, we say that z q u is a successor of zqu, denoted by zqu z q u . A halting conguration is a conguration that has no successor. The reexive and transitive closure of is denoted by * . On an input string w ∈ Σ * , the initial conguration is q 0 w.

An accepting conguration is a halting conguration zq f u such that q f is a nal state of the machine. A computation is a (possibly innite) sequence of successive congurations. It is accepting if it is nite, its rst conguration is initial, and its last conguration is accepting. Therefore, the language accepted by a machine A is the set {w ∈ Σ * | q 0 w * zq f u, where q f ∈ F and zq f u is halting}.

We say that two machines T and H agree on some language L if every string in L is accepted by T if and only if it is accepted by H.

The notions of congurations, successors, computations, and halting congurations naturally transfer to one-way and two-way nite automata.

In the paper we consider the following restrictions of dTms.

End-marked machines. We say that a dTm is end-marked if at the beginning of the computation the input string is surrounded by two special symbols belonging to Γ, and respectively, called the left and the right endmarkers, which can never be overwritten, and that prevent the head to fall out the tape portion that initially contains the input.

Formally, for each transition δ(p, σ) = (q, τ, d), σ = (resp., σ = ) implies τ = σ and d = +1 (resp., d = -1). This is the deterministic restriction of the well-known linear-bounded automata [START_REF] Kuroda | Classes of languages and linear-bounded automata[END_REF]. For end-marked machines, the initial conguration on input w is q 0 w . Weight-reducing Turing machines. A dTm is weight-reducing (wr dTm), if there exists a partial order < on Γ such that each rewriting is decreasing, i.e., δ(p, σ) = (q, τ, d) implies τ < σ. By this condition, in a wrdTm the number of visits to each tape cell is bounded by a constant. However, one wrdTm could have non-halting computations which, hence, necessarily visit innitely many tape cells.

Linear-time Turing machines. A dTm is said to be linear-time if over each input w, its computation halts within O(|w|) steps.

Halting weight-reducing machines. These machines are wrdTm that work in linear time, and hence are necessarily halting.

Hennie machines. A Hennie machine (dHm) is a linear-time dTm which is, in addition, end-marked.

Weight-reducing Hennie machines. By combining previous conditions, weight-reducing Hennie machines (wr dHm) are dened as particular dHm for which there exists an order < over Γ \ { , } such that δ(p, σ) = (q, τ, d) implies τ < σ unless σ ∈ { , }. Observe that each end-marked wrdTm can execute a number of steps that is at most linear in the length of the input. Hence, end-marked wrdTm are necessarily weight-reducing Hennie machines.

The size of a machine is given by the total number of symbols used to write down its description. Therefore, the size of a one-tape Turing machine is bounded by a polynomial in the number of states and of tape symbols;

namely, it is Θ(#Q • #Γ • log(#Q • #Γ)).
In the case of nondeterministic (resp., deterministic) nite automata, since no writing to the tape is allowed and hence the work alphabet is not provided, the size is linear in the number of instructions and states, which is bounded by a function quadratic (resp., subquadratic) in the number of states and linear in the number of input symbols; namely, it is

Θ(#Σ • #Q 2 ) (resp., Θ(#Σ • #Q • log(#Q))).
We now state two preliminary results that will be used in the subsequent sections for building weight-reducing Turing machines and weight-reducing Hennie machines, respectively.

It is known that a dTm works in linear time only if there exists a constant k such that in no computation the head visits each tape cell more than k times [10, Proof of Theorem 3]. The following lemma states that, given a dTm that visits each tape cell at most k times, a weight-reducing Turing machine can be obtained, augmenting linearly the work alphabet only. Indeed, we can enforce the machine to store on each tape cell the number of further visits the head is allowed to perform on the cell. As this number decreases, the overwriting is decreasing. Using k copies of each tape symbol is enough to implement this. Therefore, in order to dene a wrdTm, it is sucient to dene a dTm and to provide a constant k bounding the number of visits to each tape cell. Lemma 1 ([11]). Let T = Q, Σ, Γ, δ, q 0 , F be a dTm such that, for any input, T performs at most k computation steps on each tape cell. Then there is a wr dTm A equivalent to T with the same set of states Q as T and tape alphabet of size O(k •#Γ). Furthermore, on each input A uses the same space as T . Hence, if T is linear time or end-marked then so is A.

Weight-reducing Turing machines extend weight-reducing Hennie machines by allowing the use of some extra space besides the portion that initially contains the input. Indeed, the former model can use a bi-innite tape while the latter is end-marked. However, it has been shown that every nite computation of a wrTm uses an amount of this extra space which is bounded by a constant in the input length [START_REF] Guillon | Weight-reducing Turing machines[END_REF]. We do not know whether the use of this extra space can be avoided in general, while keeping the weight-reducing property and bounding the size increase by a polynomial. Nevertheless, this can be achieved when the inputs are long enough. Lemma 2. Let T be a weight-reducing Turing machine which uses at most C initially-blank cells in every halting computation. Then there exists a weightreducing Hennie machine H of size polynomial in the size of T that agrees with T on every input of length at least C.

Proof. The idea of the proof is the same as the folklore simulation of Turing machines working on a bi-innite tape by Turing machines working on a semiinnite tape. Indeed, we fold the portion of the tape occurring to the left of the initial segment onto the complementary portion of the tape, thus creating a second track. Similarly, we can fold the portion of the tape occurring to the right of the initial segment onto the complementary portion of the tape.

Next, as T uses at most C initially-blank cells in total, and providing the input has length at least C, we observe that the additional tracks do not overlap hence only one additional track is sucient for the simulation. On shorter inputs, the simulation could fail giving an outcome dierent from those of T . Doing so, we obtain a dHm H that uses twice the number of states of T (two copies of each state of T for indicating which track should be read), and the work alphabet Γ H = Γ ∪ Γ 2 where Γ is the work alphabet of T . In particular, the size of H is polynomial in the size of T . Finally, we can extend the order < T on Γ witnessing that T is weight-reducing, to an order < H on Γ H witnessing that H is weight-reducing.

Simulating Two-way Automata by Weight-reducing Machines

This section is devoted to present our main simulation: we show that every 2nfa A = Q, Σ, δ, q 0 , F can be transformed into an equivalent wrdTm of size polynomial in the size of A. Let n = #Q. Our construction is based on the classical simulation of 2nfas by 1dfas, inspired from Shepherdson's construction [START_REF] Shepherdson | The Reduction of Two-Way Automata to One-Way Automata[END_REF]. The main idea is to perform forward moves, while updating a table of size n 2 that describes parts of computations which may occur to the left of the current position. In parallel, an adaptation of the classical powerset construction for converting 1nfas into 1dfas is done, in such a way that the set of states that are accessible from the initial conguration when visiting for the rst time the current head position is updated at each move. In the simulation by 1dfas, the table and the set are stored on the nite state control. In our simulation by wrdTms they will be written, under a suitable encoding, in O(n 2 ) many tape cells.

To describe computation paths that occur on some restricted part of the tape, we dene partial congurations, by relaxing the denition of congurations, as strings xqy where q is a state and xy ∈ { , ε}

• Σ * • { ,
τ zX = {(p, q) ∈ Q × Q | zpX * zXq }, and
γ zX = {r ∈ Q | q 0 zX * zXr }.
Observe that a word w ∈ Σ * is accepted by A if and only if F ∩ γ w = ∅.

In order to simulate A on input w, it is thus sucient to incrementally compute γ z for each prex z of w . To do so, we will keep the table τ z updated as well. Indeed, given γ z , τ z and a symbol σ, it is possible to compute γ zσ and τ zσ . This is achieved by observing that (see Figure 2):

1. (p, q) ∈ τ zσ if and only if there exists a sequence r 0 , s 0 , r 1 , s 1 , . . . , r ∈ Q, with ≥ 0, satisfying:

r 0 = p,
(q, +1) ∈ δ(r , σ), and

X σ z r 0 s 0 r 1 s 1 r q • • •
Figure 2: A computation path from p = r 0 to q giving (p, q) ∈ τ zσ . For each i, (s i , r i+1 ) ∈ τ z and (s i , -1) ∈ δ(r i , σ), while (q, +1) ∈ δ(r , σ).

(s i , -1) ∈ δ(r i , σ) and (s i , r i+1 ) ∈ τ z , for i = 0, . . . , -1.

2. q ∈ γ zσ if and only if there exists p ∈ γ z such that (p, q) ∈ τ zσ .

We represent a pair (γ z , τ z ) as a word uv in {0, 1} * with |u| = n and |v| = n 2 .

Each bit of u (resp., v) indicates the membership of some state p (resp., some pair (p, q) of states) to the set γ z (resp., τ z ) through an implicitly xed bijection from Q to {1, . . . , n} (resp., from Q 2 to {1, . . . , n 2 }). For each input symbol σ, there exists a halting dHm T σ which computes (γ zσ , τ zσ ) from (γ z , τ z )

in the following sense. On input uv ∈ {0, 1} n+n 2 encoding (γ z , τ z ), T σ ends the computation with the tape containing the encoding u v ∈ {0, 1} n+n 2 of (γ zσ , τ zσ ). Notice that this computation does not depend on the entire z, which, indeed, is not given to T σ , but only on the information about z stored in γ z and τ z which are given in the input.

Lemma 3. For each σ ∈ Σ ∪ { }, there exists a halting dHm T σ with O(n 6 ) states and O(1) tape symbols that on input (γ z , τ z ) halts with the tape containing (γ zσ , τ zσ ) after O(n 5 ) visits to each cell. The input and the output are represented on the tape as strings in {0, 1} n+n 2 .

Proof. Fix σ, and let uv be the input string encoding the pair of tables (γ z , τ z ), of size n and n 2 respectively. In order to update them, T σ uses a second track on the tape, on which it will progressively build the updated tables. At the end of the computation, namely when the updated tables have been determined and written down the second track, the device performs a projection of the tape on its second track, in order to produce the correct output, and halts.

We x the work alphabet Γ = {0, 1} ∪ {0, 1} 2 . The simple symbols from {0, 1} are used only for the input and the output of T σ . From now on, we suppose that the tape contains only symbols from the 2-track alphabet part, i.e., the right side of the union. Moreover, since the length of the input is xed and it is n + n 2 , we can suppose that T σ keeps updated a state component of size n + n 2 which always stores the position of its head on the tape. This allows it to navigate over the tables.

We divide the tape into two parts: a prex u of length n (thus covering the factor u which encodes γ z on its rst track) and a sux v of length n 2

(thus covering the factor v which encodes τ z on its rst track). As previously explained, the updated table γ zσ can easily be obtained once the updated table τ zσ has been computed. Hence, we rst show how to write the table τ zσ on the second track of v. This is achieved using the space n available on the second track of u as temporary memory, to which we refer as temporary table.

As observed above (see Figure 2), a computation path on the segment containing zσ starting from the rightmost position of the segment and exiting the segment to the right at its last step, i.e., a computation of the form zpσ * zσq, can be decomposed into an alternation of computation paths on the segment containing z (described by the table τ z ) and of backward computation steps on σ connecting these paths, followed by a last forward computation step on σ that exits the segment. For each state p, in order to decide which pairs (p, q) belong to τ zσ , the machine T σ rst computes the set Z p of states that are reachable at the rightmost position of the segment containing zσ, from the state p at the same position, by visiting only cells from the segment, i.e.,

Z p = {r | zpσ * zrσ}.
Thus, a pair (p, q) belongs to τ zσ if and only if for some r ∈ Z p , we have (q, +1) ∈ δ(r, σ). For a xed p, T σ can incrementally construct Z p on the temporary table as follows. Initially, all the cells from the table are unmarked (i.e., contain 0) except the one corresponding to state p which contains 1.

The update process behaves as follows: for each state r corresponding to a marked cell, each state s such that (s, -1) ∈ δ(r, σ), and each state r such that (s, r ) ∈ τ z , the machine marks the cell corresponding to r with 1 in the temporary table. Since Z p has size bounded by n, after at most n passes, the temporary table is not modied any longer and contains exactly an encoding of Z p .

So done, computing the set Z p uses only a polynomial number of states in n. This is however not sucient to get a weight-reducing machine of polynomial size. To this end, using Lemma 1, we should indeed prove that the number of visits to each cell is bounded by some polynomial in n. To update Z p , three nested loops on states, namely on r, s, and r , are used.

Once such a triple is xed, the machine navigates on the tape in order to check that r is currently marked in the temporary table, and (s, r ) ∈ τ z (notice that the condition (s, -1) ∈ δ(r, σ) is veried in constant time, since σ is xed). These two conditions require reading the corresponding cells in the temporary table (on u) and in the table τ z (on v), respectively. This can be performed by visiting each tape cell at most twice. Marking the cell corresponding to r also implies scanning the tape part u twice. As the operation is repeated for each triple, we obtain that the number of visits to each cell in a pass for updating Z p is O(n 3 ). Since the number of passes is at most n, the total number of visits to each cell is O(n 4 ). Moreover, this operation can be implemented by using O(n 3 ) states because we just need to remember the values of r, s, and r , but not the number of the pass: it is sucient to use a bit to remember if during the last pass at least one state has been added to Z p . This is because if no states are added during a pass, then no states will be added when executing further iterations.

Once Z p has been computed, for each state r corresponding to a marked cell in the temporary table, and each state q such that (q, +1) ∈ δ(r, σ), the dHm adds the pair (p, q) to the table τ zσ represented on the second track of v. This requires visiting each tape cell O(n) times and can be performed using only a quadratic number of states in n.

Hence, the total number of states used to add pairs (p, q) to the table τ zσ , for a xed state p, is O(n 3 ), without taking into account the state component which stores the head position, while the number of visits to each tape cell is O(n 4 ).

By repeating this for each state p, we manage to update the table from τ z to τ zσ . This multiplies the number of states and the number of visits to each tape cell by a linear factor in n. Finally, we can update the table γ z . As observed before, it is sucient to consider whether (p, q) ∈ τ zσ for some p ∈ γ z for each state q. This last step requires only a quadratic number of states and a linear number of visits to each cell. Combining the above-described subroutines, and taking into account that the state component which stores the head position has size O(n 2 ), we obtain a dHm with O(n 6 ) states and O(1

)
tape symbols, whose number of visits to each tape cell is in O(n 5 ).

We are now ready to state our main simulation.

Theorem 1. Every n-state 2nfa can be transformed into an equivalent halting wr dTm with O(n 6 ) states and O(1) tape symbols.

Proof. Let A = Q, Σ, δ, q 0 , F be a 2nfa. We build a deterministic Turing machine that mimics the simulation of A by a 1dfa: after reading any prex z of an input w, the machine stores the tables γ z and τ z and checks the existence of a nal state in γ w . The tables are stored on a suitable tape track and updated each time a further input symbol is read, using the method presented in Lemma 3. This can be achieved by switching between two tape tracks at each update of the tables. However, as the number of updates is linear in the length of the input, storing and updating the tables on a xed part of length n + n 2 of the tape would lead to a non-weightreducing Turing machine. To handle this issue, for each prex z of w, we store the tables γ z and τ z on the n + n 2 cells that precede the last position of z. (Remember that, in a wrdTm, some initially-blank cells to the left of the initial segment are available.) Thus, at each update of the tables made according to Lemma 3, the tables are shifted one cell to the right. Hence, since a xed cell may occur in n + n 2 successive stored tables, the number of visits to each cell is in O(n 7 ), and the number of states is in O(n 6 ). We thus obtain a halting weight-reducing Turing machine equivalent to A whose size is polynomial in the size of A by Lemma 1. Furthermore, the machine uses only n + n 2 initially-blank cells that are all to the left of the initial segment.

Simulating Two-way Automata by Hennie Machines

In Section 3 we provided a polynomial-size conversion from 2nfas to wrdTms. The resulting machines use additional tape cells, besides the initial segment. In this section we study how to make such a simulation when the use of such extra space is not allowed; namely when we want to obtain a deterministic Hennie machine. We show that a polynomial conversion still exists, but we are not able to guarantee that the resulting machine is weight reducing. Actually this issue is related to short inputs, namely to strings of length less than n 2 , where n is the number of states of the given 2nfa.

For such inputs we do not have enough tape space to perform the simulation in Theorem 1. We will deal with them by using a dierent technique.

Let us start by considering acceptance of long inputs.

Theorem 2. For each n-state 2nfa A, there exists a wr dHm H with O(n 6 ) states and O(1) tape symbols that agrees with A on strings of length at

least n 2 .
Proof. The technique used in the proof of Theorem 1 can be exploited, with slight modications. Indeed, when recovering the tables corresponding to the short prexes z's of the tape content, the wrdTm machine resulting from the above construction uses up to n + n 2 initially-blank cells to the left of the initial segment, that are not any longer available with a wrdHm. By folding n of these cells on an additional track, as in the proof of Lemma 2, we can reduce this space amount to n 2 cells by a polynomial size increasing.

Hence, applying Lemma 2, we can obtain a wrdHm which agrees with the original machine on inputs of length at least n 2 .

In the case of unary 2nfas, namely working on a single-letter input alphabet, the number of short inputs that are not handled by Theorem 2 is n 2 .

They can be managed in a read-only preliminary phase that uses O(n 2 )

states.

Theorem 3. Every n-state unary 2nfa is equivalent to a wr dHm with O(n 6 ) states and O(1) tape symbols.

Proof. We simulate a given unary 2nfa A as follows. Let X be the nite set {i < n 2 | i = |w| for some w ∈ L}. First, the head of our simulating wrdHm is moved to the right to test whether the input is shorter than n 2 , using a counter from 0 to n 2 -1. In this case, the machine accepts if and only if the counter value belongs to X. Otherwise, the head is moved back to the left endmarker and the simulation from Theorem 2 is performed. With respect to the wrdTm obtained from Theorem 2, our device uses O(n 2 ) additional states and O(1) extra tape symbols. Hence, our construction yields a wrdHm equivalent to A of size polynomial in n.

In the nonunary case, since the number of short strings is exponential in n, we cannot apply the same technique as in Theorem 3. However, we of T (Line 1). Otherwise, if T = 0 but (p, i) = (q, j), then the function returns false (Line 2), while, if T = 1, the function returns true if there is a suitable edge in G (Line 4). In order to verify that, H saves (q, i) and (p, j)

in its internal state and then, if the distance between i and j is 1, it moves its head to position i, reads the symbol w i , and checks (q, j -i) ∈ δ(p, w i ).

Notice that this read-only process uses only a number of states polynomial in n.

In the recursive case, for checking if there exists a path in the graph from (p, i) to (q, j) of length at most T > 1, H veries whether there exists a node (r, ) ∈ Q × {0, . . . , m + 1} such that there is a path from (p, i) to (r, )

of length at most T 2 and a path from (r, ) to (q, j) of length at most T 2 (Lines 6 to 8). This is done by trying all possible nodes (r, ) until nding one satisfying these conditions. If it does not exist, then the procedure returns false (Line 9).

Recursive calls to the function reachable can be naturally saved on a pushdown store. More precisely, at the beginning of the simulation the store is empty. When a call to reachable(p, i, q, j, T ) is performed, the activation record, consisting of the parameters p, i, q, j, and T , is pushed on the top of the pushdown. Similarly, when reachable returns, the activation record of the last call is popped o. The function reachable uses seven variables, ve of them being arguments saved on the pushdown store, and two being the local variables r and . As these two local variables are arguments of inner recursive calls, their values can be recovered when popping o the inner activation record (after the corresponding call has returned). Hence, the state components saving r and are freed at each recursive call. Therefore, all the checks performed by reachable can be done with a number of states that is polynomial in n, and using the pushdown alphabet (Q × {0, . . . , n 2 }) 2 × {0, . . . , K} of size polynomial in n. We can observe that, at the beginning of the computation, we could call reachable(q 0 , 0, q f , m + 2, 2 log K ) instead of reachable(q 0 , 0, q f , m + 2, K). In this way, in each recursive call the last argument is a power of 2. This allows to reduce the number of dierent values that the last argument can get to log K + 1. Actually, it is not necessary to explicitly write down this argument: it can be computed and saved in the nite control, at the beginning of each call of reachable, by counting the number of active recursive calls (i.e., the height of the stack of recursion calls).

Finally, notice that the maximum recursion depth is log K = O(log n).

The stack of recursion calls can be stored in a separate track on log n tape cells, by using standard space compression techniques, which only induce a polynomial-size increase of the work alphabet. Since the input length m is larger than log n, the simulating Hennie machine H has enough space in its initial segment. The number of visits to each cell is super-polynomial in n, and hence the machine is not weight-reducing. However, because the input lengths are bounded by n 2 , the number of visits to each cell is bounded by a number which only depends on n.

Considering also how the machine works on inputs of length at least n 2 , this allows us to conclude that the working time of the whole machine H is linear in the input length.

It is natural to ask if Theorem 4 can be improved in order to obtain from a given 2nfa A an equivalent wrdHm of polynomial size. In the light of Theorem 2, to do that it will be enough to obtain a wrdHm of polynomial size which agrees with the 2nfa on short inputs. With this respect, we point out that the problem of Sakoda and Sipser seems to be hard even when restricted to strings of length polynomial in the number of states of A [START_REF] Kapoutsis | Two-way automata versus logarithmic space[END_REF].

The One-Way Case

In this section we restrict our attention to one-way automata simulations.

A natural question is to ask if in the case of 1nfas results stronger than those presented in Section 4 can be achieved. A simulation of 1nfas by wrdHms was studied in [1, Theorem 11], claiming that each n-state 1nfa A has an equivalent wrdHm H of size polynomial in n. Unfortunately, the presented proof is incorrect as it casts the problem of A acceptance as the problem of reachability in an undirected computation graph. Existence of a path connecting the initial and an accepting conguration in such a graph does not guarantee the existence of an accepting computation of A since the path can include back edges.

By revising [START_REF] Pr•²a | Weight-reducing Hennie machines and their descriptional complexity[END_REF]Theorem 11], we prove two weakened variants of this result.

In the rst one, the simulation holds only for suciently long inputs. The improvement with respect to Theorem 2 is that, in this case, short inputs are the strings of length less than n rather than n 2 . In the second variant, we show that each 1nfa can be simulated by a deterministic Hennie machine which, however, is not weight-reducing.

Let us start by presenting the weight-reducing simulation for long inputs.

In particular, γ ε is the singleton {q 0 } and an input w is accepted by A if and only if γ w ∩ F is nonempty. In order to store any subset γ z of Q on the tape, we represent it as a word u ∈ {0, 1} n , in which u i is 1 if and only if q i ∈ γ z . Ranging over input prexes, T iteratively computes γ zσ from γ z , where σ ∈ Σ is the (|z| + 1)-th input symbol. To avoid erasing γ z when writing down γ zσ , T uses two distinct tape tracks: γ z is read from the rst track and γ zσ is written on the second one (shifted by one cell to the right with respect to γ z ). The role of the two tracks is inverted after each such update.

At the beginning of the computation, T writes γ ε on the n cells preceding the initial segment (on one track, suppose the rst one for ease of exposition).

During the simulation, when T reaches a position for the rst time, the n tape cells preceding that position will contain the encoding of γ z (on the rst track) where z is the input prex read so far. From such a point, T is able to compute γ zσ , working on the tape portion of length n + 1 that contains both γ z and the current position containing σ, and to which we refer as the current working segment. Indeed, for each q i ∈ Q, we have q i ∈ γ zσ if and only if q i ∈ δ(q j , σ) for some q j ∈ γ z . Since T can test for each q i , q j ∈ Q whether, on the one hand, q j belongs to γ z (by visiting the j-th cell of the current working segment which stores the j-th bit of γ z on the rst track), and, on the other hand, q i ∈ δ(q j , σ) (by inspecting the transition table of A),

it can write γ zσ on the tape. More precisely, when the two conditions above are satised, T writes 1 on the (i + 1)-th cell of the current working segment (on the second track), for storing the i-th bit of γ zσ . Notice that γ zσ is shifted one cell to the right with respect to γ z , so that its last bit is written on the

Conclusion

Sakoda and Sipser raised the question of the cost of the elimination of nondeterminism from nite automata exploiting the possibility of moving the head in both directions. Though they conjectured that this cost is exponential, we proved that a determinization of polynomial-size cost is possible for some simulating machines that are deterministic and have some extra capabilities than 2dfas. The extensions of 2dfas we considered are some special cases of one-tape Turing machines which are not more powerful than 2dfas, namely they recognize the class of regular languages.

In Theorem 4 we showed such a polynomial determinization using Hennie machines. However, this result is not fully satisfying because of known drawbacks of dHms: on the one hand, it is not decidable whether a Turing machine is actually a Hennie machine; on the other hand, no recursive function bounds the size blowup of the conversion of dHms into 1dfas. These drawbacks are avoided when moving to weight-reducing devices [START_REF] Guillon | Weight-reducing Turing machines[END_REF].

We do not know if the simulations of Theorem 4 can be changed in such a way that the resulting dHm is always weight-reducing while keeping the size cost polynomial, and we leave it as an open problem. However, we solve this question in some particular cases. Indeed, when equivalence is required only over long enough inputs, or when the input alphabet is unary, polynomial size determinizations using wrdHms are possible (Theorems 2, 3 and 5).

Moreover, our main result states that it is always possible to eliminate nondeterminism from nite automata by using weight-reducing linear-time Turing machines as long as they are not required to be end-marked (Theorem 1), namely when the simulating machine is allowed to use extra tape beside the

  ε} is a factor of the tape content. The successor relation on congurations extends onto partial congurations. In particular, zpX * zXq with |X| = 1 means that there exists a computation path starting from the rightmost position of zX (with the head scanning the symbol X) in state p, ending while entering the cell to the right of this position in state q, and which visits only cells from the part of the tape containing zX in the meantime. By storing in a set τ zX the pairs of states (p, q) such that such a computation path exists, we save the possible behaviors of A when moving leftward from the cell c immediately to the right of zX. Indeed, in order to reach an accepting conguration after moving leftward from c, the device should eventually return to c, because acceptance is made after passing the right endmarker. We are going to give the formal denition of the set τ zX for a prex zX of the tape content, together with the denition of the set γ zX of states that are reachable from the initial conguration, when visiting for the rst time the position to the right of the part containing zX. Formally, for a prex zX ∈ { } • Σ * • {ε, } of the tape contents with |X| = 1 we have:

part that initially contains the input.

Partially supported by Gruppo Nazionale per il Calcolo Scientico (GNCS-INdAM). 2 Supported by the Czech Science Foundation, grant 19-21198S.

are able to obtain a polynomial-size Hennie machine (not necessarily weight reducing) using a dierent technique, which is based on the analysis of the computation graph of the simulated 2nfa.

Theorem 4. Each n-state 2nfa is equivalent to a dHm with O(n 9 log n) states and O(n 6 ) tape symbols.

Proof. Let A = Q, Σ, δ, q 0 , F be a 2nfa, with #Q = n. Without loss of generality we suppose F = {q f }. Let w ∈ Σ * be an input word, with m = |w|.

We distinguish three cases, depending on m. Observe that the simulating dHm H can decide the case by performing a reading traversal of the input using a polynomial number of states.

If m ≤ log n, then H simulates a 1dfa with a polynomial number of states in n (and in the number of input symbols, which is assumed to be a xed constant), which agrees with A on all strings of length at most log n.

Finally, if log n < m < n 2 , then H checks whether there is an accepting computation of A on w by analyzing the computation graph G = V, E of A on w, dened as follows. The set of vertices of G is V = Q × {0, . . . , m + 1} ∪ {(q f , m + 2)}, where the pair (q, i) ∈ V corresponds to the conguration on input w in which A is in the state q while scanning the i-th symbol of the input tape. The edges in E represent single moves, i.e., there exists an edge from (q, i) to (p, j) if and only if (p, j -i) ∈ δ(q, w i ), where w = w .

The simulating Hennie machine H should check the existence of a computation of A starting from the initial state q 0 with the head on the left endmarker (i.e., at position 0) and ending in the unique nal state q f after passing the right endmarker (i.e., at position m + 2). This is equivalent to Function reachable(p, i, q, j, T ): boolean Checks the existence of a path from (p, i) to (q, j) of length less than or equal to T in the graph of the congurations of a given 2nfa on

if reachable(r, , q, j, T /2 ) then return true 9 return false checking the existence of a path from the node (q 0 , 0) to the node (q f , m + 2) in G. Let K = n(m + 2) + 1 be the number of nodes in G. If such a path exists, then there should exist one of length at most K. Hence, checking the existence of an accepting computation reduces to checking the existence of a path of length at most K in G. The recursive function reachable is used to perform this checking by calling reachable(q 0 , 0, q f , m + 2, K).

Let us describe how a call of reachable(p, i, q, j, T ) works. The function has to check if there exists a computation from (p, i) to (q, j) of length at most T . This is done by using a divide-and-conquer technique as in the famous proof of Savitch's Theorem [START_REF] Savitch | Relationships between nondeterministic and deterministic tape complexities[END_REF]. If (p, i) = (q, j), i.e., there is a path of length 0 from (p, i) to (q, j), then the function returns true independently Theorem 5. For each n-state 1nfa A, there exists a wr dHm H with O(n 3 ) states and O(1) tape symbols which agrees with A on strings of length at least n.

Proof. In order to obtain H, we build a dTm T equivalent to A with the following properties:

(P1) the size of T is bounded by a polynomial in the size of A;

(P2) the number of visits to each cell in any computation is bounded by a polynomial in n;

(P3) only n tape cells beside the initial segment are used, in any computation.

Then, using (P2) and Lemma 1, T can be turned into an equivalent wrdTm preserving (P1) and (P3). Finally, using (P3) and Lemma 2, the resulting wrdTm is converted to the wanted wrdHm H whose size is polynomial in the size of A.

We build T by adapting the classical powerset construction for converting 1nfas into 1dfas. In this standard construction, the simulating 1dfa scans the input word, while keeping updated, at each step, the subset of states that can be reached by A from the initial conguration while reading input symbols. Our construction uses this technique but, instead of storing the subset in the nite control of the simulating machine, T stores the successive subsets on the tape, exploiting the writing capability of wrdTms in order to avoid an exponential size blowup.

Let A = Q, Σ, δ, q 0 , F with Q = {q 0 , q 1 , . . . , q n-1 }. Following the notation of Section 3, for any input prex z, we consider the set γ z ⊆ Q of states that are reachable from the initial conguration after having read z.

rightmost cell of the current working segment (which initially contains σ).

Furthermore, during the update procedure, each cell of the current working segment is visited O(n) times. Finally, when reaching the rst cell to the right of the initial segment (containing the blank symbol), T accepts if and only if γ w contains a nal state. By slightly modifying the above update procedure, we may assume that this information has been prepared in the nite control. Indeed, when computing γ zσ , the dTm T can store in a state component whether γ zσ intersects F .

The described approach implies the use of n extra tape cells to the left of the initial segment, on which T has initially written γ ε . No extra space is necessary, and thus (P3) is satised. Moreover, the simulating machine uses O(1) tape symbols, and O(#Σ • n 3 ) states for simultaneously storing the variables σ, q i , q j , and the head position relative to the current working segment. This implies (P1). Next, each tape cell is used for storing at most n successive subsets of states. Hence, its total number of visits is in O(n 2 ), yielding (P2).

By Theorem 4, every n-state 2nfa can be transformed into an equivalent dHm of size polynomial in n. So, using the same result, we can also transform 1nfas. For this particular case, we now present a more direct simulation which uses a technique similar to that of proof of Theorem 4.

Let A = Q, Σ, δ, q 0 , F be an n-state 1nfa. At the cost of one extra state, we suppose F = {q f }. Let w ∈ Σ * be an input to A. Distinguish two cases by m = |w|.

If m ≤ n, the machine H checks whether there is an accepting computation of A on w by calling reachableOneWay(q 0 , 0, q f , m), a slightly modi-ed version of the function reachable presented in the proof of Theorem 4, adapted to deal with 1nfas. Function reachableOneWay(p, i, q, j): boolean Checks the existence of a path from (p, i) to (q, j) of length j-i in the graph of the congurations of a given 1nfa on input w = w 1 • • • w m 10 if (p, i) = (q, j) then return true 11 if j -i = 1 and q ∈ δ(p, w j ) then return true 12 if j -i > 1 then 13 foreach r ∈ Q do 14 if reachableOneWay(p, i, r, (i + j)/2 ) then 15 if reachableOneWay(r, (i + j)/2 , q, j) then return true [START_REF] Tadaki | Theory of one-tape linear-time Turing machines[END_REF]

return false

The recursion depth is O(log m). At each level of the recursion, the function needs to store states p, q, r and indices i, j. This can be done in a tape cell if O(n 5 ) work symbols are provided for this purpose. The function runs in n O(log m) time.

If m > n, the Hennie machine H executes the computation described in the proof of Theorem 5.

In conclusion, the constructed machine H has the number of states and tape symbols polynomial in n, and hence it is of size polynomial in n. Note that the number of transitions performed by H over any tape eld is n O(log n) .


Sebastião Quintas

Alberto Abad

Julie Mauclair

Virginie Woisard

Julien Pinquier

TOWARDS REDUCING PATIENT EFFORT FOR THE AUTOMATIC PREDICTION OF SPEECH INTELLIGIBILITY IN HEAD AND NECK CANCERS

Keywords: Pathological Speech, Speech Intelligibility, Deep Learning, Head and Neck Cancer

The automatic prediction of speech intelligibility can be seen as a growing and relevant alternative to the perceptual evaluations used clinically, which are known to be biased, variant and subjective. We propose an automatic way to regress an intelligibility score based on a recurrent model with a self-attention mechanism. This approach not only presented a high correlation of 0.87 when applied to a pseudo-word task designed for head and neck cancers, but also a significant decrease in error of more than 50%, when compared to previous approaches. Moreover, we have also studied the reliability of the same system when operating with smaller amounts of data at inference time. The results suggest that we can reduce the linguistic sample size to only 30% of the full sample, without losing performance. This aspect validates the reliability of using a smaller subset of data when predicting intelligibility, which can be extremely useful to prevent patient's fatigue by creating smaller batteries of clinical exams.

INTRODUCTION

Loss of speech intelligibility is commonly found in the posttreatment of conditions that affect the vocal tract, such as head and neck cancer (HNC) and neurodegenerative diseases with dysarthria symptoms. Major functional repercussions on the upper aerodigestive tract (breathing, swallowing, and phonation/speech) are likely to appear, hence a functional impairment at communication level is expected, impacting the patient's quality of life [START_REF] De Graeff | Long-term quality of life of patients with head and neck cancer[END_REF]. Since an early tracking and diagnosis are usually correlated to a better prognosis, due to the progressive and timed implementation of post-treatment measures, the perceptual evaluation of speech intelligibility has long been the most common method of disordered speech assessment. The perceptual assessments performed clinically normally include extensive recording tasks, that can become highly wearing on patients, namely the ones with severe speech impairments. Patient's fatigue is a common reason to leave some of these speech tasks incomplete. Due to this, it becomes relevant to devise more targeted and less extensive batteries of exams. Furthermore, these measures are known to be highly variable, biased and subjective, since the evaluation can be conditioned on several aspects such as prior knowledge of the task being issued (e.g. passage reading tasks), earlier assessments or also being conditioned on a priori knowledge of the patients. This aspect greatly affects reproducibility [START_REF] Balaguer | Effects of oral and oropharyngeal cancer on speech intelligibility using acoustic analysis: Systematic review[END_REF]. The usage of tasks based on pseudo-words and pseudo-sentences can mitigate the bias associated to the prior knowledge of the phonetic content being issued [START_REF] Lalain | Design and development of a speech intelligibility test based on pseudowords in french: Why and how?[END_REF], however the majority of the issues that arise from a perceptual assessment still remain similar.

An automatic approach can be seen as an interesting alternative to perceptual measures, that could tackle the aforementioned issues. These approaches can promote more reliable, objective and reproducible scores [START_REF] Fex | Perceptual evaluation[END_REF][START_REF] Middag | Automatic analysis of pathological speech[END_REF]. In order to automatically predict speech intelligibility, one can use approaches that regress a score from the word error rate obtained via an ASR (automatic speech recognizer), however this type of approach tends to underperform on speakers with severe speech impairments [START_REF] Christensen | A comparative study of adaptive, automatic recognition of disordered speech[END_REF]. Other approaches make use of speech processing technologies based on the extraction of relevant features, such as MFCCs, filterbanks, speaker embeddings, etc. [START_REF] Middag | Automated intelligibility assessment of pathological speech using phonological features[END_REF][START_REF] Quintas | Automatic prediction of speech intelligibility based on x-vectors in the context of head and neck cancer[END_REF][START_REF] Lin | Classifying speech intelligibility levels of children in two continuous speech styles[END_REF][START_REF] Quintas | Automatic assessment of speech intelligibility using consonant similarity for head and neck cancer[END_REF]. Nevertheless, it is known that these type of datadriven systems tend to require significant amounts of data in order to operate efficiently [START_REF] Ravì | Deep learning for health informatics[END_REF]. The perceptual evaluation of speech intelligibility also differs from the one applied to the speech-in-noise paradigm [START_REF] Andersen | Nonintrusive speech intelligibility prediction using convolutional neural networks[END_REF]. While the definition of intelligibility may be similar to both, the perceptual decoding differs between the two. Traditional intelligibility predictors used in speech perception, such as STOI or E-STOI, require the usage of clean time-aligned signals, even in endto-end approaches [START_REF] Pedersen | End-to-end speech intelligibility prediction using time-domain fully convolutional neural networks[END_REF], which is unfeasible for pathological speech.

Given the fact that both patient's fatigue and the inherent subjectivity of the perceptual measures are recurrent clinical problems, and that data-driven automatic approaches tend to require larger amounts of data, in the present work we aim to:

• Present an automatic system that is capable of regressing objective and reproducible intelligibility measures (section 2), while achieving a high correlation with the perception-based measures. This is illustrated by our experiments in section 3, using a pseudo-word task from the French corpus of head and neck cancer.

• Prove that the same system can still achieve high correlations and accurate predictions when using significantly smaller amounts of data (section 4).

METHODOLOGY

The proposed methodology 1 is based on the usage of a recurrent model with self-attention, applied to a pseudo-word task (see section 3.1). We can divide the system into two distinct modules. In the first part, we make use of a recurrent model in order to obtain automatic scores for each pseudo-word. The second part corresponds to the regression of an intelligibility score per speaker, based on the individual scores of each one's respective pseudo-words. Figure 1 illustrates our proposed method.

Modelization

The proposed system relies on a recurrent model with self-attention.

Our system receives as input the individual audio files corresponding to each unique pseudo-word. From these audio files, we calculate on each window of 25ms with a 10ms stride, 40 filterbanks to be used as input features. For each pseudo-word, we use the intelligibility score obtained from its perceptual transcription as the target (see section 3.1). Our proposed model uses a bidirectional recurrent block, with three Gated Recurrent Unit (GRU) layers with an input dimension of 40 and a hidden dimension of 100. At the output of the block, a self-attention mechanism can be found, containing a single head. This mechanism allows the system to focus more on particular parts of the input file, while ignoring less relevant parts. After the attention mechanism, the utterance is passed to a set of three fully-connected layers, with a dimension of 100 units each and Rectified Linear Units (ReLUs) non-linearities. Finally, at the end of the system we have a Global Max Pooling layer used to obtain the individual score for each pseudo-word. Skip connections are added as shown in figure 1. By using the attention mechanism, we hypothesize that the system will automatically focus on and learn interesting interdependencies between the articulation of consecutive phonemes, that are known to be highly relevant for speech intelligibility [START_REF] Marczyk | Have a cake and eat it too: Assessing discrimination performance of an intelligibility index obtained from a reduced sample size[END_REF]. The fully-connected block and max pooling aim to directly maximize the use of these learned interdependencies when predicting the final intelligibility score.

Automatic Regression of Speech Intelligibility

The second part of our proposed model corresponds to the regression of an intelligibility score for each speaker, as a function of the individual score of each pseudo-word. Instead of having the proposed model directly predicting the intelligibility score at speaker level, we opted to do the average of the set of each speaker's pseudowords instead. This aspect promotes a more explainable measure, as a speaker's score can be traced down to the individual score of their pseudo-words. Interpretable systems are highly relevant clinically [START_REF] Diprose | Physician understanding, explainability, and trust in a hypothetical machine learning risk calculator[END_REF]. The usage of the average set of pseudo-words also gives us more flexibility to evaluate the importance of specific types of words in the automatic score.

EXPERIMENTS AND RESULTS

C2SI Corpus

In the present study, the focus of attention was set to the pseudo-word task recorded in the context of the French corpus of head and neck cancer (C2SI) [START_REF] Astésano | Carcinologic speech severity index project: A database of speech disorder productions to assess quality of life related to speech after cancer[END_REF]. Here, a set of speakers was invited to record each a set of 52 pseudo-words, that respect French phonotactic and orthographic rules. The pseudo-words are randomly drawn from a set of 89,346 possible forms, knowing that each list is, by construction, phonetically balanced. Due to the large amount of possible forms, the eventual repetition of a pseudo-word, despite being possible, is highly unlikely. The lists are balanced in the sense that they all contain the same number of each phoneme, but in different combinations (see [START_REF] Lalain | Design and development of a speech intelligibility test based on pseudowords in french: Why and how?[END_REF] for further reference). The perceptual intelligibility measure used in this study was obtained by averaging the individual transcription score of each pseudo-word by three distinct naive listeners, also known as perceived phonological deviation (PPD). This was used as reference throughout this work, and was calculated as a function of the distance between the transcribed word and the original one, taking into consideration a vowel and consonant matrix cost [START_REF] Ghio | How to compare automatically two phonological strings: Application to intelligibility measurement in the case of atypical speech[END_REF]. The distance between the transcribed pseudo-words and the canonical pronunciations was obtained using a Wagner-Fischer algorithm [START_REF] Wagner | The string-to-string correction problem[END_REF]. The perceptual scores range between 0, corresponding to the words perfectly pronounced, and 5, corresponding to unintelligible words. The final intelligibility score for each speaker was obtained by averaging the scores of their 52 pseudo-words. A set of 126 speakers was used, where 40 are controls and 86 patients.

System Training and Evaluation

In order to train the proposed system, a 10-fold cross validation scheme was employed. At each fold, a set of 113 speakers (patients and controls) are used for training, and the remaining 13 speakers for evaluation. For each fold, the system was trained during 200 epochs. A learning rate of 0.001 was used, with a polynomial decay until 0.0001 during the first 50 epochs. A batch size of 16 and the Adam optimizer were used during training as well. Spearman's Correlation (ρ) and the Root Mean Squared Error (RM SE) were chosen to evaluate our system. The target scores used were the perceptual intelligibility measures aforementioned in subsection 3.1, corresponding to the perceived phonological deviation.

The proposed approach is compared to two alternative systems. The first system is based on a Wagner-Fischer algorithm (previous baseline [START_REF] Fredouille | Acoustic-phonetic decoding for speech intelligibility evaluation in the context of head and neck cancers[END_REF]) that aligns the canonical pronunciations with the results obtained from the automatic transcription of the pseudowords. Due to the nature of the pseudo-words, the usage of a language model becomes invalidated. A text-constrained alignment is used instead, where each phoneme is represented by a three-state context-independent hidden markov model (HMM). Furthermore, after obtaining the phoneme boundaries, those are reconsidered by searching the most appropriate phoneme label among a set of 36 French phones while keeping the segment frontiers fixed (denoted as semi-constrained acoustic-phonetic decoding). In this manner, each speech segment available in the phoneme segmentation is confronted with the 36 three-state context-independent HMM obtained previously.

The second system compared to our approach is an intelligibility regression based on x-vector speaker embeddings [START_REF] Snyder | X-vectors: Robust dnn embedings for speaker recognition[END_REF]. Due to their nature, whose performance drops when using short file segments, the speaker embeddings were extracted from the file containing the entire set of pseudo-words, instead of extracting individual embeddings for each word. Similarly to [START_REF] Quintas | Automatic prediction of speech intelligibility based on x-vectors in the context of head and neck cancer[END_REF], the x-vectors are used as features and fed to a shallow neural network that predicts speech intelligibility from the entire set of pseudo-words. A pre-trained model was used to extract the speaker embeddings. The shallow neural network was trained using a 10-fold cross-validation scheme.

The results, presented on table 2 and illustrated in figure 2, suggest a significant increase in correlation from 0.80 to 0.87, when compared to the latest previous system, and a drastic reduction on the RMSE values of more than 50 %, when compared to the Wagner-Fischer baseline.

Table 2. Comparison between two reference systems and our proposed approach.

ρ RM SE Wagner-Fischer (baseline) 0.72 0.792 X-vector Speaker Embeddings 0.80 0.447 Recurrent Model with Self-Attention 0.87 0.370

Pseudo-Word Reduction

Clinically, the recording of 52 pseudo-words is not only timeconsuming, but also highly wearing for the patients, namely the ones with more severe speech impairments. Given that patient's fatigue is not uncommon to happen in these recording sessions, which translates into leaving the recording session incomplete, it becomes thoroughly pertinent to evaluate how our proposed auto-Fig. 2. Results of the automatic prediction of speech intelligibility using the Perceived Phonological Deviation (PPD).

matic approach behaves when predicting intelligibility with smaller quantities of data per speaker. Different sub-sets of pseudo-words have been investigated depending on the position and number of occurrences of d.c. [START_REF] Marczyk | Have a cake and eat it too: Assessing discrimination performance of an intelligibility index obtained from a reduced sample size[END_REF] as shown in Table 3. For each reduced sub-set of pseudo-words, the final automatic score of every subject is computed as the mean of the scores of the sub-set, while the reference score still corresponds to the mean value of the 52 perceptual scores. The pseudo-word reduction only takes place during prediction and no new models were trained.

Given the results obtained with the two 16 words sets, with a d.c. at the beginning and middle respectively, we can only see minor changes both at correlation and at RMSE. These results corroborate the fact found in [START_REF] Marczyk | Have a cake and eat it too: Assessing discrimination performance of an intelligibility index obtained from a reduced sample size[END_REF] for the perceptual measures, and therefore we can say that it is possible to use significantly smaller amounts of data whilst maintaining the reliability of the automatic measures promoted. For the remaining subsets of words, the results were similar, but they tend to accentuate the difference between pseudo-words with and without d.c. This aspect was particularly evident in the set without a d.c. (26 words), where besides having 10 more words than the two sets with d.c., the correlation and error remain comparable. This analysis shows that pseudo-words with occurrences of d.c. are more relevant to obtain robust and reliable automatic intelligibility measures. This aspect was also illustrated by the results obtained in the last line of table 3, which displayed the results obtained with pseudo-words containing the two types of d.c.. Here a fairly decent correlation and RMSE values were obtained considering the small quantity of only five pseudo-words, that corresponds to less than 10% of the original quantity of pseudo-words used per speaker. We hypothesize that a larger subset of these words would outperform the other reduced lists, but we were limited by their small quantity in the corpus.

DISCUSSION

The results obtained suggest that it is possible to obtain high correlation values between the perceptual evaluations and automatic predictions. In addition, not only the correlation values increased greatly, Table 3. Comparison between the scores obtained on the complete pseudo-word list and those of the reduced lists. but also the RMSE value drastically reduced to more than half compared to a prior approach [START_REF] Fredouille | Acoustic-phonetic decoding for speech intelligibility evaluation in the context of head and neck cancers[END_REF].

Model

Moreover, the analysis performed in subsection 3.3 showed that it is possible to remove words used in the global score and barely affect the reliability of the same automatic measures. This aspect becomes crucial clinically, where not only we can save precious time by recording fewer data, but also mitigate patient's fatigue. The usage of pseudo-words with d.c. was crucial to achieve these results, since it displayed a clear direction towards the best type of words to be used in these assessments. We believe that, these words tend to outperform their counterpart due to the larger phonetic content and key co-articulations between consonant and vowels and consecutive consonants. These co-articulations are an important marker for the post-operative assessment of head and neck cancers [START_REF] Saravanan | Speech outcome in oral cancer patients -pre-and postoperative evaluation: A cross-sectional study[END_REF]. A larger presence of consonants is also hypothesized to be a good indicator of speech intelligibility [START_REF] Crevier-Buchman | Intelligibility of french consonants after partial supra-cricoid laryngectomy[END_REF][START_REF] Fort | Consonants are more important than vowels in the bouba-kiki effect[END_REF].

While keeping fewer pseudo-words, the results obtained with the d.c. subsets were encouraging, leaving the possibility for further reductions without largely affecting the scores. The creation of a reduced list, as well as working towards more interpretable scores through the means of the attention plots remain interesting leads for future work. The usage of a small number of words also becomes relevant clinically when compared to other automatic approaches that operate, for example, at sentence level [START_REF] Quintas | Automatic prediction of speech intelligibility based on x-vectors in the context of head and neck cancer[END_REF], showing that high correlations can be achieved while using smaller amounts of data.

CONCLUSIONS

We proposed a new way to automatically predict speech intelligibility, based on a recurrent model with self-attention, for head and neck cancers. The proposed method achieved a high correlation value of 0.87 and a drastic reduction of more than 50% on the RMSE values, when compared to a previous approach based on the automatic transcription of the pseudo-word task. Moreover, the system was also studied on its reliability towards using smaller amounts of data. The results suggest that, we can significantly reduce the quantity of pseudo-words used given specific criteria whilst maintaining accurate predictions. The usage of pseudo-words with doubleconsonants was crucial for this reduction, showing that these words are indeed a viable indicator of speech intelligibility. This aspect becomes highly relevant in clinical practice, since it can not only help counter the variance and subjectivity associated with perceptual measures, but also alleviate patient's fatigue by recording smaller quantities of data.

Fig. 1 .

 1 Fig. 1. Global overview of the proposed methodology. INT stands for the intelligibility score. N corresponds to the number of pseudowords.

  Each pseudo-word follows the structure C(C)1V1C(C)2V2, where C(C)i is either a single consonant or a consonant group and Vi a single vowel. Each set of 52 words has a subset of 16 words with an occurrence of a double consonant (d.c.) at the beginning of the word, 16 words with d.c. in the middle and at least 26 words without d.c. The pseudo-words can have both occurrences of the d.c., either at the beginning or at the middle, however in a smaller quantity (see table 1

Table 1 .

 1 ). Example of a set of 52 pseudo-words. Blue and violet represent the d.c. clusters. banfou bleja boucti brimpli chessant choniou clifant cogu crimpin daillu dinrant dredi fanrsi flinrpu fouma fravi gabi glunou grorvo guchin joutu juro lanvin lerda messo mouco nianlo niejo noksa nouillou pastu pidant ploniou pripin psila quiga rinta rurnu sanvrin scuna souquin spaclant sticho tangri tougzu tradrou virjant vumou yainzi yaltin zebou zouzant

https://github.com/Elquintas/ Self-Attention-Speech-intelligibility ICASSP

-2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) | 978-1-7281-6327-7/23/$31.00 ©2023 IEEE | DOI: 10.1109/ICASSP49357.2023.10094921

Authorized licensed use limited to: IEEE Xplore. Downloaded on May 10,2023 at 11:55:04 UTC from IEEE Xplore. Restrictions apply.

ACKNOWLEDGEMENTS

This project has received funding from the European Union's Horizon 2020 research and innovation programme under Marie Skłodowska-Curie grant agreement No 766287.