Luc Dartois

Ismaël Jecker

Pierre-Alain Reynier

Aperiodic String Transducers

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The theory of regular languages constitutes a cornerstone in theoretical computer science. Initially studied on languages of finite words, it has since been extended in numerous directions, including finite and infinite trees. Another natural extension is moving from languages to transductions. We are interested in this work in stringto-string transductions, and more precisely in string-to-string functions. One of the strengths of the class of regular languages is their equivalent presentation by means of automata, logic, algebra and regular expressions. The class of so-called regular string functions enjoys a similar multiple presentation. It can indeed be alternatively defined using deterministic two-way finite state transducers (2DFT), using Monadic Second-Order graph transductions interpreted on strings (MSOT) [START_REF] Engelfriet | MSO definable string transductions and two-way finite-state transducers[END_REF], and using the model of streaming string transducers (SST) [START_REF] Alur | Expressiveness of streaming string transducers[END_REF]. More precisely, regular string functions are equivalent to different classes of SST, namely copyless SST [START_REF] Alur | Expressiveness of streaming string transducers[END_REF] and k-bounded SST, for every positive integer k [START_REF] Alur | Regular transformations of infinite strings[END_REF]. Different papers [START_REF] Engelfriet | MSO definable string transductions and two-way finite-state transducers[END_REF][START_REF] Alur | Expressiveness of streaming string transducers[END_REF][START_REF] Alur | Regular transformations of infinite strings[END_REF][START_REF] Alur | From monadic second-order definable string transformations to transducers[END_REF] have proposed transformations between 2DFT, MSOT and SST, summarized on Figure 1.

The connection between automata and logic, which has been very fruitful for model-checking for instance, also needs to be investigated in the framework of trans- Plain (resp. dotted) arrows concern regular models (resp. bracketed models). Original constructions presented in this paper are depicted by thick dashed arrows and are valid for both regular and aperiodic versions of the models.

ductions. As it has been done for regular languages, an important objective is then to provide similar logic-automata connections for subclasses of regular functions, providing decidability results for these subclasses. As an illustration, the class of rational functions (accepted by one-way finite state transducers) owns a simple characterization in terms of logic, as shown in [START_REF] Filiot | Logic-automata connections for transformations[END_REF]. The corresponding logical fragment is called order-preserving MSOT. The decidability of the one-way definability of a two-way transducer proved in [START_REF] Filiot | From two-way to one-way finite state transducers[END_REF] thus yields the decidability of this fragment inside the class of MSOT.

The first-order logic considered with order predicate constitutes an important fragment of the monadic second order logic. It is well known that languages definable using this logic are equivalent to those recognized by finite state automata whose transition monoid is aperiodic (as well as other models such as star-free regular expressions). These positive results have motivated the study of similar connections between first-order definable string transformations (FOT) and restrictions of state-based transducers models. Two recent works provide such characterizations for 1-bounded SST and 2DFT respectively [START_REF] Filiot | First-order definable string transformations[END_REF][START_REF] Carton | Aperiodic two-way transducers and fo-transductions[END_REF]. The authors study a notion of transition monoid for these transducers, and prove that FOT is expressively equivalent to transducers whose transition monoid is aperiodic by providing back and forth transformations between FOT and 1-bounded aperiodic SST (resp. aperiodic 2DFT). In particular, [START_REF] Filiot | First-order definable string transformations[END_REF] lets as an open problem whether FOT is also equivalent to aperiodic copyless SST and to aperiodic k-bounded SST, for every positive integer k. It is also worth noticing that these characterizations of FOT, unlike the case of languages, do not allow to decide the class FOT inside the class MSOT. Indeed, while decidability for languages relies on the syntactic congruence of the language, no such canonical object exists for the class of regular string transductions, although some recent work was done on one-way transducers [START_REF] Filiot | First-order definability of rational transductions: An algebraic approach[END_REF].

In this work, we aim at improving our understanding of the relationships between 2DFT and SST. We first provide an original transformation from 1-bounded (or copyless) SST to 2DFT, and study its complexity. While the existing construction used MSO transformations as an intermediate formalism, resulting in a nonelementary complexity, our construction is in double exponential time, and in single exponential time if the input SST is copyless. Conversely, we describe a direct construction from 2DFT to copyless SST, which is similar to that of [START_REF] Alur | Expressiveness of streaming string transducers[END_REF], but avoids the use of an intermediate model. These constructions also allow to establish links between the crossing degree of a 2DFT, and the number of variables of an equivalent copyless (resp. 1-bounded) SST, and conversely. Last, we provide a direct construction from k-bounded SST to 1-bounded SST, while the existing one was using copyless SST as a target model and not 1-bounded SST [START_REF] Alur | Regular transformations of infinite strings[END_REF]. These constructions are represented by thick dashed arrows on Figure 1.

In order to lift these constructions to aperiodic transducers, we introduce a new transition monoid for SST, which is intuitively more precise than the existing one (more formally, the existing one divides the one we introduce). We use this new monoid to prove that the three constructions we have considered above preserve the aperiodicity of the transducer. As a corollary, this implies that FOT is equivalent to both aperiodic copyless and k-bounded SST, for every integer k, two results that were stated as conjectures in [START_REF] Filiot | First-order definable string transformations[END_REF] (see Figure 1).

Definitions

Words, Languages and Transducers

Given a finite alphabet A, we denote by A * the set of finite words over A, and by the empty word. The length of a word u ∈ A * is its number of symbols, denoted by |u|. For all i ∈ {1, . . . , |u|}, we denote by u[i] the i-th letter of u.

A language over A is a set L ⊆ A * . Given two alphabets A and B, a trans-

duction from A to B is a relation R ⊆ A * × B * . A transduction R is functional if it is a function.
The transducers we will introduce will define transductions. We will say that two transducers T, T are equivalent whenever they define the same transduction.

Automata A deterministic two-way finite state automaton (2DFA) over a finite alphabet A is a tuple A = (Q, q 0 , F, δ) where Q is a finite set of states, q 0 ∈ Q is the initial state, F ⊆ Q is a set of final states, and δ is the transition function, of type δ : Q × (A { , }) → Q × {+1, 0, -1}. The new symbols and are called endmarkers.

An input word u is given enriched by the endmarkers, meaning that A reads the input u . We set u[0] = and u[|u| + 1] = . Initially the head of A is on the first cell in state q 0 (the cell at position 0). When A reads an input symbol, depending on the transitions in δ, its head moves to the left (-1), stays at the same

1 2 3 a|a, +1 | , +1 b| , -1 | , -1 a|b, -1 b| , +1 | , +1 a| , +1 b| , +1 a X →Xa Y →Y b b X →XY Y → XY Fig. 2: Aperiodic 2DFT (left)
and SST (right) realizing the function f . position (0), or moves to the right (+1). To ensure the fact that the reading of A does not go out of bounds, we assume that there is no transition moving to the left (resp. to the right) on input symbol (resp. ). A stops as soon as it reaches the endmarker in a final state. A configuration of A is a pair (q, i) ∈ Q × N where q is a state and i is a position on the input tape. A run r of A is a finite sequence of configurations. The run

r = (p 1 , i 1 ) . . . (p m , i m ) is a run on an input word u ∈ A * of length n if i m n + 1, and for all k ∈ {1, . . . , m -1}, 0 i k n + 1 and δ(p k , u[i k ]) = (p k+1 , i k+1 -i k ). It is accepting if p 1 = q 0 , i 1 = 0,
and m is the only index where both i m = n + 1 and p m ∈ F . The language of a 2DFA A, denoted by L(A), is the set of words u such that there exists an accepting run of A on u.

Transducers Deterministic two-way finite state transducers (2DFT) from A to B extend 2DFA with a one-way left-to-right output tape. More formally, the transition relation is extended with outputs:

δ : Q × (A { , }) → B * × Q × {-1, 0, +1}.
When a transition with right-hand side (v, q, m) ∈ B * × Q × {-1, 0, +1} is fired, the word v is appended to the right of the output tape. Formally, 2DFT are defined as tuples T = (A, B, Q, q 0 , F, δ).

A run of a 2DFT is a run of its underlying automaton, i.e. the 2DFA obtained by ignoring the output (called its underlying input automaton). A run r may be simultaneously a run on a word u and on a word u = u. However, when the input word is given, there is a unique sequence of transitions associated with r. Given a 2DFT T , an input word u ∈ A * and a run r = (p 1 , i 1 ) . . . (p m , i m ) of T on u, the output of r on u is the word obtained by concatenating the outputs of the transitions followed by r. If r contains a single configuration, this output is simply . The transduction defined by T is the relation R(T ) defined as the set of pairs (u, v) ∈ A * × B * such that v is the output of an accepting run r on the word u. As T is deterministic, such a run is unique, thus R(T ) is a function.

Streaming String Transducers Let X be a finite set of variables denoted by X, Y, . . . and B be a finite alphabet. A substitution σ is defined as a mapping σ : X → (B ∪ X ) * . Let S X ,B be the set of all substitutions. Any substitution σ can be extended to σ : (B ∪ X ) * → (B ∪ X ) * in a straightforward manner. The Aperiodic String Transducers 5 composition σ 1 σ 2 of two substitutions σ 1 and σ 2 is defined as the standard function composition σ1 σ 2 , i.e. σ1 σ 2 (X) = σ1 (σ 2 (X)) for all X ∈ X . We say that a string u ∈ (B ∪ X ) * is k-linear if each X ∈ X occurs at most k times in u. A substitution σ is k-linear if σ(X) is k-linear for all X. It is copyless if for any variable X, there exists at most one variable Y such that X occurs in σ(Y ), and X occurs at most once in σ(Y ).

A streaming string transducer (SST) is a tuple T = (A, B, Q, q 0 , Q f , δ, X , ρ, F ), where (Q, q 0 , Q f , δ) is a deterministic one-way automaton over the alphabet A, B is the finite output alphabet, X is the finite set of variables, ρ : Q×(A { , }) → S X ,B is the variable update function and F : Q f (X ∪ B) * is the output function. The concept of a run of an SST is defined in an analogous manner to that of a finite state automaton. The sequence σ r,i 0 i |r| of substitutions induced by a run r = q 0 a1 -→ q 1 a2 -→ q 2 . . . q n-1 an --→ q n is defined inductively as the following: σ r,i =σ r,i-1 ρ(q i-1 , a i ) for 1 < i |r| and σ r,1 = ρ(q 0 , a 1 ). We denote σ r,|r| by σ r and say that σ r is induced by r.

If r is accepting, i.e. q n ∈ Q f , we can extend the output function F to r by F (r) = σ σ r F (q n ), where σ substitutes all variables by their initial value . For all words u ∈ A * , the output of u by T is defined only if there exists an accepting run r of T on u, and in that case the output is denoted by T (u) = F (r). The transformation R(T ) is then defined as the set of pairs (u, T (u)) ∈ A * × B * .

Example 1. As an example, let f : {a, b} * → {a, b} * be the function mapping any word u = a k0 ba k1 • • • ba kn to the word f (u) = a k0 b k0 a k1 b k1 • • • a kn b kn obtained by adding after each block of consecutive a a block of consecutive b of the same length. Since each word u over A can be uniquely written u = a k0 ba k1 • • • ba kn with some k i being possibly equal to 0, the function f is well defined. We give in Figure 2 a 2DFT and an SST that realize f . An SST T is copyless if for every (q, a) ∈ Q × (A { , }), the variable update ρ(q, a) is copyless. Given an integer k ∈ N >0 , we say that T is k-bounded if all its runs induce k-linear substitutions. It is bounded if it is k-bounded for some k.

The following theorem gives the expressiveness equivalence of the models we consider. Since our results will only involve state-based transducers, we give no definition of MSO graph transductions (see [START_REF] Filiot | Logic-automata connections for transformations[END_REF] for more details).

Theorem 2 ([8, 1, 3]) Let f : A * → B * be a function over words. Then the following conditions are equivalent:

• f is realized by an MSO graph transduction, • f is realized by a 2DFT, • f is realized by a copyless SST, • f is realized by a bounded SST.

Transition monoid of transducers

A (finite) monoid M is a (finite) set equipped with an associative internal law • M having a neutral element for this law. A morphism η : M → N between monoids is an application from M to N that preserves the internal laws, meaning that for all x and y in M , η(x • M y) = η(x) • N η(y). When the context is clear, we will write xy instead of x • M y. A monoid M divides a monoid N if there exists an onto morphism from a submonoid of N to M . A monoid M is said to be aperiodic if there exists a least integer n, called the aperiodicity index of M , such that for all elements x of M , we have

x n = x n+1 .
Given an alphabet A, the set of words A * is a monoid equipped with the concatenation law, having the empty word as neutral element. It is called the free monoid on A. A finite monoid M recognizes a language L of A * if there exists an onto morphism η : A * → M such that L = η -1 (η(L)). It is well-known that the languages recognized by finite monoids are exactly the regular languages.

The monoid we construct from a machine is called its transition monoid. We are interested here in aperiodic machines, in the sense that a machine is aperiodic if its transition monoid is aperiodic. We now give the definition of the transition monoid for a 2DFT and an SST.

u p q

Deterministic Two-Way Finite State Transducers As in the case of automata, the transition monoid of a 2DFT T is the set of all possible behaviors of T on a word. The following definition comes from [START_REF] Carton | Aperiodic two-way transducers and fo-transductions[END_REF], using ideas from [START_REF] Shepherdson | The reduction of two-way automata to one-way automata[END_REF] amongst others. As a word can be read in both ways, the possible runs are split into four relations over the set of states Q of T . Given an input word u, we define the left-to-left behavior bh (u) as the set of pairs (p, q) of states of T such that there exists a run on u starting on the first letter of u in state p and exiting u on the left in state q (see Figure on the right). We define in an analogous fashion the left-to-right, right-to-left and right-to-right behaviors denoted respectively bh r (u), bh r (u) and bh rr (u). Then the transition monoid of a 2DFT is defined as follows:

Let T = (A, B, Q, q 0 , F, δ) be a 2DFT. The transition monoid of T is (A { , }) * /∼ T where ∼ T is the conjunction of the four relations ∼ ll , ∼ lr , ∼ rl and ∼ rr defined for any words u, u of A * as follows: u ∼ xy u iff bh xy (u) = bh xy (u ), for x, y ∈ { , r}. The neutral element of this monoid is the class of the empty word , whose behaviors bh xy ( ) is the identity function if x = y, and is the empty relation otherwise.

Note that since the set of states of T is finite, each behavior relation is of finite index and consequently the transition monoid of T is also finite. Let us also remark that the transition monoid of T does not depend on the output and is in fact the transition monoid of the underlying 2DFA.

Aperiodic String Transducers 7

Streaming String Transducers A notion of transition monoid for SST was defined in [START_REF] Filiot | First-order definable string transformations[END_REF]. We give here its formal definition and refer to [START_REF] Filiot | First-order definable string transformations[END_REF] for advanced considerations. In order to describe the behaviors of an SST, this monoid describes the possible flows of variables along a run. Since we give later an alternative definition of transition monoid for SST, we will call it the flow transition monoid (FTM).

Let T be an SST with states Q and variables X . The flow transition monoid M T of T is a set of square matrices over the integers enriched with a new absorbent element ⊥. The matrices are indexed by elements of Q × X . Given an input word u, the image of u in M T is the matrix m such that for all states p, q and all variables

X, Y , m[p, X][q, Y ] = n ∈ N (resp. m[p, X][q, Y ] = ⊥) if,
and only if, there exists a run r of T on u from state p to state q, and X occurs n times in σ r (Y ) (resp. iff there is no run of T on u from state p to state q).

Note that if T is k-bounded, then for every word w, all the coefficients of its image in M T are bounded by k. The converse also holds. Then M T is finite if, and only if, T is k-bounded, for some k.

It can be checked that the machines given in Example 1 are aperiodic. Theorem 2 extends to aperiodic subclasses and to first-order logic, as in the case of regular languages [START_REF] Schützenberger | On finite monoids having only trivial subgroups[END_REF][START_REF] Mcnaughton | Counter-free automata[END_REF]. These results as well as our contributions to these models are summed up in Figure 1.

Theorem 3 ( [START_REF] Filiot | First-order definable string transformations[END_REF][START_REF] Carton | Aperiodic two-way transducers and fo-transductions[END_REF]) Let f : A * → B * be a function over words. Then the following conditions are equivalent:

• f is realized by a FO graph transduction, • f is realized by an aperiodic 2DFT, • f is realized by an aperiodic 1-bounded SST.

Substitution Transition Monoid

In this section, we give an alternative take on the definition of the transition monoid of an SST, and show that both notions coincide on aperiodicity and boundedness. The intuition for this monoid, that we call the substitution transition monoid, is for the elements to take into account not only the multiplicity of the output of each variable in a given run, but also the order in which they appear in the output. It can be seen as an enrichment of the classic view of transition monoids as the set of functions over states equipped with the law of composition. Given a substitution σ ∈ S X ,B , let us denote σ the projection of σ on the set X , i.e. we forget the parts from B. The substitutions σ are homomorphisms of X * which form an (infinite) monoid. Note that in the case of a 1-bounded SST, each variable occurs at most once in σ(Y ), and in the case of a copyless SST, the monoid is finite.

Substitution Transition Monoid of an SST. Let T be an SST with states Q and variables X . The substitution transition monoid (STM) of T , denoted M σ T , is a set of partial functions f : Q Q×S X , where S X is the monoid of homomorphisms on X , equipped with the composition. Given an input word u, the image of u in M σ T is the function f u such that for all states p, f u (p) = (q, σr ) if, and only if, there exists a run r of T on u from state p to state q that induces the substitution σr . This set forms a monoid when equipped with the following composition law: Given two functions f u , f v ∈ M σ T , the function f uv is defined by f uv (q) = (q , σ • σ ) whenever f u (q) = (q , σ) and f v (q ) = (q , σ ).

We now make a few remarks about this monoid. Let us first observe that the FTM of T can be recovered from its STM. Indeed, the matrix m associated with a word u in M T is easily deduced from the function f u in M σ T . This observation induces an onto morphism from M σ T to M T , and consequently the FTM of an SST divides its STM. This proves that if the STM is aperiodic, then so is the FTM since aperiodicity is preserved by division of monoids. Similarly, copyless and k-bounded SST (given k ∈ N >0 ) are characterized by means of their STM. This transition monoid can be separated into two main components: the first one being the transition monoid of the underlying deterministic one-way automaton, which can be seen as a set of functions Q → Q, while the second one is the monoid S X . The aware reader could notice that the STM divides the wreath product of transformation semigroups (Q, Q Q ) • (X * , S X ). However, as the monoid of substitutions is obtained through the closure under composition of the homomorphisms of a given SST, it may be infinite while the STM is always finite for k-bounded SST.

The next theorem proves that aperiodicity for both notions coincide, since the converse comes from the division of the STM by the corresponding FTM. Theorem 4. Let T be a k-bounded SST with variables. If its FTM is aperiodic with aperiodicity index n then its STM is aperiodic with aperiodicity index at most n + (k + 1) .

Proof. Let T be a k-bounded SST. We define a loop as the run induced by a pair (q, u) ∈ Q × A * such that δ(q, u) = q. Suppose now that M T is aperiodic, and let n be its aperiodicity index. Wlog, we assume that the transition function of T is complete. This implies that for all states p of T , there exists a state q such that p

u n --→ q u -→ q.
Then if the image of the loops (i.e. the set of all σ such that there exists a loop (q, u) where f u (q) = (q, σ)) in the STM is aperiodic with index m, then the STM is aperiodic with index at most n + m.

Consequently, in the following σ denotes the substitution of a loop of T , and we aim to prove that σ(k+1) = σ(k+1) +1 .

Before proving this though, we define the relation ⊆ X × X as follows. Given two variables X and Y , we have X Y if there exists a positive integer i such that X flows into Y in σ i . This relation is clearly transitive. The next lemma proves that it is also anti-symmetric, hence we can use this relation as an induction order to prove the result.

Lemma 5. Given two different variables X and Y , if X Y , then Y X.
Proof. We proceed by contradiction and assume that there exist two different variables X and Y and two integers i and j such that X occurs in σ i (Y ) and Y occurs in σ j (X).

Then for any m > 0, X occurs in σ m(i+j) (X) and Y occurs in σ m(i+j)+j (X). As T is aperiodic of index n, for m large enough we have σ m(i+j) = σ m(i+j)+j = σ n and thus both X and Y occur in both σ n (X) and σ n (Y ). Then σ 2n (X) contains both σ n (X) and σ n (Y ) and thus contains at least two occurrences of X and Y . By aperiodicity we have σ 2n (X) = σ n (X) thus σ n (X) contains two occurrences of X. By iterating this process, we prove that the number of occurrences of X in σ n (X) is not bounded, yielding a contradiction.

We now prove that for all variables X in X , σ(k+1) (X) = σ(k+1) +1 (X) by treating the following two cases:

• If X ∈ σ(X), then either σ(X) = X and then σ2 (X) = σ(X), or there exists Y = X such that Y ∈ σ(X). In the latter case, we get by iteration that for all i > 0,

|σ i (X)| > Σ j<i |σ j (Y )|. Then as T is k-bounded, we have |σ i (X)| k and thus Σ j<i |σ j (Y )
| is bounded, and σk (Y ) = , which proves that σk (X) = σk +1 (X).

• If X ∈ σ(X), let us consider the relation . By Lemma 5 this relation is cycle-free. Then there is a lesser level, on which there are the variables Y such that σ(Y ) ⊆ {Y }. There, either σ(Y ) = ∅ and aperiodicity becomes trivial, or σ(Y ) = Y and the case was dealt with in the previous point and is thus aperiodic with index k . Now we can end the proof by reasoning by induction on , as if X ∈ σ(X) and all variables Y X are aperiodic with index i, then σi+1 (X) can be written as the concatenation of σi (Y ), for aperiodic variables Y of index i. Then σi+1 (X) = σi+2 (X). We conclude by noticing that the length of the longest chain of is bounded by .

From 1-bounded SST to 2DFT

The existing transformation of a 1-bounded (or even copyless) SST into an equivalent 2DFT goes through MSO transductions, yielding a non-elementary complexity.

We present here an original construction whose complexity is elementary.

Theorem 6. Let T be a 1-bounded SST with n states and m variables. Then we can effectively construct a deterministic 2-way transducer that realizes the same function. If T is 1-bounded (resp. copyless), then the 2DFT has O(m2 m2 m n n ) states (resp. O(mn n )).

Proof. Let T = (A, B, Q, q 0 , Q f , δ, X , ρ, F ) be an SST. Let us construct a two-way transducer A that realizes the same function. The transducer A will follow the output structure (see Figure 3) of T and construct the output as it appears in the structure. To make the proof easier to read, we define A as the composition of a The second transducer uses this information, and enriches the input word with the set of variables corresponding to the variables that will be produced from this position. The last transducer is more interesting: it uses the enriched information to follow the output structure of T .

q i-1 q i a i q i+1 a i+1 q i+2 a i+2 X → aa Z → aZab X → aXc Y → bZ X → XaaY b X i : X o : Y i : Y o : Z i : Z o : • • • • • • • • • • a aa c
The output structure of a run is a labeled and directed graph such that, for each variable X useful at a position j, we have two nodes X j i and X j o linked by a path whose concatenated labels form the value stored in X at position j of the run (see [START_REF] Filiot | First-order definable string transformations[END_REF] and Figure 3). Formally, the output structure of a run q 0 u -→ q n is the oriented graph over X × [1, |u|] × {i, o} whose edges are labeled by output words and are of the form:

• ((X, j, i), v, (Y, j -1, i)) if ρ(q j-1 , a j , X) starts with vY . • ((X, j, o), v, (Y, j -1, i)) if there exists Z such that XvY appears in ρ(q j-1 , a j , Z), • ((X, j, o), v, (Y, j + 1, o)) if ρ(q j-1 , a j , Y ) ends by Xv, • ((X, j, i), v, (X, j + 1, o)) if ρ(q j-1 , a j , X) = v.
We furthermore restrict to the connected component corresponding to the actual output of the run.

The set of variables (added to the input word by A ) will be used to clear the nondeterminism due to the 1-bounded property. Note that in the case of a copyless SST, the transducer A can be omitted. We now explain how the several transducers behave on a given run r = q 0 a1 -→ q 1 . . . (a, q, S) (a , q , S ) we let A = A { }.

(X, i) (Y, i) σ(X) = uY.. (X, o) σ(X) = u (Y, o) σ (Y ) = ..Xu Y ∈ S (X , i) σ (Y ) = ..XuX .. Y ∈ S
The transducer A = (A, A × Q, Q {i , f }, {i }, {f }, δ ), which enriches the input word with the transitions of the previous step, can be done easily with a 1way transducer. The transitions of δ are defined as follows: first, we have i

| --→ q 0 .
Second, we have q σ|(σ,q) ----→ q for all q ∈ Q and σ ∈ A , where q = δ(q, a) if σ ∈ A, and q = f otherwise. Note that one can recover the transition taken by the SST from the letter read and the previous state. Then on the run r, if u = a 1 . . . a n , we get the output word A ( u ) = (a 1 , q 0 )(a 2 , q 1 ) . . . (a n , q n-1 )( , q n ).

The transducer

A = (A × Q, A × Q × 2 X , 2 X {i , f }, {i }, {f }, δ
), which enriches each letter of the input word (except the endmarkers) with the set of variables involved in the final output from this step, can be done with a right-to-left sequential transducer. The last symbol ( , q n ) allows to identify the set of variables appearing in F (q n ). This information can be propagated while getting back in the run of the SST. Formally, the transitions of δ are defined as follows:

             i | --→ i i ( ,q)|( ,q,∅) --------→ {X ∈ X | X appears in F (q)} S (a,q)|(a,q,S) --------→ {X ∈ X | ∃Y ∈ S, X occurs in ρ(q, a, Y )} for all q ∈ Q, a ∈ A S | --→ f
Given the run r of the SST on the input word u, we define S n = F (q n ), and

S i-1 = {X ∈ X | ∃Y ∈ F (q n ) X ∈ σ qi-1,ai...

an (Y )}. Then we get the output word

A • A ( u ) = (a 1 , q 0 , S 1 )(a 2 , q 1 , S 2 ) . . . (a n , q n-1 , S n )( , q n , ∅).
The aim of the third transducer B is to follow the output structure of T . Let B = (A × Q × 2 X , B, P, {p 0 }, {p f }, δ B ) be defined as follows. First, P = (X × {i, o}) {p 0 , p f } is the set of states. The transducer does a first left-to-right reading of the input in state p 0 . The subset X × {i, o} will then be used to follow the output structure while keeping track of which variable we are currently producing. The set {i, o} stands for in and out and corresponds to the similar notions in the output structure. Informally, in states will move to the left, while out states move to the right. The states p 0 and p f are new states that are respectively initial and final.

The transition function δ B is detailed below (see also Figure 4). In the following, we consider that the transducer is in state p reading the triplet t = (a, q, S) ∈ A × Q × 2 X , or one of the endmarkers:

• If p = p 0 and a = , then we set δ B (p 0 , t) = ( , p 0 , +1).

• If p = p 0 and a = , then if F (q) starts by uX with u ∈ B * and X ∈ X , then δ B (p, t) = (u, (X, i), -1). • If p = (X, i), and t = then:

either ρ(q, a)(X) = u ∈ B * and does not contain any variable, and we set δ B (p, t) = (u, (X, o), +1), or ρ(q, a)(X) starts by uY with u ∈ B * and Y ∈ X , then δ B (p, t) = (u, (Y, i), -1).

• If p = (X, i), and t = then δ B (p, t) = ( , (X, o), +1).

• If p = (X, o) and a = , then let Y be the unique variable of S such that X appears in ρ(q, a)(Y ). Then we have:

either ρ(q, a)(Y ) ends by Xu with u in B * and we set δ B (p, t) = (u, (Y, o), +1), or ρ(q, a)(Y ) is of the form (B ∪ X ) * XuX (B ∪ X ) * and we set δ B (p, t) = (u, (X , i), -1).

Note that the unicity of such Y in S is due to the 1-boundedness property. If T is copyless, then this information is irrelevant and A can be bypassed. • If p = (X, o), q ∈ Q f and a = then:

either F (q) ends by Xu with u in B * and we set δ B (p, t) = (u, p f , +1), or F (q) is of the form (B ∪ X ) * XuX (B ∪ X ) * and we set δ B (p, t) = (u, (X , i), -1).

Then we can conclude the proof as T = B • A • A and 2-way transducers are closed under composition [START_REF] Chytil | Serial composition of 2-way finite-state transducers and simple programs on strings[END_REF].

Regarding complexity, a careful analysis of the composition of a one-way transducer of size m with a two-way transducer of size n from [START_REF] Dartois | Méthodes algébriques pour la théorie des automates[END_REF][START_REF] Carton | Aperiodic two-way transducers and fo-transductions[END_REF] shows that this can be done by a two-way transducer of size O(nm m ). Then given a 1-bounded SST with n states and m variables, we can construct a deterministic two-way transducer of size

O(m(2 m ) 2 m n n ) = O(m2 m2 m n n ).
If T is copyless, the sequential right-to-left transducer can be omitted, and the resulting 2DFT is of size O(mn n ).

Theorem 7. Let T be an aperiodic 1-bounded SST. Then the equivalent 2DFT constructed using Theorem 6 is also aperiodic.

Proof. We prove separately the aperiodicity of the three transducers. Then the result comes from the fact that aperiodicity is preserved by composition of a oneway by a two-way [START_REF] Carton | Aperiodic two-way transducers and fo-transductions[END_REF].

First, consider the transducer A . It is a one-way transducer that simply enriches the input word with transitions from T , each enrichment corresponding to the transition taken by T in the previous step. Then since T is aperiodic, so is its underlying automaton. Then the enrichment and thus A are aperiodic.

Secondly, given an input word, the transducer A stores at each position the set of variables that will be output by T . Now as T is aperiodic, the flow of variable is aperiodic. Thus the value taken by this set is aperiodic and so is A . Now, consider the transducer B and a run r of B on u n starting in state p. Note that the fact that there exists a run on an enriched input word v implies that it is well founded, meaning that it is the image of some word of A * by A • A . If p is of the form (X, i), then the run starts from the right of u n and follows the substitution σ r (X). It exits u n either in state (X, o) on the right if σ r (X) is a word of B * , or in a state (Y, i) on the left where Y is the first variable appearing in σ r (X). In both cases the state at the end of the run only depends on the underlying automata of T and the order of variables appearing in the substitution induced by the run. Since the substitution transition monoid is aperiodic if T is aperiodic by Theorem 4, a similar run exists on u n+1 .

Finally, if p is of the form (X, o), then the state in which the run exits u n depends on the unique variable Y such that X belongs to σ r (Y ) and Y belongs to the set of variables of the last letter of the input. Then the run follows the substitution σ r (Y ). It will exit the input word in state (X , i) on the left if X appears in σr (Y ) for some variable X and in state (Y, o) otherwise. As the flow of variable as well as the underlying automaton are aperiodic, a similar run exists on u n+1 .

We conclude the proof by noticing that the same arguments will hold to reduce runs on u n+1 to runs on u n .

From 2DFT to copyless SST

In [START_REF] Alur | Expressiveness of streaming string transducers[END_REF], the authors give a procedure to construct a copyless SST from a 2DFT. This procedure uses the intermediate model of heap based transducers. We give here a direct construction with similar complexity. This simplified presentation allows us to prove that the construction preserves the aperiodicity. Theorem 8. Let T be a 2DFT with n states. Then we can effectively construct a copyless SST with O((2n) 2n ) states and 2n -1 variables that computes the same function.

The main idea is for the constructed SST T to keep track of the right-to-right behavior of the prefix read until the current position, similarly to the construction of Shepherdson [15]. This information can be updated upon reading a new letter, constructing a one-way machine recognizing the same input language. The idea from [START_REF] Alur | Regular transformations of infinite strings[END_REF] is to have one variable per possible right-to-right run, which is bounded by the number of states. However, since two right-to-right runs from different starting states can merge, this construction results in a 1-bounded SST. To obtain copylessness, we keep track of these merges and the order in which they appear. Different variables are used to store the production of each run before the merge, and one Ap2w-SST 14 Dartois, Jecker and Reynier a u q 5 q 5 q 4 q 4 q 3 q 3 q 2 q 2 q 1 q 1 more variable stores the production after.

q 0 q 0 • • • ⇒ ua q 5 q 4 q 3 q 2 q 1 q 0 • •
The states of T are represented by sets of labeled trees having the states of the input 2DFT as leaves. Each inner vertex represents one merging, and two leaves have a common ancestor if the right-to-right runs from the corresponding states merge at some point. Each tree then models a set of right-to-right runs that all end in a same state. Note that it is necessary to also store the end state of these runs. For each vertex, we use one variable to store the production of the partial run corresponding to the outgoing edge.

Given such a state and an input letter, the transition function can be defined by adding to the set of trees the local transitions at the given letter, and then reducing the resulting graph in a proper way (see Figure 5).

Finally, as merges occur upon two disjoint sets of states of the 2DFT (initially singletons), the number of merges, and consequently the number of inner vertices of our states, is bounded by n -1. Therefore, an input 2DFT with n states can be realized by an SST having 2n -1 variables. Finally, as states are labeled graphs, Cayley's formula yields an exponential bound on the number of states.

The remainder of the section is dedicated to give a formal proof of this intuition. Subsection 5.1 describes the merging forests that are the states of the SST, and Subsection 5.2 proves complexity bounds on the size of these objects. These bounds are then used in Subsection 5.3 to precisely define the substitution function. The formal construction is presented in Subsection 5.4 and its aperiodicity proved in Subsection 5.5.

Merging forests

Let T = (A, B, Q, q 0 , F, δ) be a 2DFT. We suppose that the transducer T starts to read its input from the end, and not from the beginning, i.e., given an input w, the initial configuration is (q 0 , |w| + 1). Moreover, we also assume that T produces no output while reading the symbol , i.e., for any every p ∈ Q, δ(p, ) = ( , q, +1) for some q ∈ Q. Note that any 2DFT can be transformed with ease into a transducer satisfying those two properties.

For every word w over the alphabet Ā * , we expose a pair (G w , φ w ) that contains the information concerning the right-to-right runs of T on the input word w, and their mergings. It is composed of a forest G w whose branches represent right-toright runs and vertices represent merging of such runs, and an injective function φ w that maps the root of each tree of G w , representing a set of merging runs, to an element of Q, corresponding to the final state of these right-to-right runs.

In order to represent mergings, we use rooted forests whose vertices are included into 2 Q \ ∅. A merging between the right-to-right runs starting from two states q 1 and q 2 is expressed by adding an edge from both {q 1 } and {q 2 } towards {q 1 , q 2 }. Then, if a third run starting from state {q 3 } merges with them later on, an edge is added from both {q 1 , q 2 } and {q 3 } towards 1 , q 2 , q 3 }. Formally, we will use the set F Q of rooted forests G satisfying the following properties.

• The vertices of G are non empty subsets of Q.

• The roots of G are disjoint subsets of Q.

• For every vertex s of G, the sons of s are disjoint proper subsets of s.

Note that, as a direct consequence of those properties, there exists no pair of distinct forests of F Q that share the same set of vertices. Therefore, in order to define an element of F Q , it is enough to expose its set of vertices.

In order to ensure that the pair (G w , φ w ) accurately represents the behavior of T on w , we want the two following properties to be satisfied. For every state q ∈ Q that appears in a vertex of G w , let r q ∈ 2 Q denote the root of the forest G w that contains q. P 1.1 The vertices of G w are the sets s ⊆ Q such that the right-to-right runs of T on w starting in a state belonging to s merge at some point, before merging with any other. P 1.2 For all (p, q) ∈ bh rr ( w), we have φ w (r p ) = q.

We begin by defining (G , φ ). For every q ∈ Q, let δ -1 (q) ⊆ Q denote the set of states p such that δ(p, ) = ( , q, +1). Let G be the graph of F Q whose set of vertices is composed of the singletons {p}, and the sets δ -1 (q) that are not empty. Moreover, let φ be the function mapping each root δ -1 (q) of G to q ∈ Q. Then both P 1.1 and P 1.2 are satisfied for w = . Now, given w ∈ Ā * , a ∈ Ā, and a pair (G w , φ w ) satisfying the properties for w, we expose the construction in three steps of the pair (G wa , φ wa ) satisfying the properties for wa. First, we build a graph G wa by adding to G w edges corresponding to the function φ w . Second, we build a graph G wa by adding to G wa the local transitions induced by the letter a. Finally, since the intermediate graph G wa is not an element of F Q , we shrink it into a new graph G wa ∈ F Q . The reduction of this last step is depicted by Figure 5, while the copy Q i of the second step appear in red on the left picture.

• Let G wa = (V wa , E wa ) be the graph defined by

V wa = V w ∪ Q i ,
E wa = E w ∪ {(φ -1 w (p), p i ) ∈ 2 Q × Q i |p ∈ Im(φ w )}. • Let G wa = (V wa , E wa ) be the graph defined by V wa = V wa ∪ Q o , where Q o
is a copy of the set Q, and let

E wa = E wa ∪ {(p i , τ (p)) ∈ Q i × V wa |p ∈ Q},
where τ is defined as follows. For every q ∈ Q, let s q denote the smallest vertex of G w containing q. Then, for every p ∈ Q,

τ (p) =    q o ∈ Q o if δ(p, a) = (q, +1); q i ∈ Q i if δ(p, a) = (q, 0); s q ∈ V w if δ(p, a) = (q, - 1).
• By definition of G wa , for every vertex s ∈ V wa there exists at most one path r s between s and a vertex q o ∈ Q o . Let out : V wa → Q ∪ {⊥} be the function mapping s ∈ V wa to ⊥ if there exists no such path, and to the state q ∈ Q corresponding to the target of r s otherwise. Let in : V wa → 2 Q be the function mapping each vertex s of G wa to the set in(s) of states q ∈ Q such that out(q i ) = ⊥ and the path r q i goes through s. Let G wa ∈ F Q , be defined by its set of vertices V wa = {in(s) ⊂ Q|s ∈ V wa , in(s) = ∅, and out(s) = ⊥}, and let φ wa be the function mapping each root in(s) of V wa to out(s) ∈ Q.

We prove that the pair (G wa , φ wa ) satisfies the desired properties.

Lemma 9. The set of vertices V wa corresponds to a graph G wa ∈ F Q . Moreover, the pair (G wa , φ wa ) satisfies P 1.1 and P 1.2 for wa.

Proof. By definition of V wa , the vertices of G wa are non empty subsets of Q. Therefore, in order to show that the set of vertices V wa corresponds to a graph G wa ∈ F Q , it is sufficient to show that for every pair of vertices of V wa that are not disjoint, one is included into the other. Let s 1 , s 2 ∈ V wa . If s 1 and s 2 are not disjoint, let s ∈ s 1 ∩ s 2 , let s 1 ∈ V wa denote the state such that in(s 1 ) = s 1 and let s 2 ∈ V wa denote the state such that in(s 2 ) = s 2 . Then there exists a run r s in G wa between q i and an element q o ∈ Q o that goes through s 1 and s 2 . If s 1 appears earlier, s 1 ⊆ s 2 , and if s 2 appears earlier, s 2 ⊆ s 1 . This proves the desired result. Now consider a vertex s of G wa . By construction, this means that all runs starting from the right on wa in a state q of s end in the same state p. This particularly means that all these runs merge, thus we only have to prove that they merge together before potentially merging with another run. To this end, assume that there exists a state p not present in s, and two states p 1 and p 2 of s such that p merges with p 1 before p 1 merges with p 2 . Then either the merging appears while processing w and by induction there is a contradiction, or the mergings appear on a, but by construction of G wa , this would imply that there is a state containing p and p 1 but not p 2 . Hence in both cases we get a contradiction and property P 1.1 is satisfied.

Finally, we show that P 1.2 is satisfied. By the induction hypothesis, G w satisfies P 1.2 , hence for all (p 1 , q 1 ) ∈ bh rr ( w), we have φ w (s p1 ) = q 1 , where s p1 is the root of G w containing p 1 . Moreover, since G w ∈ F Q , there is a path in G w between p 1 and s p1 . Therefore, by definition of G wa , there is a path in G wa between p 1 and q i

1 . Then, by definition of G wa , for every (p 2 , q 2 ) ∈ bh rr ( wa), there is a path r in G wa between p i 2 and q o 2 . By definition of G wa , in(p i 2 ) ∈ 2 Q is a vertex of G wa that contains p 2 . Let s p2 be the root of G wa that contains p 2 , and let s ∈ V wa be the state such that in(s ) = s p2 . By definition of in, the path r goes through s . Since q o 2 is the target of r, φ wa (s p2 ) = out(s ) = q 2 , which proves that P 1.2 is satisfied.

Remark 10. Since the construction of G wa only depends on G w and a, for every

w ∈ Ā * , if G w = G w then G w a = G wa .

Bounded size complexity

The next results will allow us to obtain the bound over the size of the set of states presented in the statement of Theorem 8.

Lemma 11. Every rooted forest G = (V, E) in F Q has at most 2|Q| -1 vertices.

Proof. The proof is by induction on the size of Q.

If |Q| = 1, |2 Q \ ∅| = 1, hence |V | 1 = 2|Q| -1. Now suppose that |Q| > 1,
and that the result is true for every set Q such that |Q | < |Q|. Let G be the graph obtained by removing all the roots of G. Then G is a union of trees

G 1 = (V 1 , E 1 ), G 2 = (V 2 , E 2 ), . . . , G m = (V m , E m ).
For every 1 i m, the forest G i is an element of F si , where s i ⊂ Q denotes the root of G i . Therefore, by using the induction hypothesis, we have

|V | = 1 + |V 1 | + |V 2 | + . . . + |V m | 1 + (2|s 1 | -1) + (2|s 2 | -1) + . . . + (2|s m | -1) = 2(|s 1 | + . . . + |s m |) + 1 -m 2|Q| -1.
Lemma 12. Let n = |Q|. The size of F Q is smaller than or equal to (2n) 2n-2 (n-2)! .

Proof. By Cayley's Formula, there exist exactly (2n) 2n-2 labeled trees on 2n vertices. If we only label n+2 elements, we gain n-2 degrees of liberty and hence there is only (2n) 2n-2 (n-2)! such trees. We prove that we can injectively project the elements of F Q into trees with 2n vertices and n + 2 labels, proving the bound.

Given an element G = (V, E) of F Q , we know that |V | 2n -1 by Lemma 11. Let G be the tree on 2n vertices obtained by adding to G a vertex s ⊥ , an edge from each root of G to s ⊥ , and, if |V | < 2n -1, a linear path composed of 2n -|V | -1 new vertices starting from a vertex s , and whose end is linked to s ⊥ . Now for each state q of Q, let s q be the smallest in terms of inclusion of labels vertice of V that contains q, if it exists. Then each vertex of G corresponding to a vertex s q is labeled s q , and for all q in Q that do not appear in a vertex of V , we label one element of the linear path under s by q. We can assign a different element to all such q by Lemma 11, since q not appearing is equivalent to having V on a smaller set of states.

Thus we proved that G can indeed be embedded into a tree with 2n vertices and n + 2 labels (we added the s ⊥ and s labels). We conclude the proof by showing that the projection is injective. Note that all leaves of G are a vertex s q for some q, and that if all s q are fixed, then the label of a vertex in G which is not a state s q is simply the union of the labels of its sons. Then two different forests will be embedded into two different trees, proving injectivity.

Substitution function

As a consequence of Lemma 11, for every word w ∈ Ā * , the graph G w = (V w , E w ) admits an injective vertex labeling λ w : V w → X , where X = (X 1 , . . . , X 2|Q|-1 ) is a set containing 2|Q|-1 variables. We now present, for every w ∈ A * , the construction of a substitution σ w ∈ S X ,B that will allow us, together with the graph G w and its vertex labeling λ w , to describe the output production of the right-to-right runs of T on the input word w. Formally, for every (p, q) ∈ bh rr ( w), let w p,q ∈ B * denote the production of the corresponding right-to-right run. Moreover, for every vertex s of G w , let λw (s) denote the concatenation of the λ-labels of the vertices forming the path between s and the root of the corresponding tree in G w , and for every state q ∈ Q that appears in at least one vertex of G w , let s q ∈ 2 Q be the vertex of G w of minimal size such that q ∈ s q . We want the following property to be satisfied. P 2 For all (p, q) ∈ bh rr ( w), we have (σ w )( λw (s p )) = w p,q .

Let σ be the substitution mapping every variable to . By supposition, for every p ∈ Q, we have δ(p, ) = ( , q, +1) for some q ∈ Q. Therefore P 2 is satisfied for . Now, given w ∈ Ā * , a ∈ Ā, and a substitution σ w satisfying P 2 for w, we expose the construction in three steps of a copyless substitution σ w,a such that the composition σ wa = σ w • σ w,a satisfies P 2 for wa. First, we extend the labeling λ w of V w to a labeling µ wa : V wa → X ∪ B * of G wa . Second, we reduce it into a labelling µ wa : V wa → (X ∪ B) * of G wa . Then, σ w,a is defined as the substitution mapping λ wa (s) to µ wa (s).

• Let µ wa : V wa → X ∪ B * be the substitution mapping s ∈ V w to λ w (s), q o ∈ Q o to , and p i ∈ Q i to the word w ∈ B * satisfying δ(p, a) = (w , q, m). • For every t ∈ V wa , the set V t of vertices s of G wa such that t = in(s) is not empty, and they form a path s 1 , . . . , s m such that s 1 ∈ Q i ⊆ V wa . Let µ wa (t) = µ wa (s 1 ) . . . µ wa (s m ).

• For every X ∈ X , let σ w,a (X) = if no state s ∈ V wa is mapped to X by λ wa , and let σ w,a (X) = µ wa (s) for some state s ∈ V w satisfying λ wa (s) = X otherwise. Since λ wa is injective, the function σ w,a is well-defined.

We prove that σ wa satisfies the desired properties.

Lemma 14. The substitution σ w,a is copyless and σ w • σ w,a satisfies P 2 for wa.

Proof. We prove that σ w,a is copyless by contradiction. Suppose that there exists a variable X ∈ X that appears twice in σ w,a (Y ) for some Y ∈ X , or that appears in the image of two distinct variables Y 1 , Y 2 ∈ X by σ w,a . Then, by definition of σ w,a , X appears twice in µ wa (s) for some vertex s ∈ V wa , or X appears in the image of two distinct vertices s 1 , s 2 ∈ V wa by µ wa . Therefore, by definition of µ wa , there exist two distinct vertices s 1 , s 2 ∈ V wa such that λ w (s 1 ) = µ wa (s 1 ) = X = µ wa (s 2 ) = λ w (s 2 ). This is not possible, since λ w is injective. We now prove that P 2 is satisfied. Let μwa (s) (resp. μ wa (s)) denote the concatenation of the labels of the vertices forming the path starting from a vertex s of G wa (resp. G wa ) and ending at the corresponding root. Since P 2 is satisfied for w by supposition, for every (p, q) ∈ bh rr (wa) we have, by definition of G wa , σ w (μ wa (in(p i ))) = σ w (μ wa (p i )) = w p,q . Note that σ wa = σ w • σ w,a , in(p i ) is equal to the smalles vertex s p of V wa containing p, and σ w,a (λ wa (s p )) = µ wa (s p ). We obtain σ wa ( λwa (s p )) = σ w (μ wa (in(p i ))) = w p,q . This proves that P 2 is satisfied for wa.

Remark 15. Since the construction of σ w,a only depends on G w and a, for every w ∈ Ā * , if G w = G w then σ w ,a = σ w,a .

Construction

We now have all the ingredients to define formally a copyless SST T = (A, B, Q , q 0 , Q f , α, X , β, F ) equivalent to T . Recall that we assumed that the 2DFT T read its input starting from the right, and that nothing was produced on the initial marker . Let

• Q = {(G w , φ w )|w ∈ A * }; • q 0 = (G , φ ); • Q f = {(G w , φ w )|φ w (r q0 ) ∈ F }; • α : Q × A → Q , ((G w , φ w ), a) → (G wa , φ wa ); • X = {X i |1 i 2|Q| -1}; • β : Q × A → S X ,B
, ((G w , φ w ), a) → σ w,a ; • F : Q f → (X ∪ B) * , (G w , φ w )) → σ w, ( λw (s q0 )).

Note that the functions α and β are well-defined as a consequence of the remarks 10 and 15. For every input word w ∈ A * , as a direct consequence of the definitions of α and β, the state reached by T on input w is G w , and the substitution induced to a sequence s 0 . . . s k of vertices of G u . Should we forget about the production, σ w,a (λ wa (s)) corresponds to λ w (s 0 ) . . . λ w (s k ). Thanks to Lemma 18, we know that w n and w n+1 are merge equivalent. Then given a state G u and one of its vertex, it will correspond to the same vertex after reading w 2n or w 2n+1 . Since we have a unique way of mapping vertices to variables, the substitutions σ uw 2n and σ uw 2n+1 will be equal when production is erased, proving the aperiodicity of the substitution function.

As a corollary, we obtain that the class of aperiodic copyless SST is expressively equivalent to first-order definable string-to-string transductions.

Corollary 21. Let f : A * → B * be a function over words. Then f is realized by a FO graph transduction iff it is realized by an aperiodic copyless SST.

From k-bounded to 1-bounded SST

The existing construction from k-bounded to 1-bounded, presented in [START_REF] Alur | Regular transformations of infinite strings[END_REF], builds a copyless SST. We present an alternative construction that, given a k-bounded SST, directly builds an equivalent 1-bounded SST. We will prove that this construction preserves aperiodicity.

Theorem 22. Given a k-bounded SST T with n states and m variables, we can effectively construct an equivalent 1-bounded SST. This new SST has n2 N states and mkN variables, where N = O(n n (k + 1) nm 2 ) is the size of the flow transition monoid M T .

Proof. In order to move from a k-bounded SST to a 1-bounded SST, the natural idea is to use copies of each variable. However, we cannot maintain k copies of each variable all the time: suppose that X flows into Y and Z, which both occur in the final output. If we have k copies of X, we cannot produce in a 1-bounded way k copies of Y and k copies of Z. We will thus limit, for each variable X, the number of copies of X we maintain. In order to get this information, we will use a look-ahead information on the suffix of the run.

The proof relies on the following fact: suppose that we know at each step what is the substitution induced by the suffix of the run. From this substitution, we know how many copies of each variable X will be involved in the final output. We can thus copy each variable sufficiently many times and use them to produce this substitution in a copyless fashion.

One can observe that there are finitely many substitutions, this information being held in the transition monoid of the SST. Then we can compute, at each step and for each possible substitution, a copyless update. But as a given element of the monoid may have several successors, the update function flows variables from one element to variables of several elements. As these variables are never recombined, we get the 1-boundedness of the construction.

Fig. 1 :

 1 Fig. 1: Summary of transformations between equivalent models. k-b. stands for k-bounded.

Fig. 3 :

 3 Fig.3: The output structure of a partial run of an SST used in the proof of Theorem 6.

  an --→ q n . To ease the notations, March 8, 2018 13:0 WSPC/INSTRUCTION FILE Ap2w-SST Aperiodic String Transducers 11 u :

Fig. 4 :

 4 Fig. 4: The third transducer follows the output structure. States indexed by i correspond to the beginning of a variable, while states indexed by o correspond to the end. σ (resp. σ ) stands for the substitution at position a (resp. a ).

Fig. 5 :

 5 Fig. 5: Left: The state of the SST is represented in black. The red part corresponds to the local transitions of the 2DFT. Right: After reading a, we reduce the new forest by eliminating the useless branches and shortening the unlabeled linear paths.

Corollary 13 .

 13 Let n = |Q|. The size of {(G w , φ w )|w ∈ Ā * } is smaller than or equal to (2n) 2n . Proof. For every w ∈ Ā * , since φ w is an injective function mapping the trees of G w to Q and G w contains at most n trees, we have |{(G w , φ w )|w ∈ Ā * }| n!|F Q | (2n) 2n .

  where Q i is

	March 8, 2018 13:0 WSPC/INSTRUCTION FILE	Ap2w-SST
	16 Dartois, Jecker and Reynier
	a copy of the set Q, and

Dartois, Jecker and Reynier

Dartois, Jecker and Reynier

* This work is supported by the ARC project Transform (French speaking community of Belgium), the Belgian FNRS PDR project Flare, the PHC project VAST (35961QJ) funded by Campus France and WBI, and the DeLTA project (ANR-16-CE40-0007).

Ap2w-SST 20 Dartois, Jecker and Reynier by the corresponding run is σ w . Therefore, by P 1.1 and the definition of P f , the domains of the function f T defined by T and the function f T defined by T are identical. Moreover, by P 2 and the definition of F , the image of a given word by those two functions are identical, hence the functions are the same.

Aperiodicity of the construction

We now prove that this construction preserves aperiodicity:

Theorem 16. Let T be an aperiodic 2DFT. Then the equivalent SST constructed using Theorem 8 is also aperiodic.

To prove this theorem, we introduce a new equivalence relation ∼ m , and we prove that the aperiodicity of the 2DFT T implies the aperiodicity of this relation, which in turn implies the aperiodicity of the SST T . We say that two words v and w are merge equivalent (v ∼ m w) if both v and w induce the same merges in the same order, and bh xy (v) = bh xy (w) for every x, y ∈ {r, }.

Proof. This follows from the fact that for every word u ∈ Ā * , the graph G uv represents the merges of the right-to-right runs of T on uv, and these runs can be decomposed into right-to-right runs on u, and partial runs on v.

Lemma 18. Let w ∈ Ā * be such that w n ∼ T w n+1 . Then w 2n ∼ m w 2n+1 .

Proof. Let w and n be such that w n ∼ T w n+1 . Given a run r on w 2n+1 , if ρ is left-to-left or right-to-right, it never reaches the middle iterations of w in w 2n+1 . Moreover, if r is left-to-right or right-to-left, it reaches exactly once the middle iteration of w in w 2n+1 , which it crosses while staying in the same state. This proves that, on input w n+1 , runs are only merging in the leftmost and rightmost n iterations of w, and they merge in the same order in w 2n .

The two following lemmas now conclude the proof, since the aperiodicity of both the underlying automaton and the substitution imply the aperiodicity of the whole SST.

Proof. This follows directly from Lemma 18 and Lemma 17.

Proof. By construction, reducing the graph G ua to G ua amounts to deleting the unnecessary information from G u , i.e. deleting cycles and reducing paths with no new merges to a single vertex. Therefore, each vertex s from G ua can be traced back Ap2w-SST 22 Dartois, Jecker and Reynier Let T = (A, B, Q, q 0 , Q f , δ, X , ρ, F ) be an aperiodic k-bounded SST, M T be its transition monoid, and η T : A * → M T be its transition morphism.

We construct T = (A, B, Q , q 0 , Q f , δ , X , ρ , F ) where:

• The set of states Q = Q× P(M T ) is the current state plus a set of elements of M T corresponding to the possible images of the current suffix. • q 0 = (q 0 , S 0 ) where

possible images of input words. Here, we are abusing notations as δ(q, m) stands for δ(q, u) where η T (u) = m. By definition of the transition monoid, we have that η T (u) = η T (v) implies δ(q, u) = δ(q, v), thus this is well defined.

), a) = (q , S ) where q = δ(q, a) and

Variables from X will be denoted X m i for X ∈ X , i k and m ∈ M T .

• The variable update function is defined as follows. First given a state q of T and an element m of M T , we define σq,m as the projection of the output substitution induced by a run starting on q on a word whose image is m, i.e σq,u = γ(q, u) • F (δ(q, u)) for η T (u) = m. Note that by definition of the transition monoid of an SST, it is well defined. Now consider a transition (q, S) a -→ (q , S ). For any s ∈ S and 0 < i |σ q ,s | X , ρ ((q, S), a, X s i ) is defined similarly to ρ(q, a, X), but all variables are labeled by the element η T (a)s from S and they are all distinct copies to ensure the 1-bounded property. Such a numbering is possible thanks to the fact that s indicates which variables are used as well as how many times. This allows us to copy each variables the right amount of times, using different copies at each occurrence. The k-bounded property then ensures that we will never need more than k variables for a possible output.

• F : Q f → (B ∪ X ) * is defined as follows. Let (q, S) ∈ Q f . The string F (q, S) is obtained from the string F (q) by substituting each variable X by a variable X n i , where 0 < i |F (q)| X and n = 1 M T .

Theorem 23. Let T be an aperiodic k-bounded SST. Then the equivalent 1-bounded SST constructed using Theorem 22 is also aperiodic.

Proof. We now have to prove that T is aperiodic. By construction of T , we have that the runs of T are of the form (q, S) u -→ (q , S ) where q u -→ T q and S = {n ∈ M T | η T (u)n ∈ S}. The update for such a run is then the update of T over the run q u -→ T q , where variables are labeled by elements from S and S and numbered accordingly. Then as T is aperiodic, the Q part of the run is also aperiodic by construction. The other part computes sets of runs according to M T , which is also aperiodic. Then T will also be aperiodic as the set S only depends on the image of the word read, and by definition η T (u n ) = η T (u n+1 ) for n large enough.

Aperiodic String Transducers 23

As a corollary, we obtain that for the class of aperiodic bounded SST is expressively equivalent to first-order definable string-to-string transductions.

Corollary 24. Let f : A * → B * be a function over words. Then f is realized by a FO graph transduction iff it is realized by an aperiodic k-bounded SST (k ∈ N >0 ).

Perspectives

There is still one model equivalent to the generic machines whose aperiodic subclass elude our scope yet, namely the functional two-way transducers, which correspond to non-deterministic two-way transducers realizing a function. To complete the picture, a natural approach would then be to consider the constructions from [START_REF] Souza | Uniformisation of two-way transducers[END_REF] and prove that aperiodicity is preserved. One could also think of applying this approach to other varieties of monoids, such as the J -trivial monoids, equivalent to the boolean closure of existential first-order formulas BΣ 1 [<]. Unfortunately, the closure of such transducers under composition requires some strong properties on varieties (at least closure under semidirect product) which are not satisfied by varieties less expressive than the aperiodic. Consequently the construction from SST to 2DFT cannot be applied. On the other hand, the other construction could apply, providing one inclusion. Then an interesting question would be to know where the corresponding fragment of logic would position.


Rubén Martín-Clemente

Vicente Zarzoso
email: zarzoso@i3s.unice.fr

Unsupervised Classification of Array Data Based on the L1-Norm

L1-norm criteria have been the subject a flurry of research in signal processing and machine learning over the last decade, especially due to their ability to exploit the sparsity of latent variables and their robustness in the presence of faulty data. Among such criteria, L1-norm principal component analysis (L1-PCA) has drawn considerable attention, resulting in a variety of optimization algorithms and connections with other data processing techniques such as independent component analysis. The present contribution takes a step forward in the characterization of L1-PCA by exploring its linear discrimination capabilities. A variant of L1-PCA consisting of L1-norm maximization subject to an L2-norm constraint is put forward for unsupervised classification. The discrimination properties of the proposed L1-PCA variant are demonstrated through a number of computer experiments.

I. INTRODUCTION

Data analysis techniques based on the L1 norm have become ubiquitous in signal processing and machine learning. Indeed, L1-norm costs arise as natural criteria for exploiting the underlying sparsity in many real-world problems and present increased robustness to faulty data as compared with traditional L2-norm based techniques such as second-order principal component analysis (L2-PCA) [START_REF] Jolliffe | Principal Component Analysis[END_REF].

A remarkable L1-norm approach is L1-PCA [START_REF] Kwak | Principal component analysis based on L1-norm maximization[END_REF], [START_REF] Markopoulos | Optimal algorithms for L1-subspace signal processing[END_REF]. While behaving like L2-PCA in many situations, L1-PCA offers enhanced immunity against outliers as well as an interesting flexibility in analyzing data patterns. These advantages come at the expense of numerical complexity, as the absolute value is difficult to treat mathematically, making the optimization of L1-norm criteria more computationally demanding than that of traditional L2-norm criteria. To alleviate this difficulty, a number of optimal and suboptimal algorithms have been proposed for computing L1-PCA [START_REF] Kwak | Principal component analysis based on L1-norm maximization[END_REF], [START_REF] Markopoulos | Optimal algorithms for L1-subspace signal processing[END_REF], [START_REF] Markopoulos | Efficient L1-norm principal-component analysis via bit flipping[END_REF].

Although increasing complexity, the absolute value nonlinearity confers great potential to this technique. The nonlinearity introduces higher-order statistics in the cost function, implying, in particular, that L1-PCA can perform independent component analysis (ICA) in a robust manner under rather general assumptions [START_REF] Martín-Clemente | On the link between L1-PCA and ICA[END_REF]. This finding opens interesting possibilities for the use of L1-PCA in application scenarios for which it was not originally conceived, as the technique yields meaningful results under different underlying data models.

V. Zarzoso is a member of the Institut Universitaire de France.

Motivated by the flexibility of this technique, the present work investigates for the first time L1-PCA in a data classification framework. Traditional L2-PCA has been used in unsupervised classification tasks, a fundamental data analysis problem. Unsupervised classification aims at allocating an observed feature vector to one of different classes according to a decision rule based on some proximity criterion. In the fundamental two-class (or binary) case, projecting the observed samples in the direction that maximizes the projected data variance, i.e., applying L2-PCA, can perform unsupervised classification when the data form two well-separated clusters. As a prime example, the Eigenfaces method for face recognition is largely based on this property [START_REF] Turk | Eigenfaces for recognition[END_REF], [START_REF] Martinez | PCA versus LDA[END_REF]. Inspired by this result, we move forward in the characterization of L1-PCA by analyzing its discrimination capabilities. An L1-PCA variant is proposed that is able to carry out unsupervised classification, much like its L2-norm counterpart but with increased discrimination properties and robustness to outliers. These results are justified using intuitive arguments and supported by several numerical experiments.

II. PROBLEM FORMULATION

This section summarizes the main assumptions and mathematical notations used throughout the paper. Then L2-PCA and L1-PCA are recalled, as well as the linear discrimination properties of the former. These inspire the search for analogous properties in L1-norm criteria.

A. Assumptions and Notations

The data analysis techniques considered in this paper assume the observation of N samples x 1 , x 2 , . . . , x N drawn from a d-dimensional random variable x 2 R d . For simplicity, it is assumed that {x n } N n=1 has zero sample mean. In the sequel, we use the standard definitions of the L1-norm and the L2-norm, respectively, of an N -dimensional vector y 2 R N :

kyk 1 = N X n=1 |y n | k yk 2 = v u u t N X n=1 y 2 n ! . (1)
Also, symbol

B. L2-PCA

We first recall the traditional L2-PCA. Its goal is to find a direction a 2 R d , kak 2 = 1, such that the projected samples

y n = a > x n (2)
have maximum dispersion as measured by variance. This is also the linear projection best fitting the data in the leastsquares sense [START_REF] Jolliffe | Principal Component Analysis[END_REF]. By defining the vector of projected samples as y = [y 1 , y 2 , . . . , y N ] > , the problem takes in practice the following form:

max kak2=1 kyk 2 = max kak2=1 N X n=1 a > x n 2 (3)
where we are using the sample variance instead of the population variance to introduce the optimization criterion. By defining the d⇥N sample matrix as X = [x 1 , . . . , x N ], we can write y = X > a, and the above criterion accepts the equivalent matrix formulation:

max kak2=1 kX > ak 2 .
Simple algebra shows that this optimization problem is solved by the eigenvector associated with the largest eigenvalue of the data sample covariance matrix

C x = XX > . (4)

C. L1-PCA

A major problem with the above technique is that the square in (3) tends to overemphasize large outliers and L2-PCA inherits this sensitivity to faulty data. To overcome this drawback, the square function can be replaced by the absolute value, as proposed in [START_REF] Kwak | Principal component analysis based on L1-norm maximization[END_REF], thus yielding the following criterion:

max kak2=1 kyk 1 = max kak2=1 kX > ak 1 . (5)
PCA based on criterion ( 5) is usually referred to as L1-norm based PCA or, simply, L1-PCA. The absolute value in eqn. ( 5) endows L1-PCA with an increased robustness to outliers as compared to L2-PCA.

The main difficulty with L1-PCA lies in the optimization of its cost function, which requires the development of specific algorithms. A cost-effective though suboptimal method is proposed by Kwak [START_REF] Kwak | Principal component analysis based on L1-norm maximization[END_REF], who proves that the following fixedpoint iteration:

1

) y = X > a i 2) a i+1 = X sign(y) kX sign(y)k 2
where a i represents the update of a at the ith iteration, monotonically increases the L1-norm criterion kyk 1 after each step, and so the algorithm converges at least to a local maximum. The most notable feature of this simple method is that no parameters need to be tuned. Alternatively, one can use the polynomial time approaches in [START_REF] Allemand | A polynomial case of unconstrained zero-one quadratic optimization[END_REF], [START_REF] Ben-Ameur | A polynomial-time recursive algorithm for some unconstrained quadratic optimization problems[END_REF], [START_REF] Ferrez | Solving the fixed rank convex quadratic maximization in binary variables by a parallel zonotope construction algorithm[END_REF]. L1-PCA algorithms with guaranteed convergence to a global maximum have also been proposed, although they come at the expense of increased computational complexity [START_REF] Markopoulos | Optimal algorithms for L1-subspace signal processing[END_REF], [START_REF] Karystinos | Efficient computation of the binary vector that maximizes a rank-deficient quadratic form[END_REF]. In addition, a simplified and faster, yet suboptimal, version of [START_REF] Markopoulos | Optimal algorithms for L1-subspace signal processing[END_REF] can be found in [START_REF] Markopoulos | Efficient L1-norm principal-component analysis via bit flipping[END_REF].

D. Unsupervised Classification via L2-PCA

We now recall that L2-PCA can perform unsupervised classification or clustering in the two-class scenario when the clusters are well separated [START_REF] Turk | Eigenfaces for recognition[END_REF]. To see this, let us assume a binary data classification framework where each sample

x n belongs to one of two possible classes C k , k = 1, 2, characterized by sample means (or centroids) and covariance matrices:

µ µ µ k = 1 N k X xn2C k x n C k = 1 N k X xn2C k (x n µ µ µ k )(x n µ µ µ k ) > .
L2-PCA searches for the dominant eigenvector of the overall data covariance matrix C x (4). Under our working assumptions, this matrix can be expressed up to an irrelevant scale factor as:

C x = 2 X k=1 ⇡ k C k + ⇡ 1 ⇡ 2 µ µ µ µ µ µ >
where

⇡ k = N k /N and µ µ µ = (µ µ µ 2 µ µ µ 1 )
C x ⇡ ⇡ 1 ⇡ 2 µ µ µ µ µ µ >
. Consequently, L2-PCA defines a projection in the direction µ µ µ joining the class centroids. To illustrate why this direction may be useful for classification, Figure 1 represents the scatter plot of a zero-mean synthetic data set with two clusters ('green' and 'red'), as well as the data projections (2) along unit vector a in the direction of the line joining the cluster means. We can see that the projection yields mostly negative values for the green class and mostly positive for the red class, thus allowing cluster discrimination based on these values.

III. L1-NORM BASED DISCRIMINATION

Pursuing these intuitive arguments, we can define an L1-PCA based criterion for unsupervised clustering as follows.

A. Separating the Projected Class Centroids

In the specific case illustrated in Figure 1, we observe that the sign of the projection gives us clues about the class label: a data vector is most likely 'red' if its projection is positive, and 'green' otherwise. The better the classes are separated after the projection, the more accurate the estimation but, in any case, the sign allows us to eliminate any reference to the 'colors' or categories of the data points. This is therefore an unsupervised approach. Now, the L1 norm recalled in eqn. ( 1) is, by definition, the sum of the positively signed projections minus the sum of the negatively signed ones: In a situation such as that depicted in Figure 1, we can think of this difference as an indicator of the distance between the projected clusters, so that the more separated the clusters, the larger the L1-norm. Therefore, maximizing criterion (5) appears as a promising option for classification. There is an additional interpretation: in many cases, the direction of maximum variance produces well separated clusters; this is why traditional PCA has discriminative properties as recalled in the previous section. Here, we simply reformulate this idea by substituting the variance with the L1-norm for measuring the spread of the data. It is implicitly assumed that the clusters are sufficiently distant in the original d-dimensional space, but this assumption is reasonable in many classification problems. In practice, however, it may not be sufficient to just search for a vector a such that the corresponding projections y in (2) have a large variance. It is for this reason that L2-PCA fails when the class dispersion is significant relative to the centroid distance, even if the clusters are linearly separable [START_REF] Martinez | PCA versus LDA[END_REF]. To prevent the overlapping between the projected clusters, the spread of the projections around their respective centroids should also be minimized, much like in classical linear discriminant analysis (LDA) [START_REF] Fisher | The use of multiple measures in taxonomic problems[END_REF].

kyk 1 = N X n=1 |y n | = X yn>0 y n X yn<0 y n .

B. Reducing the Projected Data Dispersion

The scatter can be measured by 2 pos and 2 neg , defined as

2 pos = 1 N pos X yn>0 (y n m pos ) 2 m pos = 1 N pos X yn>0 y n 2 neg = 1 N neg X yn<0 (y n m neg ) 2 m neg = 1 N neg X yn<0 y n
where N pos and N neg represent the number of positive and negative projections, respectively, with N pos + N neg = N . The weighted sum N pos 2 pos + N neg 2 neg can be interpreted as an estimate of the total spread of the projected data. Some algebra shows that

2 pos = 1 N pos X yn>0 y 2 n m 2 pos 2 neg = 1 N neg X yn<0 y 2 n m 2 neg .
For zero-mean data, it also holds that X Putting it all together, it can be shown that

N pos 2 pos + N neg 2 neg = kyk 2 2 µkyk 2 1 where µ = N 4N pos N neg > 0.

C. L1-norm Criterion for Unsupervised Classification

As a result of the above developments, we can state that:

• To maximize the distance between the projected data centroids, one should maximize kyk 1 .

• To minimize the dispersion around the projected data centroids, one should maximize kyk 1 while minimizing kyk 2 or at least keeping it constant. Accordingly, the following Rayleigh quotient arises as a sensible criterion for unsupervised classification based on the L1 norm:

max a J 1 (a) = kyk 1 p kyk 2 . ( 6
)
The purpose of taking the square root of the L2 norm in the denominator of ( 6) is to ensure that the objective function is dimensionless and invariant to the scale of a, i.e., J 1 ( a) = J 1 (a), 2 R\{0}. This criterion is experimentally assessed next.

IV. EXPERIMENTAL RESULTS

This section evaluates the performance of the proposed L1norm criterion through several computer experiments.

A. Discriminative Properties

The first experiment randomly draws N = 500 samples from a mixture of two equiprobable (⇡ [START_REF] Jolliffe | Principal Component Analysis[END_REF][START_REF] Markopoulos | Optimal algorithms for L1-subspace signal processing[END_REF]. Figure 2 depicts the proposed criterion J 1 (a), defined in eqn. [START_REF] Turk | Eigenfaces for recognition[END_REF], as a function of the angle ✓ between the projection vector a and the x-axis (blue line). The curve attains its global maximum at approximately ✓ = 0 degrees, i.e., the optimal direction for this dataset is parallel to the horizontal axis. For completeness, Figure 2 The scatter plot of the observations is given in Figure 3, where data of class 1 and class 2 are represented by circles and crosses, respectively. The blue line points in the direction maximizing J 1 (a). As reported in the previous paragraph, observe that this line is almost horizontal. Compare with the yellow line, which is the direction determined by classical LDA [START_REF] Fisher | The use of multiple measures in taxonomic problems[END_REF]: there is no significant difference between the projections calculated by the two methods, as both lines practically overlap. Finally, we point out that the black dashed line marked PCA in Figure 3 points in the direction of maximum variance of the data. Even though L2-PCA seems to yield an acceptable result, i.e., the projected data form clusters, this technique may have poor performance when the data dispersion is large compared to the distance between the class means. This is clearly illustrated by Figure 4, which shows the result obtained by repeating the experiment with class covariance matrices [START_REF] Jolliffe | Principal Component Analysis[END_REF][START_REF] Ferrez | Solving the fixed rank convex quadratic maximization in binary variables by a parallel zonotope construction algorithm[END_REF], so that the direction of maximum variance is now along the x 2 -axis. Obviously, projecting along this axis does not produce well separated groups. By contrast, the proposed criterion is essentially unaffected by the change in experimental conditions.

1 = ⇡ 2 = 0.5) two- dimensional Gaussian distributions with means µ µ µ 1 = [2, 0] > and µ µ µ 2 = [2, 0] > and covariance matrices C 1 = C 2 = diag
C 1 = C 2 = diag

B. Robustness Against Outliers

Outliers are samples generated by a different mechanism, or model, than the nominal observations. In this experiment, we replace 33% of the data in Figure 3 by outliers generated by raising a Gaussian random variable to the third power. The mean of the outliers in each class is set to that of the data they are replacing. Figure 5 represents the scatter plot of the corrupted dataset. The blue line again points in the direction maximizing the proposed criterion J 1 , while the black line represents the direction of maximum variance of the data. The experiment shows that, as expected, the proposed L1-norm based method is more robust against outliers than L2-PCA. Figure 6 plots the estimated probability density function, computed by a kernel density estimator method, of the projection of the data onto the direction maximizing J 1 (blue line of Figure 5). The distribution is clearly bimodal, showing that the sample arises from two different classes. As a further experiment, we fit a Gaussian mixture model (GMM) to the corrupted data. GMMs are based on the assumption that all the observations are drawn from a mixture of normal distributions, and are very popular for solving unsupervised classification problems [START_REF] Bishop | Pattern Recognition and Machine Learning[END_REF]. Roughly speaking, GMMs generalize the standard k-means clustering algorithm by incorporating information about the covariance structure of the data classes. In this experiment, the parameters of the model are found by using the Expectation-Maximization (EM) algorithm [START_REF] Bishop | Pattern Recognition and Machine Learning[END_REF]. Figure 7 plots the data over the es- timated Gaussian mixture model contours. Observe that the EM algorithm models the dataset as a mixture of two almostoverlapped Gaussians with a priori probabilities ⇡ 1 = 0.94 and ⇡ 2 = 0.06. After learning the GMM, a data point is classified according to the probability of having been generated by each of the Gaussians. Figure 7 also plots the predicted labels of the data points: data from class 1 are shown as green dots, while data from class 2 are shown as red crosses. The resulting classification is clearly erroneous and, in view of Figure 6, it can easily be outperformed by the proposed L1-PCA based approach.

V. CONCLUSIONS

The present contribution has framed L1-PCA in the context of data classification. An L1-PCA variant has been derived that can perform unsupervised linear discrimination in the twoclass setting. The variant consists of the L1-norm of the vector of projected data samples normalized by the square root of its L2 norm, which can be cast as a Rayleigh quotient. Although the criterion has been derived on intuitive grounds, a number of computer experiments have confirmed its good discrimination capabilities and enhanced robustness to outliers as compared to classical L2-PCA. Further work should include a thorough theoretical study and a comparative performance analysis on real data.

Fig. 1 :

 1 Fig.1: Scatter plot of samples from two classes ('green' and 'red'). The small vertical lines on the horizontal axis represent the sample projections onto the dashed line joining the class means Also shown are the histograms and kernel estimates of the densities of the projected data.

yn>0 y n = X yn<0 yy

 yn<0 n ) N neg m neg = N pos m pos and n = 2N pos m pos .

Fig. 2 :

 2 Fig. 2: Proposed criterion J 1 (✓) defined in eqn. (6) (blue line) for y = a > x with a = [cos(✓), sin(✓)] > , ✓ 2 [ ⇡, ⇡]. For comparison, the L2-PCA objective function (3) is also depicted (black line). Both curves are normalized with respect to their maximum values.

Fig. 3 :

 3 Fig. 3: Performance of the proposed algorithm when applied to classes with almost spherical data point clouds. Results obtained by using L2-PCA and LDA are also shown for comparison.

Fig. 4 :

 4 Fig. 4: Performance of the proposed algorithm when applied to classes with non-spherical data point clouds. Results obtained by using L2-PCA and LDA are also shown for comparison.

Fig. 5 :

 5 Fig.5: Performance of the proposed algorithm and L2-PCA when applied to data corrupted by outliers.

Fig. 6 :

 6 Fig. 6: Histogram of the projection of the corrupted data onto the optimal L1-norm based direction, shown by the blue line of Figure 5.

2 Fig. 7 :

 27 Fig. 7: Contour plot of the estimated Gaussian mixture model of the corrupted data. Tentative classification of the data points as suggested by this model is also shown, yielding highly inaccurate results.

  (•) > denotes the matrix transpose operator and

	in: Proc. 52nd Asilomar Conference on Signals, Systems and Computers, Pacific Grove, CA, USA, Oct. 28-31, 2018, invited.
	diag(a entries {a k } K 1 , a 2 , . . . , a K ) the K ⇥K diagonal matrix with diagonal k=1 .

  is the line joining the class means. If the data dispersion in each class is negligible compared to the distance between the class means, i.e., kC k k

Fro ⌧ k µ µ µk 2 ,

where k • k Fro denotes the Frobenius norm, then we can approximate