Nicolas Baudru
email: nicolas.baudru@lis-lab.fr

Pierre-Alain Reynier
email: pierre-alain.reynier@lis-lab.fr

From Two-Way Transducers to Regular Function Expressions

Transducers constitute a fundamental extension of automata. The class of regular word functions has recently emerged as an important class of word-to-word functions, characterized by means of (functional, or unambiguous, or deterministic) two-way transducers, copyless streaming string transducers, and MSO-definable graph transformations. A fundamental result in language theory is Kleene's Theorem, relating finite state automata and regular expressions. In [3], the authors introduced a set of regular function expressions and proved a similar result for regular word functions, by showing the equivalence with copyless streaming string transducers. In this paper, we propose a direct, simplified and effective translation from unambiguous two-way transducers to regular function expressions extending the Brzozowski and McCluskey algorithm. In addition, we identify a subset of regular function expressions characterizing the (strict) subclass of functional sweeping transducers.

Introduction

The theory of regular languages has been extended in numerous directions, including finite and infinite trees. Another natural extension is moving from languages to transductions. One of the strengths of the class of regular languages is their equivalent presentation by means of automata, logic, algebra and regular expressions. Regular expressions are of particular interest for specification purposes in a declarative manner. We are interested in this paper in regular expressions for specifying word-to-word functions.

While finite state automata are very robust under modifications in the model, the situation is different for transducers. It is well known that non-determinism and two-wayness increase the expressive power, even when one only considers functional transductions. The class of functions realized by non-deterministic two-way transducers, so-called regular functions, has attracted recently a strong interest [1-4, 13, 6, 14, 8]. It is very expressive and allows to express natural transformations that are not definable by one-way transducers (e.g. duplicate the input word, or produce its mirror image). This class also enjoys a logical characterization using Monadic Second-Order graph transductions interpreted on strings [START_REF] Courcelle | Monadic second-order definable graph transductions: a survey[END_REF], and can also be defined using the model of copyless streaming string transducers (SST) [START_REF] Alur | Expressiveness of streaming string transducers[END_REF].

A natural line of research concerns the identification of adequate regular expressions to specify different classes of word functions, as investigated in [START_REF] Choffrut | An algebraic characterization of unary two-way transducers[END_REF][START_REF] Lombardy | Two-way representations and weighted automata[END_REF].

It is well known that rational relations (realized by non-deterministic one-way transducers) can be described using standard regular expressions on pairs of input and output words, as a special case of Schützenberger theorem for weighted automata [START_REF] Schützenberger | On the definition of a family of automata[END_REF]. Imposing on these regular expressions the restriction of being unambiguous on their input part yields a presentation of rational functions [START_REF] Berstel | Transductions and context-free languages[END_REF]. More recently, a set of regular combinators has been introduced in order to characterize the class of regular functions [START_REF] Alur | Regular combinators for string transformations[END_REF]. The equivalence goes through the model of copyless SST, and relies on a very involved proof.

In this paper, we propose a new construction showing that any regular function can be expressed using the regular functions expressions of [START_REF] Alur | Regular combinators for string transformations[END_REF]. Unlike [START_REF] Alur | Regular combinators for string transformations[END_REF], we take as input unambiguous two-way finite state transducers. Intuitively, our construction lifts the standard state-elimination algorithm proposed by Brzozowski and McCluskey in [START_REF] Brzozowski | Signal flow graph techniques for sequential circuit state diagrams[END_REF] for one-way finite state automata to unambiguous two-way finite state transducers. The difficulty lies in two aspects: going from a one-way to a two-way model, and going from automata to transducers. In order to address these issues, we use the construction of the Shepherdson automaton [START_REF] Shepherdson | The reduction of two-way automata to one-way automata[END_REF] and the notion of traversals of two-way automata, that allow to describe the computation flow of a two-way automaton over some input word. In addition, we label the edges of these flow graphs with regular function expressions.

More precisely, the state-elimination algorithm requires to be able to compute the union, concatenation and Kleene star of transitions of the automaton. We thus have to be able to perform these operations on flows. Unlike union and concatenation, the operation of Kleene iteration may yield complex behaviors that are difficult to describe by means of regular function expressions. A key contribution of our work is a deep investigation of these flows, and the identification of an important characteristic: the number of crossing edges. Using this parameter, we first identify a subclass of flows for which the representation of the Kleene iteration by means of regular function expressions is rather simple, and then present a construction allowing to reduce the Kleene iteration of arbitrary flows to that of the subclass. This results in a very simple proof, which we believe will be useful for further extensions. A side-result of our work is the exhibition of a set of operators characterizing the class of sweeping transducers (this result could also be deduced from [START_REF] Lombardy | Two-way representations and weighted automata[END_REF]). Sweeping transducers induce a third class of functions in-between rational and regular functions.

The very recent work [START_REF] Dave | Regular transducer expressions for regular transformations over infinite words[END_REF] adopts an approach similar to ours in order to lift the results of [START_REF] Alur | Regular combinators for string transformations[END_REF] to infinite words. However, to deal with Kleene iteration, they resort to an unambiguous version of Simon's factorization forest theorem.

It is worth mentioning that our results are presented for word transducers but they could be easily adapted to the setting of transducers producing output in some monoid, as in [START_REF] Alur | Regular combinators for string transformations[END_REF].

We introduce the model of transducers and the regular function expressions in Section 2, and our labelled flow graphs in Section 3. In Section 4, we present the algorithm, and the main results concerning the representation of the Kleene star of flow graphs. The case of sweeping transducers is dealt with in Section 4.5.

The second author is funded by the DeLTA project (ANR-16-CE40-0007).

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.

Given n > 0, we denote by [n] the set {0, 1, . . . , n -1}. A language over A is a set L ⊆ A * . Given two languages L, L over A, the concatenation of L and L , denoted LL , is defined as {uv | u ∈ L, v ∈ L }. We say that L and L are unambiguously concatenable whenever for every word w ∈ LL , there exist unique words u ∈ L and v ∈ L such that w = uv. Given a language L over A, the Kleene star of L, denoted by L * , is defined as

{u 1 • • • u n | n 0 and ∀i, u i ∈ L}.
The Kleene plus of L, denoted by L + , is defined as LL * . When ∈ L, we say that L is unambiguously iterable if for every word w ∈ L * , there exist unique words

u 1 , . . . , u n ∈ L such that w = u 1 • • • u n .
A monoid is a set M equipped with an associative internal law and a neutral element. Given an alphabet A and a monoid M , a transduction from A to M is a relation R ⊆ A * × M . 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.

When dealing with two-way machines, we assume the alphabet A to be extended into A by adding two special symbols , , and we consider input words with left and right markers. The automaton then reads the input word u , and we set u[0] = and u[|u| + 1] = . We also define D = {←, →}. Automata. A two-way finite state automaton (2NFA) 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 δ ⊆ Q × A × Q × D is the transition relation. We describe the behaviour of A on some input word u . Informally, a 2NFA has a reading head pointing between symbols (and possibly on the left of and on the right of ). A configuration of A is a triple (q, i, d) ∈ Q × N × D, where 0 i |u| + 2 is the position of the reading head on the input tape. The direction d indicates whether the next input letter read is on the left or on the right of the reading head. The configurations (q, i, d) and (q , i , d ) are consecutive if we have (q, u[i + m d ], q , d ) ∈ δ, where m → = 0 and m ← = -1, and

i = i + 1 if d = d = →, i = i -1 if d = d = ←,
and i = i otherwise. A run is a finite sequence of consecutive configurations. It is accepting if the first configuration is (q 0 , 0, →), and the last configuration is (q, |u| + 2, →) with q ∈ F . Note that this latter configuration does not allow additional transitions. An exemple of run is depicted in Figure 2. The language of A is the set of words u ∈ A * such that there exists an accepting run of A on u .

A two-way finite state automaton is:

deterministic if we may write δ as a function from

Q × A to Q × {←, →}.
unambiguous if for any u ∈ A * , there is at most one accepting run on u .

one-way it it does not have transitions of the form (q, a, q , ←).

sweeping if the head can change direction only at the extremities of the input.

0 1 2 3 4 a, b/ , → #, / , ← a, b/ , → / , → a/a, ←, b/b, ← #, / , → #/#, → / , → Fig. 1. A 2NFT realizing the function f of Example 2.
Transducers. Given two finite alphabets A and B, two-way finite state transducers (2NFT) from A to B extend 2NFA over A with a one-way left-to-right output tape containing elements of B * . They are defined as 2NFA except that the transition relation δ is extended with outputs:

δ ⊆ Q × A × B * × Q × {←, →}.
When a transition (q, a, w, q , d) is fired, the word w is appended to the right of the output tape. The transduction defined by a 2NFT 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 on the word u . We say that a 2NFT T is functional if the relation R(T ) is a function. We say that a 2NFT T is deterministic (resp. unambiguous, one-way, sweeping) if its underlying 2NFA is. Observe that if T is deterministic or unambiguous, there is at most one accepting run for each input word, and thus R(T ) is a function. Theorem 1. [START_REF] Engelfriet | MSO definable string transductions and two-way finite-state transducers[END_REF] The classes of functional, deterministic and unambiguous 2NFT are equivalent, and strictly more expressive than that of functional sweeping transducers, which in turn is strictly more expressive than the class of functional one-way transducers.

We call rational functions (resp. sweeping functions, regular functions) the ones that are definable by one-way transducers (resp. sweeping transducers, two-way transducers). Example 2. Given a word u, we denote by mirror(u) its mirror image. Given A = {a, b, #}, we consider the function mirror * mapping an input word u, whose decomposition according to

#'s is u = u 1 #u 2 # . . . #u n , to the word v = v 1 #v 2 # . . . #v n , with v i = mirror(u i ) for all i.
This function is realized by the deterministic 2NFT depicted in Figure 1. An execution of this transducer on the input word u = ab#bba is depicted in Figure 2.

Shepherdson automaton construction

A crossing sequence is a sequence of states encountered by a run at a given position in the input word. For instance, if we consider the run depicted in Figure 2, the crossing sequence at position 0 (resp. position 8) is the tuple (0) (resp. ( 4)), while all the other crossing sequences are equal to the triple (1, 2, 3). It is well-known that the crossing sequences of accepting runs of unambiguous 2NFA have size bounded by 2|Q|, as a state cannot appear twice in a crossing sequence at two indices of same parity (otherwise a loop is entered).

Unlike one-way automata, partial runs of a two-way automaton on some factor of an input word do not all go through the input word from left to right. Flows are graphs allowing to describe these partial runs between two crossing sequences. More precisely, a flow of size (n, m), n, m > 0, is a particular directed graph F with set of vertices

[n] × {L} [m] × {R}. Vertices in [n] × {L} (resp.
[m] × {R}) are called left (resp. right) vertices, satisfying additional conditions that intuitively imply that it connects two crossing sequences (see [START_REF] Baschenis | Untwisting two-way transducers in elementary time[END_REF]). An edge is a crossing edge if it is between two vertices on different sides, it is a return edge otherwise. From now on, we fix an integer M and only consider flows of size (n, m) with n, m ≤ M . We denote by F this finite set of flows. It is well-known that F can be equipped with an operation of composition (denoted by F • F ), yielding a monoid. This operation can be understood as the identification of paths in the concatenation of the two graphs. We state a simple property of flows: Lemma 3. Let F, F be two flows with k and l crossing edges respectively. Then F • F has at most min(k, l) crossing edges. The Shepherdson automaton of an unambiguous two-way automaton A is an equivalent one-way automaton obtained as follows: states are crossing sequences, and there is a transition between two states on some letter a if there exists an adequate flow on this letter. This automaton may be of exponential size. W.l.o.g., we assume that the Shepherdson automaton is trimmed, meaning that every state appears in some accepting run. Note that as A is unambiguous, then so is its Shepherdson automaton. More precisely, for every transition, there is a single flow that can be associated with it. An example is depicted in Figure 3.

Function Expressions

We recall the function expressions introduced in [START_REF] Alur | Regular combinators for string transformations[END_REF] to specify word-to-word functions from A * to B * . First observe that in [START_REF] Alur | Regular combinators for string transformations[END_REF], these operators are mappings from elements of A * to elements of some monoid M . We have chosen to present our results in the setting of transducers but they could easily be extended to an arbitrary monoid as output. Observe also that we do not follow the terminology used in [START_REF] Alur | Regular combinators for string transformations[END_REF], and rather adopt a terminology coming from formal power series (see for instance [START_REF] Choffrut | An algebraic characterization of unary two-way transducers[END_REF][START_REF] Lombardy | Two-way representations and weighted automata[END_REF]). It is however trivial to verify that the operators we introduce correspond to the ones of [START_REF] Alur | Regular combinators for string transformations[END_REF]. Constant functions. Given a language L ⊆ A * and v ∈ B * , the constant function L/v is such that dom(L/v) = L and for all u ∈ L, L/v(u) = v. Sum. Given two functions f, g such that dom(f ) ∩ dom(g) = ∅, the sum f ⊕ g is such that dom(f ⊕ g) = dom(f ) dom(g) and for all u ∈ dom(f ⊕ g),

(f ⊕ g)(u) = f (u) if u ∈ dom(f ); (f ⊕ g)(u) = g(u) if u ∈ dom(g). Hadamard product. Given two functions f, g, the Hadamard product f ⊗ g is such that dom(f ⊗ g) = dom(f ) ∩ dom(g) and for all u ∈ dom(f ⊗ g), (f ⊗ g)(u) = f (u)g(u).
Cauchy products. Given two functions f, g such that dom(f ) and dom(g) are unambiguously concatenable, the Cauchy product f • g and the left Cauchy product f

← • g are such that dom(f • g) = dom(f ← • g) = dom(f )dom(g) and: ∀u = u 1 u 2 with u 1 ∈ dom(f ), u 2 ∈ dom(g), (f • g)(u) = f (u 1 )g(u 2 ) (f ← • g)(u) = g(u 2 )f (u 1 )
Kleene stars. Given f such that dom(f ) is unambiguously iterable, the Kleene star f * and the left Kleene star f

← * are s. t. dom(f * ) = dom(f ← * ) = L * and: ∀u = u 1 u 2 . . . u n with ∀i, u i ∈ dom(f ), f * (u) = f (u 1 )f (u 2 ) . . . f (u n ) f ← * (u) = f (u n )f (u n-1 ) . . . f (u 1 )
Chained stars. Given a function f and a language L such that L 2 ⊆ dom(f ) and L is unambiguously iterable, the chained star f, L , and the left chained star f, L ← , are such that dom( f, L ) = dom( f, L ← ) = L 2 , and:

∀u = u 1 u 2 . . . u n with ∀i, u i ∈ L, f, L (u) = f (u 1 u 2 )f (u 2 u 3 ) . . . f (u n-1 u n ) f, L ← (u) = f (u n-1 u n ) . . . f (u 2 u 3 )f (u 1 u 2 )
We consider the following grammars: (L is a regular language over A, v ∈ B * )

Reg f, g ::= L/v | f ⊕ g | f ⊗ g | f • g | f ← • g | f, L | f, L ← Rat f, g ::= L/v | f ⊕ g | f • g | f *
A function expression obtained from some grammar G is called a G-expression. Reg-expressions are called regular function expressions. -Rational functions are equivalent to Rat-expressions [START_REF] Berstel | Transductions and context-free languages[END_REF].

-Regular functions are equivalent to Reg-expressions [START_REF] Alur | Regular combinators for string transformations[END_REF].

Function Expression Flow Automata

Intuitively, we refine the Shepherdson automaton construction by labelling transitions with flows, in which each edge is labelled by a function expression. From now on, we fix an input alphabet A and an output alphabet B. We denote by E the set of all function expression flows, by dom(E) the domain of a FEF E and by flow(E) its underlying flow (flow(E) ∈ F).

A function expression flow E ∈ E of size (n, m) defines a functional transduction from A * to W: for all u ∈ dom(E), E(u) is the word flow W of size (n, m) such that (x, f (u), y) is an edge of W iff (x, f, y) is an edge of E.

We say that two FEFs E, E ∈ E are disjoint if dom(E) ∩ dom(E ) = ∅.

Definition 8. A label of size (n, m), with n, m > 0, is a non-empty set of FEFs of size (n, m) that are pairwise disjoint.

We denote by L the set of labels and define the domain of a label as the union of the domains of the FEFs it contains: dom(L) = E∈L dom(E). A label also defines a functional transduction from A * to W: for any u ∈ dom(L), L(u) = E(u) for the unique FEF E of L such that u ∈ dom(E).

Definition 9. A function expression flow automaton (FEFA for short) is a tuple A = (Q, q 0 , q f , δ) where Q is a finite set of states, q 0 (resp. q f ) is the initial (resp. final) state, and δ ⊆ Q × L × Q is the finite transition relation. We require that there is no incoming (resp. outgoing) transition to the initial state (resp. from the final state), and that there exists a mapping size : Q → N such that size(q 0 ) = size(q f ) = 1 and, for every (q, L, q ) ∈ δ, L is of size (size(q), size(q )).

Given a word u ∈ A * , an execution on u of a FEFA A = (Q, q 0 , q f , δ) is a decomposition u 1 • • • u k of u and a sequence (q i , L i , q i+1 ) 1 i k of consecutive transitions such that u i ∈ dom(L i ) for all i. The execution is accepting if q 1 = q 0 and q k+1 = q f . We say that a FEFA is unambiguous if for every word u, there is at most one accepting execution on u. When this holds, following above notations, the word flow associated with such an execution is out

(u) = L 1 (u 1 ) • L 2 (u 2 ) • . . . • L k (u k ).
The properties of the mapping size ensure that this composition is well defined.

The semantics of a FEFA A is a functional transduction from A * to B * . Indeed, given a word u with some accepting execution which produces the word flow out(u), the properties of the mapping size in the definition of FEFA ensure that out(u) is of size [START_REF] Alur | Expressiveness of streaming string transducers[END_REF][START_REF] Alur | Expressiveness of streaming string transducers[END_REF], hence reduced to a single left-to-right crossing edge, labelled by some word v ∈ B * . We thus consider that A maps u to v.

The following lemma follows from Shepherdson automaton construction:

Lemma 10. Given an unambiguous 2NFT, one can build an equivalent unambiguous FEFA.

A Brzozowski and McCluskey-like Algorithm

Presentation of the algorithm

The standard Brzozowski and McCluskey (BMC for short) algorithm takes as input a one-way finite-state automaton A, with distinguished initial and final states, and proceeds as follows: it removes all the states of the automaton one by one, except the initial and final states. Each time a state is removed, the remaining transitions are modified in order to obtain an equivalent automaton.

The transitions are now labelled by regular expressions. More precisely, consider the removal of some state q 2 . Then, for all states q 1 and q 3 of A we have to replace the transitions q 1 e1 -→ q 2 e2 -→ q 2 e3 -→ q 3 and q 1 e4 -→ q 3 by a unique transition q 1 e -→ q 3 . In order to obtain an equivalent automaton, one defines e = e 1 e 3 + e 1 e + 2 e 3 + e 4 . At the end of the algorithm, one ends up with a single transition between the initial and the final state. The regular expression e labelling this transition describes exactly the whole behaviour of the automaton.

In order to adapt this algorithm to unambiguous FEFA, one needs to define the operations of sum, concatenation and Kleene plus (i.e. Kleene star with a positive number of iterations) on labels. It is worth observing that unambiguity of the FEFA ensures that sum (resp. concatenation, Kleene plus) involves labels with disjoint domains (resp. unambiguously concatenable domains, unambiguously iterable domains). As we will see in the subsequent sections, while sum and concatenation are easy to deal with, Kleene plus is more involved. We first present in Subsection 4.3 how to compute the Kleene plus for a restricted class of labels, called simple labels, and as a corollary we obtain a particular instance of BMC algorithm valid for FEFA for which BMC always eliminates self-loops with simple labels. Last, we show in Subsection 4.4 how the Kleene plus of arbitrary labels can be obtained using this particular instance of BMC algorithm for FEFA.

Putting everything together, we obtain:

Theorem 11. Given an unambiguous 2NFT, our Brzozowski and McCluskeylike algorithm returns an equivalent Reg-expression.

Sum, concatenation and Kleene plus of labels

Sum. Let L 1 , L 2 be two labels of L having the same size and such that dom(L 1 ) and dom(L 2 ) are disjoint. It is possible to define a new label, called the sum of L 1 and L 2 and denoted by L 1 ⊕ L 2 , whose domain is dom(L 1 ) dom(L 2 ), and such that for all u ∈ dom(L 1 ) dom(L 2 ),

L 1 ⊕ L 2 (u) = L 1 (u) if u ∈ dom(L 1 ),
and

L 1 ⊕ L 2 = L 2 (u) if u ∈ dom(L 2
). This label is simply obtained by taking the union of FEFs of L 1 and L 2 .

Concatenation. Let L 1 , L 2 be two labels of size (n, m) and (m, k), and such that dom(L 1 ) and dom(L 2 ) are unambiguously concatenable. It is possible to define a new label, called the concatenation of L 1 and L 2 and denoted by L 1 • L 2 , whose domain is dom(L 1 )dom(L 2 ), and such that for all u = u 1 u 2 , with

u i ∈ dom(L i ) for i ∈ {1, 2}, (L 1 • L 2 )(u) = L 1 (u 1 ) • L 2 (u 2 ).
We first explain how to define the concatenation of two FEFs E 1 and E 2 , denoted by

E 1 • E 2 . Its underlying flow is F = flow(E 1 ) • flow(E 2 )
. As the sizes of flows are bounded, it is not difficult to observe that the function expressions labelling the edges of F can be obtained from the ones of E 1 and E 2 using the Hadamard and Cauchy product operators.

The concatenation of labels is then obtained by cartesian product as:

L 1 • L 2 = {E 1 • E 2 | E 1 ∈ L 1 , E 2 ∈ L 2 }.
Kleene plus. Given a label L of size (m, m) such that dom(L) is unambiguously iterable, we will explain how to define the Kleene plus of L, denoted by L + , whose domain is dom(L) + , and which is such that

∀u = u 1 u 2 . . . u n with ∀i, u i ∈ dom(L), L + (u) = L(u 1 ) • L(u 2 ) • . . . • L(u n ).
Constructing the label L + is difficult and is addressed in the next two subsections. As a first step, given a simple FEF E and a language L that is unambiguously iterable and such that L 2 ⊆ dom(E), we define the chained star of E w.r.t. L, denoted by E, L , as follows. It is a FEF whose domain is L 2 and such that for any word u = u 1 u 2 . . .

u n ∈ L 2 , we have E, L (u) = E(u 1 u 2 ) • E(u 2 u 3 ) • . . . • E(u n-1 u n ).
This FEF is obtained from E by applying the chained star operator (or its left version) on each (crossing) edge of E.

We turn to the construction of the label L + when L is a simple label. The definition of simple labels implies that for all n > 0 and E, E 1 , . . . , E n ∈ L,

flow(E) = flow(E • E 1 • E 2 • • • • • E n ).
In consequence, the flows that appear in L ≥2 are the flows of L. Let L = dom(L). Given some E ∈ L, we claim we can build a FEF Ẽ with domain dom(E)L ≥1 , size (m, m) and flow( Ẽ) = flow(E), that "simulates" all sequences of FEFs of L beginning by E. More precisely, its semantics is as follows: for all E 1 , . . .

E n ∈ L, if u = u 0 u 1 . . . u n with u 0 ∈ dom(E) and u i ∈ dom(E i ) for all i, then Ẽ(u) = E(u 0 ) • E 1 (u 1 ) • • • • • E n (u n ). (1)
We can then define the label L + as L ⊕ { Ẽ | E ∈ L}.

We detail now the construction of Ẽ for a FEF E ∈ L, depicted in Figure 4. We start with a property of simple labels, obtained using Lemma 3: Lemma 13. All FEFs of a simple label have the same number of crossing edges.

We first decompose E into two FEFs Ē and Ê such that for every word u ∈ dom(E), we have E(u) = Ê(u) • Ē(u). Formally, given a FEF E, Ē is the FEF obtained by deleting all return edges on the left (and the corresponding nodes), and Ê is the FEF obtained by deleting all return edges on the right (and the corresponding nodes) and moreover by replacing all function expressions of crossing edges of E with dom(E)/ε (dashed edges in Figure 4). By Lemma 13, there exists c such that each E ∈ L has c crossing edges. Let F be the flow consisting of no return edges and c crossing edges, then for all E 1 , E 2 ∈ L, we have flow( Ē1 • Ê2 ) = F . As a consequence, we can define1 the FEF E ♣ = E1,E2∈L Ē1 • Ê2 . Observe that E ♣ is a simple FEF. We can thus use the chained star E = E ♣ , L of domain L ≥2 to rewrite Eq. ( 1) as:

Ẽ(u)= Ê(u 0 )• ( Ē• Ê1 )(u 0 u 1 )•( Ē1 • Ê2 )(u 1 u 2 )• . . . •( Ēn-1 • Ên )(u n-1 u n ) E (u0...un) • Ēn (u n ) E1 u1 u2 u0 u0 u0 u1 u1 u2 u2 E2 E E1 E2 E E1 E E2 = Fig. 4.
Illustration of the decomposition used for simple labels.

Remark 14. We have thus proven that we are able to compute the Kleene plus for simple labels. This implies that we can apply our BMC algorithm for a given FEFA if each time a state is removed, its self-loop is labelled with a simple label. We call this the simple-BMC algorithm.

Kleene plus over arbitrary labels

We present now how to construct the label L + when L is an arbitrary label. For simplicity, we construct a label L ≥2 , and then define L + = L ⊕ L ≥2 . The intuitive idea is to use the previously described simple-BMC algorithm. Therefore, we consider an automaton A that consists only of three transitions ι

L -→ α L -→ α L -→ β
with initial state ι and final state β. We will exhibit a finite unfolding A Unf = (Q Unf , ι, β, -→ Unf ) of A, equivalent to A, which has a property ensuring that the simple-BMC algorithm can be applied.

Let 2N + 1 be the greatest number of crossing edges among the FEFs of L. Let S i be the sets of underlying flows with 2i + 1 crossing edges finitely generated by L with concatenation of FEFs. By Lemma 3 there are at most N such sets S i . Then, we set Q Unf = {ι, β} ∪ i∈0,...,N (S i ∪ { }). The alphabet of A Unf consists of subsets of L. Intuitively, the state (s i ) 0≤i≤N reached in A Unf after reading a sequence of labels L 1 , . . . , L n is a decomposition of flow(L 1 • . . . • L n ). Formally the transition function -→ Unf is defined as follows: ( is neutral for composition)

-for each F ∈ {flow(E) | E ∈ L}, ι {E∈L|flow(E)=F } ------------→ Unf (s i ) 0≤i≤N with s i = F ∈ S i and for all j = i, s j = ; -(s 0 , . . . , s N ) L -→ Unf β for all (s 0 , . . . , s N ) ∈ Q Unf ; -let q = (s 0 , . . . , s N ) ∈ Q Unf , 0 ≤ j ≤ N and F ∈ F. We define L q,j,F as the set of FEFs E ∈ L such that F = s j • s j+1 • • • • • s N • flow(E) ∈ S j and for all i > j, s i • s i+1 • • • • • s N • flow(E) / ∈ S i . If L q,j,F = ∅, then q L q,j,F -→ Unf (s i ) 0≤i≤N , with s j = F , s i = s i if i < j, and
s i = if i > j.
For j ≤ N , we define Q j as the set of states (s 0 , . . . , s j , , . . . , ) with s j = .

We write q 0 Lσ j q n if there is an execution (q i Li -→ Unf q i+1 ) 0≤i<n of A Unf with L σ = L 0 • • • • • L n-1 , and such that for every i ∈ {1, . . . , n -1}, q i ∈ k j Q k .

Lemma 15. If q Lσ j q with q = (s i ) 0≤i≤N and q = (s i ) 0≤i≤N in Q j , then:

(1) for all E ∈ L σ , s j • flow(E) = s j and, (2) flow(E) has 2j + 1 crossing edges.

A careful analysis of the different types of edges in flows of L σ allows to deduce from Lemma 15 that L σ is simple whenever q = q. More generally, using similar techniques, we can show: Lemma 16. Let j ≥ 0 and q ∈ Q j . If {L 1 , . . . , L k } is a set of labels such that q Li j q for all i, then ⊕ i∈{1,...,k} L i is a simple label. We now consider the application of BMC algorithm that successively eliminates states in Q j , for j = N, N -1, . . . , 0. We can prove by induction on the number of steps performed by the algorithm that for every remaining state q, the label L q of the self-loop around q is simple. Indeed, as we observed in Subsection 4.3, the flows associated with the Kleene plus of a simple label are exactly those of that label. This allows to show that the flows appearing in L q are obtained by finitely many paths around q in A Unf that only go through states in k j Q k , where j is such that q ∈ Q j . Hence L q is simple by Lemma 16.

The case of sweeping transducers

We consider now the case of sweeping transducers. We introduce the two following grammars for function expressions: (L is a regular language over A, v ∈ B * ) Proof. One observes that for sweeping transducers, the Kleene plus only concerns simple FEFs, for which the Kleene star operator of expressions is sufficient.

← Rat f, g ::= L/v | f ⊕ g | f ← • g | f

Conclusion

In this paper, we have extended the standard state elimination algorithm due to Brzozowski and McCluskey to unambiguous two-way finite-state transducers. This yields a simple, direct and effective translation from these transducers to regular function expressions. We have also identified a subclass of expressions characterizing sweeping functions.

This work opens the way to numerous applications and extensions: deciding one-wayness [START_REF] Filiot | From two-way to one-way finite state transducers[END_REF][START_REF] Baschenis | Untwisting two-way transducers in elementary time[END_REF], studying infinite words [START_REF] Alur | Regular transformations of infinite strings[END_REF] and identifying star-free expressions for first-order definable transformations [START_REF] Mcnaughton | Counter-free automata[END_REF][START_REF] Filiot | First-order definable string transformations[END_REF][START_REF] Carton | Aperiodic two-way transducers and FO-transductions[END_REF] for instance.

Fig. 2 .

 2 Fig. 2. A run of the 2NFT of Example 2.

Fig. 3 .

 3 Fig. 3. The Shepherdson automaton of the underlying 2NFA of Example 2. Flows associated with transitions are indicated for clarity.

Example 4 .Theorem 5 .

 45 We give examples to illustrate these operators:the identity function mapping on A * can be defined as idA * = a∈A {a}/a * ,the mirror image on A * can be defined as mirrorA * = a∈A {a}/a ← * ,the function last mapping word ua ∈ A * to a |ua| , for every a ∈ A, can be defined as last = a∈A (A/a) * • {a}/a . the function mirror * of Example 2 can be defined as (mirror {a,b} * • {#}/#) * • mirror {a,b} * . The following equivalences hold:

Definition 6 .

 6 A word flow W is a flow of F whose edges are labelled by words of B * . The set of word flows is denoted by W. Composition of flows can be lifted to word flows, by labelling new edges with the concatenation of words labelling edges along the path. We denote it by W • W . Definition 7. A function expression flow (FEF) E over domain L is a flow of F whose edges are labelled by function expressions from A * to B * of domain L.

4. 3

 3 Kleene plus over simple labels Definition 12. An FEF E ∈ E is simple if its flow contains no return edge. A label L ∈ L is simple if for all E, E ∈ L, flow(E • E ) = flow(E).

RatTheorem 17 .

 17 s ::= s ⊕ s | f | f ⊗ g where f, g ∈ Rat ∪← Sweeping functions are equivalent to SW -expressions.

Given two FEFs E, E with same underlying flow F , E ⊕ E is the FEF with flow F and set of edges {(x, f ⊕ f , y) | (x, f, y) ∈ E, (x, f , y) ∈ E }.


Xxx Sedao
email: xxx.sedao@univ-st-etienne.fr

Matthieu Lenci
email: lenci@emse.fr

Anton Rudenko
email: anton.rudenko@univ-st-etienne.fr

Alina Pascale-Hamri

Jean-Philippe Colombier
email: jean.philippe.colombier@univ-st-etienne.fr

Cyril Mauclair
email: cyril.mauclair@univ-st-etienne.fr

Additive and Substractive Surface Structuring by Femtosecond Laser Induced Material Ejection and Redistribution

Keywords: ultrafast laser, femtosecond, ablation, scanning, additive surface structuring, hydrophobicity

A novel additive surface structuring process is devised, which involves localized, intense femtosecond laser irradiation. The irradiation induces a phase explosion of the material being irradiated, and a subsequent ejection of the ablative species that are used as additive building blocks. The ejected species are deposited and accumulated in the vicinity of the ablation site. This redistribution of the material can be repeated and controlled by raster scanning and multiple pulse irradiation. The deposition and accumulation cause the formation of µm-scale three-dimensional structures that surpass the initial surface level. The above-mentioned ablation, deposition, and accumulation all together constitute the proposed additive surface structuring process. In addition, the geometry of the three-dimensional structures can be further modified, if desirable, by a subsequent substractive ablation process. Microstructural analysis reveals a quasi-seamless conjugation between the surface where the structures grow and the structures additively grown by this method, and hence indicates the mechanic robustness of these structures. As a proof of concept, a sub-mm sized re-entrant structure and pillars are fabricated on aluminum substrate by this method. Single units as well as arrayed structures with arbitrary pattern lattice geometry are easily implemented in this additive surface structuring scheme. Engineered surface with desired functionalities can be realized by using this means, i.e., a surface with arrayed pillars being rendered with superhydrophobicity.

Introduction

Laser based additive manufacturing (AM) processes offer unprecedented new opportunities in design and manufacture [START_REF] Gu | Laser additive manufacturing of metallic components: materials, processes and mechanisms[END_REF]. In the vast majority of laser additive manufacturing (LAM) processes, high power, continuous, or long-pulsed lasers are commonly used as high-efficiency thermal sources to heat up metallic powders/bulk, and cause melting/cohesion. Ultrafast laser pulses, due to their low onset of thermal effect, on the one hand, are extensively used in the high-precision substractive processing sector, such as surface structuring [START_REF] Sedao | Self-Arranged Periodic Nanovoids by Ultrafast Laser-Induced Near-Field Enhancement[END_REF][START_REF] Saint-Pierre | Fast Uniform Micro Structuring of DLC Surfaces Using Multiple Ultrashort Laser Spots through Spatial Beam Shaping[END_REF], bulk inscription [START_REF] Liu | Three-Dimensional Self-Organization in Nanocomposite Layered Systems by Ultrafast Laser Pulses[END_REF][START_REF] Mauclair | Dynamic ultrafast laser spatial tailoring for parallel micromachining of photonic devices in transparent materials[END_REF], and thin-film scribing [START_REF] Bonse | Femtosecond laser-induced removal of silicon nitride layers from doped and textured silicon wafers used in photovoltaics[END_REF]; however, on the other hand, they find themselves available for a fairly limited amount of applications in LAM. The few existing applications include ultrafast laser additive manufacturing/surface structuring for high melting temperature metals [START_REF] Nie | Femtosecond laser additive manufacturing of iron and tungsten parts[END_REF][START_REF] Nie | Femtosecond laser melting and resolidifying of high-temperature powder materials[END_REF], laser-induced forward transfer (LIFT) for stacking up miniature building blocks together toward high precision, µm-scale additive processes [START_REF] Delaporte | Laser-induced forward transfer: A high resolution additive manufacturing technology[END_REF][START_REF] Piqué | Laser Printing of Functional Materials: 3D Microfabrication, Electronics and Biomedicine[END_REF], and improving surface finishing of metal parts produced by conventional LAM [START_REF] Mingareev | Femtosecond laser post-processing of metal parts produced by laser additive manufacturing[END_REF][START_REF] Baubeau | System and Method for Additively Manufacturing by Laser Melting of a Powder Bed[END_REF]. In this communication, we would like to broaden the spectrum of ultrafast LAM by exploring a concept of ultrafast laser additive surface structuring (LASS): by taking advantage of the material spallation/phase explosion induced by intense ultrafast laser irradiation, the energetically ejected material from the phase explosion can be transferred and accumulated to form a predefined structure. This approach is powder-free, and the structure building material is directly acquired from the substrate where the additive features are to be grown. Moreover, "finishing touches" can be made to the as-built structures by using the very same ultrafast laser, in order to improve the fineness of the surface finishing of the additively grown features. In the following, the concept is explained firstly. Then, as a proof of concept, two types of structures are fabricated using the proposed ultrafast LASS approach. The aspect of added functions at the surface with these ultrafast laser grown structures is also discussed.

Materials and Methods

A schematic drawing of the laser setup and raster scan strategy is depicted in Figure 1a. For the sake of clarity, the material reported in the Results section is aluminum. In order to verify whether the proposed ultrafast LASS is generic, a few other materials were also chosen for the same test, such as copper and titanium alloy Ti6Al4V, and comparable results were obtained from these materials, too. Nonetheless, a similar test on stainless steel 316L did not yield satisfactory results, suggesting a certain material dependency and limitation of this process. The targets were prepared by conventional metallography procedures with a surface roughness Ra = 20 nm. The micromachining was carried out using a fiber fs laser system (Tangerine HP, Amplitude Systems, Pessac, France). The laser has a central wavelength of 1030 nm with a pulse duration of 300 fs, and a tunable repetition rate from single shot to two MHz. The linearly polarized laser pulses were attenuated, sent through a Galvano scanner, and focused through a 100-mm telecentric f-theta lens. The focused laser spot exhibits a Gaussian profile and the spot diameter (at 1/e 2 ) measures 2ω 0 = 22 µm. A raster scanning strategy was used. The overlap ratio of 0.91 between successive laser pulses and successive scan tracks was kept constant for all of the experiments. This relatively high overlap ratio was intended for a homogeneous energy deposition [START_REF] Eichstädt | Analysis of Irradiation Processes for Laser-Induced Periodic Surface Structures[END_REF]. The laser fluence quoted in this paper is the peak fluence F = 2ε/π ω 0 2 , with ε being the laser pulse energy. clusters and droplets etc., are ejected as a consequence of stress release. Under certain circumstances (a more dedicated discussion is in the following paragraphs), the ejected species land on the adjacent site, adhere to the vicinity of ablation site, and form an accumulation. Such a material redistribution is somehow similar to the work of Temmler, et al. [START_REF] Temmler | Surface structuring by laser remelting of metals[END_REF] (although the mechanism governing the material displacement is totally different). By raster scanning a small area on a substrate, the accumulation continues on and eventually forms a three-dimensional structure by itself, which will be termed as additive structures (AS), as indicated by the white bump in Figure 1a. An AS on aluminum sample was fabricated in this way, and its SEM micrograph is given in Figure 1b. The material to form the AS was sourced from the ablation groove, as marked in Figure 1b, at a laser fluence of 18 J/cm 2 , and 500-kHz repetition rate. The lateral dimension of the AS is about half of the groove width, and the longitudinal dimension is approximately 50 µm, which is better seen from the mechanical cross-section presented in the inset. In order to characterize the AS, we performed microstructural and chemical analysis. The SEM micrograph in Figure 1c shows a FIB prepared cross-section from the substrate-AS junction region. Laminated structures are observed on the AS, the formation of which is due to ablative and accumulative processes. The cross-section elaborates also that the cohesion between the AS and substrate is at the microstructural level. A borderline is evident at the junction, but no major voids nor pores are located there, which implies a robust conjugation between the substrate and the AS. The AS is relatively dense. There are some sub-µm sized voids in the bulk region of the AS, but they are sparse. Nonetheless, it is evident that some micropores are located at the outermost surface region A mechanically prepared cross-section is given as inset. (c) A Focused Ion Beam (FIB) milled cross-section of the additively fabricated part. The platinum layer appearing in the micrograph is a protective coating deposited prior to the milling process.

The topographical analysis was performed using an optical microscope (OM, Zeiss, Oberkochen, Germany) and scanning electron microscope (SEM, FEI Europe B.V., Eindhoven, Netherlands). Cross-section samples for OM were prepared by wheel-saw halving, cold-setting resin mounting, and mechanical polishing. Cross-section samples for SEM inspection were made using a dual beam system SEM and Focused Ion Beam (FIB, FEI Helios Nanolab 600i dualbeam workstation). Energy-dispersive X-ray spectroscopy (EDX, Brucker, Bremen, Germany) was used to evaluate the surface chemistry change. A Vikers microindentation (Cetim, Saint-Etienne, France) was also performed to access hardness, with a loading force of two N. All of the hardness values quoted in the text were averaged values from five individual measurements. For the wetting test, a three-µL water droplet was deposited on the surface by a microsyringe, and the side-on view was captured by a dedicated camera. The contact angle was deduced from the registered images using software Digidrop (version 13.06.3.12GB, GBX, Romans sur Isère, France).

Results

The lower-right part of the schematic drawing shown in Figure 1a can be used to illustrate the concept of the LASS by intense ultrafast laser irradiation (roughly defined as fluence >5~10 times the ablation threshold). Then, the material experiences a photo excitation, electron-phonon non-equilibration-enhanced electron heat conduction before equilibrium with the lattice, and then undergoes spallation and phase explosion [START_REF] Zhigilei | Atomistic Modeling of Short Pulse Laser Ablation of Metals: Connections between Melting, Spallation, and Phase Explosion †[END_REF]. Various species, depending on the laser fluence, consisting of anything from liquid layers and/or large droplets to a mixture of vapor-phase atom clusters and droplets etc., are ejected as a consequence of stress release. Under certain circumstances (a more dedicated discussion is in the following paragraphs), the ejected species land on the adjacent site, adhere to the vicinity of ablation site, and form an accumulation. Such a material redistribution is somehow similar to the work of Temmler, et al. [START_REF] Temmler | Surface structuring by laser remelting of metals[END_REF] (although the mechanism governing the material displacement is totally different). By raster scanning a small area on a substrate, the accumulation continues on and eventually forms a three-dimensional structure by itself, which will be termed as additive structures (AS), as indicated by the white bump in Figure 1a. An AS on aluminum sample was fabricated in this way, and its SEM micrograph is given in Figure 1b. The material to form the AS was sourced from the ablation groove, as marked in Figure 1b, at a laser fluence of 18 J/cm 2 , and 500-kHz repetition rate. The lateral dimension of the AS is about half of the groove width, and the longitudinal dimension is approximately 50 µm, which is better seen from the mechanical cross-section presented in the inset.

In order to characterize the AS, we performed microstructural and chemical analysis. The SEM micrograph in Figure 1c shows a FIB prepared cross-section from the substrate-AS junction region. Laminated structures are observed on the AS, the formation of which is due to ablative and accumulative processes. The cross-section elaborates also that the cohesion between the AS and substrate is at the microstructural level. A borderline is evident at the junction, but no major voids nor pores are located there, which implies a robust conjugation between the substrate and the AS. The AS is relatively dense. There are some sub-µm sized voids in the bulk region of the AS, but they are sparse. Nonetheless, it is evident that some micropores are located at the outermost surface region and the lower outer surface region. Those micropores located in the outermost surface region could be potentially eliminated by a substractive ablation process step, which is discussed later in this communication. An EDX spectrum was acquired from different locations across the entire AS, and compared with the spectrum obtained from the substrate. In the AS, a small increase of oxygen and nitrogen is deduced from their characteristic peaks' intensity in the spectra. This chemical composition change may be due to an oxidation/nitration or air trapping (due to the presence of the sub-µm voids) within the AS during the process.

As mentioned in Section 2, the AS can be achieved on aluminum but not stainless steel; a typical comparison can be viewed in Figure 2a,b, with the cross-sections of these two materials treated at a fluence of 18 J/cm 2 and a 250-kHz repetition rate. The laser processing is shown to be strongly material-dependent in the ~100 kHz repetition rate regime [START_REF] Sedao | Influence of Pulse Repetition Rate on Morphology and Material Removal Efficiency of Ultrafast Laser Ablated Metallic Surfaces[END_REF][START_REF] Zuhlke | Formation of multiscale surface structures on nickel via above surface growth and below surface growth mechanisms using femtosecond laser pulses[END_REF], resulting either in material accumulation on the side of the ablation groove in the aluminum case, or to significant roughness development in the case of stainless steel. The laser plasma hydrodynamics and ablation particles shielding may be taken account of in these observations. The interaction of ultrafast laser at fluence exceeding the ablation threshold with metal targets is associated with a large variety of physical phenomena, taking place from femtosecond up to microsecond timescales [START_REF] Zhigilei | Atomistic Modeling of Short Pulse Laser Ablation of Metals: Connections between Melting, Spallation, and Phase Explosion †[END_REF][START_REF] Anisimov | Selected problems of laser ablation theory[END_REF]. At 250 kHz (a pulse-to-pulse interval of four microseconds), the pulse-by-pulse thermal accumulation alone does not play a major role, as the irradiated surfaces have enough time to cool down during the interval. Besides thermal accumulation, the laser ablation by high-intensity pulses is accompanied by plasma plume expansion away from the metal target [START_REF] Anisimov | Selected problems of laser ablation theory[END_REF]. Figure 2c depicts the initiation of ablation simulated by two-dimensional (2D) compressible Navier-Stokes equations [START_REF] Sedao | Self-Arranged Periodic Nanovoids by Ultrafast Laser-Induced Near-Field Enhancement[END_REF][START_REF] Colombier | Guiding heat in laser ablation of metals on ultrafast timescales: an adaptive modeling approach on aluminum[END_REF], taking account of Gaussian pulse energy deposition on the surface, lattice heating, and hydrodynamic movement, which causes strong pressure gradients and material removal. The lowest density corresponds to hot laser-induced plasma, the highest density corresponds to unaffected ablation area, and the intermediate density corresponds to a liquid state. The central part of the plume leaves the surface and expands longitudinally above the surface; however, the corners of the plasma plume remain less hot, may re-solidify before the arrival of the next pulse, and then form a redistributed aluminum layer above the initial level. In this case, the consequent pulse-by-pulse ablation with a scan from left to right leads to a pronounced microstructure on the left side of the laser-processed area, as displayed in Figure 2a. Other possible mechanisms of material re-deposition include Marangoni melt flow and recoil vapor pressure [START_REF] Temmler | Surface structuring by laser remelting of metals[END_REF][START_REF] Volkov | Melt dynamics and melt-through time in continuous wave laser heating of metal films: Contributions of the recoil vapor pressure and Marangoni effects[END_REF]. However, these effects fail to explain why the accumulated material is observed above the ablated area, but not outside it. The interaction of ultrafast laser at fluence exceeding the ablation threshold with metal targets is associated with a large variety of physical phenomena, taking place from femtosecond up to microsecond timescales [START_REF] Zhigilei | Atomistic Modeling of Short Pulse Laser Ablation of Metals: Connections between Melting, Spallation, and Phase Explosion †[END_REF][START_REF] Anisimov | Selected problems of laser ablation theory[END_REF]. At 250 kHz (a pulse-to-pulse interval of four microseconds), the pulse-by-pulse thermal accumulation alone does not play a major role, as the irradiated surfaces have enough time to cool down during the interval. Besides thermal accumulation, the laser ablation by high-intensity pulses is accompanied by plasma plume expansion away from the metal target [START_REF] Anisimov | Selected problems of laser ablation theory[END_REF]. Figure 2c depicts the initiation of ablation simulated by two-dimensional (2D) compressible Navier-Stokes equations [START_REF] Sedao | Self-Arranged Periodic Nanovoids by Ultrafast Laser-Induced Near-Field Enhancement[END_REF][START_REF] Colombier | Guiding heat in laser ablation of metals on ultrafast timescales: an adaptive modeling approach on aluminum[END_REF], taking account of Gaussian pulse energy deposition on the surface, lattice heating, and hydrodynamic movement, which causes strong pressure gradients and material removal. The lowest density corresponds to hot laser-induced plasma, the highest density corresponds to unaffected ablation area, and the intermediate density corresponds to a liquid state. The central part of the plume leaves the surface and expands longitudinally above the surface; however, the corners of the plasma plume remain less hot, may re-solidify before the arrival of the next pulse, and then form a redistributed aluminum layer above the initial level. In this case, the consequent pulse-by-pulse ablation with a scan from left to right leads to a pronounced microstructure on the left side of the laser-processed area, as displayed in Figure 2a. Other possible mechanisms of material re-deposition include Marangoni melt flow and recoil vapor pressure [START_REF] Temmler | Surface structuring by laser remelting of metals[END_REF][START_REF] Volkov | Melt dynamics and melt-through time in continuous wave laser heating of metal films: Contributions of the recoil vapor pressure and Marangoni effects[END_REF]. However, these effects fail to explain why the accumulated material is observed above the ablated area, but not outside it. Another characteristic feature of the ultrashort laser ablation of metal targets is the formation of nanoparticles of sizes up to r = 100 nm in plasma plume [START_REF] Bourquard | In situ diagnostic of the size distribution of nanoparticles generated by ultrashort pulsed laser ablation in vacuum[END_REF][START_REF] Noël | Investigation of nanoparticle generation during femtosecond laser ablation of metals[END_REF][START_REF] Amoruso | Femtosecond laser pulse irradiation of solid targets as a general route to nanoparticle formation in a vacuum[END_REF][START_REF] Guillermin | Optical emission and nanoparticle generation in Al plasmas using ultrashort laser pulses temporally optimized by real-time spectroscopic feedback[END_REF][START_REF] Tsakiris | Ultrashort laser ablation of bulk copper targets: Dynamics and size distribution of the generated nanoparticles[END_REF]. The species are known to be moving much slower than the plasma plume, with the velocities slightly exceeding 100 m/s [START_REF] Noël | Investigation of nanoparticle generation during femtosecond laser ablation of metals[END_REF][START_REF] Tsakiris | Ultrashort laser ablation of bulk copper targets: Dynamics and size distribution of the generated nanoparticles[END_REF]. The presence of slow moving nanoparticles generated by a laser pulse may influence the following laser pulse interaction with the surface. To investigate the effects of light absorption on the surface, with and without transmission through nanoparticles, we use an ablation model, including Maxwell equations [START_REF] Rudenko | Light absorption by surface nanoholes and nanobumps[END_REF] coupled with electron-ion heat transfer equations [START_REF] Colombier | Guiding heat in laser ablation of metals on ultrafast timescales: an adaptive modeling approach on aluminum[END_REF]. The spherical nanoparticles Another characteristic feature of the ultrashort laser ablation of metal targets is the formation of nanoparticles of sizes up to r = 100 nm in plasma plume [START_REF] Bourquard | In situ diagnostic of the size distribution of nanoparticles generated by ultrashort pulsed laser ablation in vacuum[END_REF][START_REF] Noël | Investigation of nanoparticle generation during femtosecond laser ablation of metals[END_REF][START_REF] Amoruso | Femtosecond laser pulse irradiation of solid targets as a general route to nanoparticle formation in a vacuum[END_REF][START_REF] Guillermin | Optical emission and nanoparticle generation in Al plasmas using ultrashort laser pulses temporally optimized by real-time spectroscopic feedback[END_REF][START_REF] Tsakiris | Ultrashort laser ablation of bulk copper targets: Dynamics and size distribution of the generated nanoparticles[END_REF]. The species are known to be moving much slower than the plasma plume, with the velocities slightly exceeding 100 m/s [START_REF] Noël | Investigation of nanoparticle generation during femtosecond laser ablation of metals[END_REF][START_REF] Tsakiris | Ultrashort laser ablation of bulk copper targets: Dynamics and size distribution of the generated nanoparticles[END_REF]. The presence of slow moving nanoparticles generated by a laser pulse may influence the following laser pulse interaction with the surface. To investigate the effects of light absorption on the surface, with and without transmission through nanoparticles, we use an ablation model, including Maxwell equations [START_REF] Rudenko | Light absorption by surface nanoholes and nanobumps[END_REF] coupled with electron-ion heat transfer equations [START_REF] Colombier | Guiding heat in laser ablation of metals on ultrafast timescales: an adaptive modeling approach on aluminum[END_REF]. The spherical nanoparticles with a radius r = 50 nm and a concentration of C = 50 µm -2 are distributed randomly in an ellipsoid-centered region at distance of 50 µm above the initial surface level, with a radius Rz = 10 µm in the propagation direction, and Rx = 20 µm in the transverse direction. The nanoparticles are assumed to be created by the first laser pulse. The numerical results show the surface profile after N = one and N = five pulse irradiation with and without taking account of the energy loss in transmission through nanoparticles in Figure 2d. Although only a slight difference is seen after the first pulse irradiation, the inhomogeneous distribution of the energy due to the presence of nanoparticles seriously degrades the ablation quality after five consecutive pulses: the ablation profile is now asymmetric, with roughness features up to a few hundred nm. It is worth mentioning that owing to the low reflectivity of stainless steel (R = 0.56) compared to that of aluminum (R = 0.96), the greater transmission of laser pulse through steel nanoparticles would cause a stronger surface roughness. The effects of the interaction between the nanoparticles and laser-induced plasma created by the next pulse may as well lead to uncontrolled material deposition inside the crater. Both phenomena may have an impact on the quality and/or surface morphology [START_REF] Noël | Investigation of nanoparticle generation during femtosecond laser ablation of metals[END_REF]. The difference in ablated volume and depth is revealed by simulations, taking into account the presence of nanoparticles in Figure 2d already after five pulses of irradiation. Thermal effects might be at the origin of further ablation crater degradation, as the diffusivity of stainless steel D = k i /ρC i ≈ 5 × 10 -6 m 2 /s (k i is the lattice thermal conductivity, C i is the lattice heat capacity, and is the lattice density), which is six times lower than the diffusivity of aluminum D ≈ 3 × 10 -5 m 2 /s. For aluminum, the material accumulates only at the corners of the laser-processed area, leaving the central part inside the ablation crater free from micro-debris [START_REF] Sedao | Influence of Pulse Repetition Rate on Morphology and Material Removal Efficiency of Ultrafast Laser Ablated Metallic Surfaces[END_REF], and facilitating the proposed technique of additive surface structuring.

The application of such AS for surface functionalization is multifold. One of the simplest is implemented by building two basic AS blocks against one to another, and is reported in Figure 3a. The inset is a mechanical cut cross-section revealing the negatively inclining feature of the sidewalls of the AS. Such geometry is otherwise termed the re-entrant shape, and is capable of rendering a surface liquid repellent property [START_REF] Dufour | From micro to nano reentrant structures: hysteresis on superomniphobic surfaces[END_REF]. In order to test this functionality, a large surface of a few mm 2 area was fabricated with repeating "re-entrant" pattern periodically (Figure 3b). The surface was hydrophilic and anisotropic right after the LASS process, but turned to isotropic and hydrophobic after a thermal treatment at 150 • C for two hours: a droplet could sit on the AS surface without spreading, as shown in the inset. Such surface morphology, once capped with a low surface energy coating, might also exhibit oleophobic characteristics [START_REF] Li | Oil droplet self-transportation on oleophobic surfaces[END_REF]; experiments on coating preparation and oleophobicity test are currently underway. It is also worth noting that upscaling such ultrafast LASS to an even larger surface, in the order of cm 2 towards m 2 , is fairly straightforward nowadays, as it is based on standard ultrafast laser beam shaping, scanning, and processing tools [START_REF] Saint-Pierre | Fast Uniform Micro Structuring of DLC Surfaces Using Multiple Ultrashort Laser Spots through Spatial Beam Shaping[END_REF].

Furthermore, an additional merit offered by the ultrafast LASS process is worth illustrating. Given that the ultrafast laser is also a high-precision micromachining tool, additional laser processing steps can be added after the AS is fabricated, and the surface finishing of the AS can be improved by using the very same laser source. For instance, the edges of AS can be sharpened by ultrafast laser ablation, as shown in Figure 4. The four sub-mm sized pillars were fabricated by the LASS process (by circulating the laser beam from the center to outer region), and they had a mushroom-shaped geometry right after the process (a side-on view of the mushroom-shaped AS is given as an inset in Figure 4a). The cap part of the "mushroom" is trimmed to a pillar shape, as shown in Figure 4a, after an additional ultrafast laser substractive scan along the contour of the AS at a reduced laser fluence (7 J/cm 2 ). The sharp edge is better viewed in Figure 4b, where the sample is tilted by a nearly 90 • angle. The pillars in this particular case are 250 µm in diameter and 100-µm high. Pillars with height (the elevation from the substrate surface to the peak of the pillars) up to approximately 300 µm and small diameters can also be made by this strategy; the side-on view is given in the Figure 4b inset. The large surface production of the AS, which is similar to those in Figure 4a, is also easily implemented, and an example is presented in Figure 4c. The inset in Figure 4c is a wetting test on the surface with a large array of sub-mm sized pillars, where a superhydrophobicity contact angle of 150 • C is observed (after a thermal treatment at 150 • C for two hours). Mechanical property-wise, the microindentation test revealed a decreased hardness at the surface of the AS, a Vickers hardness value at two N load HV 2N = 230 at the AS, compared to a Vickers HV 2N = 252 of the substrate. The reduction of the hardness is thought to be related to the presence of the micropores and reduced density in the AS compared to bulk aluminum. It is obvious that the substractive process step can be applied to remove the previously mentioned micropores lodged in the outermost surface region. If this surface porous layer were removed, the microhardness would be further improved. A more comprehensive study on this matter and process optimization will surely be meaningful toward further exploring the value of this additive and subtractive surface structuring approach.

five pulses of irradiation. Thermal effects might be at the origin of further ablation crater degradation, as the diffusivity of stainless steel 𝐷 𝑘 𝜌𝐶 ⁄ 5 10 m s ⁄ ( 𝑘 is the lattice thermal conductivity, 𝐶 is the lattice heat capacity, and ρ is the lattice density), which is six times lower than the diffusivity of aluminum 𝐷 3 10 m s ⁄ . For aluminum, the material accumulates only at the corners of the laser-processed area, leaving the central part inside the ablation crater free from microdebris [START_REF] Sedao | Influence of Pulse Repetition Rate on Morphology and Material Removal Efficiency of Ultrafast Laser Ablated Metallic Surfaces[END_REF], and facilitating the proposed technique of additive surface structuring.

The application of such AS for surface functionalization is multifold. One of the simplest is implemented by building two basic AS blocks against one to another, and is reported in Figure 3a. The inset is a mechanical cut cross-section revealing the negatively inclining feature of the sidewalls of the AS. Such geometry is otherwise termed the re-entrant shape, and is capable of rendering a surface liquid repellent property [START_REF] Dufour | From micro to nano reentrant structures: hysteresis on superomniphobic surfaces[END_REF]. In order to test this functionality, a large surface of a few mm 2 area was fabricated with repeating "re-entrant" pattern periodically (Figure 3b). The surface was hydrophilic and anisotropic right after the LASS process, but turned to isotropic and hydrophobic after a thermal treatment at 150 °C for two hours: a droplet could sit on the AS surface without spreading, as shown in the inset. Such surface morphology, once capped with a low surface energy coating, might also exhibit oleophobic characteristics [START_REF] Li | Oil droplet self-transportation on oleophobic surfaces[END_REF]; experiments on coating preparation and oleophobicity test are currently underway. It is also worth noting that upscaling such ultrafast LASS to an even larger surface, in the order of cm 2 towards m 2 , is fairly straightforward nowadays, as it is based on standard ultrafast laser beam shaping, scanning, and processing tools [START_REF] Saint-Pierre | Fast Uniform Micro Structuring of DLC Surfaces Using Multiple Ultrashort Laser Spots through Spatial Beam Shaping[END_REF]. Furthermore, an additional merit offered by the ultrafast LASS process is worth illustrating. Given that the ultrafast laser is also a high-precision micromachining tool, additional laser processing steps can be added after the AS is fabricated, and the surface finishing of the AS can be improved by using the very same laser source. For instance, the edges of AS can be sharpened by ultrafast laser ablation, as shown in Figure 4. The four sub-mm sized pillars were fabricated by the LASS process (by circulating the laser beam from the center to outer region), and they had a mushroom-shaped geometry right after the process (a side-on view of the mushroom-shaped AS is given as an inset in Figure 4a). The cap part of the "mushroom" is trimmed to a pillar shape, as shown in Figure 4a, after an additional ultrafast laser substractive scan along the contour of the AS at a reduced laser fluence (7 J/cm 2 ). The sharp edge is better viewed in Figure 4b, where the sample is tilted by a nearly 90° angle. The pillars in this particular case are 250 µm in diameter and 100-µm high. Pillars with height (the elevation from the substrate surface to the peak of the pillars) up to approximately 300 µm and small diameters can also be made by this strategy; the side-on view is given in the Figure 4b inset. The large surface production of the AS, which is similar to those in Figure 4a, is also easily implemented, and an example is presented in Figure 4c. The inset in Figure 4c is a wetting test on the surface with a large array of sub-mm sized pillars, where a superhydrophobicity contact angle of 150 °C is observed (after a thermal treatment at 150 °C for two hours). Mechanical property-wise, the microindentation test revealed a decreased hardness at the surface of the AS, a Vickers hardness value at two N load HV2N = 230 at the AS, compared to a Vickers HV2N = 252 of the substrate. The reduction of the hardness is thought to be related to the presence of the micropores and reduced density in the AS compared to bulk aluminum. It is obvious that the substractive process step can be applied to remove the previously mentioned micropores lodged in the outermost surface region. If this surface porous layer were removed, the microhardness would be further improved. A more comprehensive study on this matter and process optimization will surely be meaningful toward further exploring the value of this additive and subtractive surface structuring approach.

Discussion

This report proposes a novel ultrafast LASS approach that is based on intense femtosecond laser irradiation, ablation, and subsequent material ejection. The inhomogeneous distribution of hot plasma induced by intense laser irradiation contributes to the accumulation of ablated species near the ablation area. The accumulation leads to the formation of the additive manufactured structures. As a proof of concept, one-dimensional re-entrant surface structures are fabricated using the approach. The advantage of ultrafast laser refining the additively manufactured structures is also demonstrated. These femtosecond laser additively manufactured geometries, once fabricated on a large scale, can render the underlying surfaces with desired properties such as anisotropic wetting

Discussion

This report proposes a novel ultrafast LASS approach that is based on intense femtosecond laser irradiation, ablation, and subsequent material ejection. The inhomogeneous distribution of hot plasma induced by intense laser irradiation contributes to the accumulation of ablated species near the ablation area. The accumulation leads to the formation of the additive manufactured structures. As a proof of concept, one-dimensional re-entrant surface structures are fabricated using the approach. The advantage of ultrafast laser refining the additively manufactured structures is also demonstrated. These femtosecond laser additively manufactured geometries, once fabricated on a large scale, can render the underlying surfaces with desired properties such as anisotropic wetting and superhydrophobicity. Although the above results were obtained from aluminum substrates, further study suggests that the method is quite generic and applicable to certain other metals and/or alloys. Supplementary tests have confirmed the applicability of this process mode to copper and titanium alloy Ti6Al4V, at adapted laser fluences. Nonetheless, a similar test on stainless steel 316L did not yield satisfactory results. Numerical analysis suggests that the presence of laser-induced nanoparticles, optical properties such as reflectance and transmission, and material properties such as diffusivity may play a role in the observed discrepancies in stainless steel with respect to the other metal/alloys. It is clear that a better understanding is still required toward the further development of the process. In the meantime, the mechanical strength of these structures needs to be characterized quantitatively. Surface functionalization, especially potentials in adding superomniphobic (hydrophobic and oleophobic at the same time) properties to an engineered surface, will be explored.

Figure 1 .

 1 Figure 1. Ultrafast laser additive surface structuring (LASS) explained: (a) Laser scan path is indicated by the red arrows: the laser beam movement starts from the far side and advances linearly toward the near side to form a scan track. The scan tracks start from the right side and end on the left. The numbers 1 and 2 represent the beginning and the end of the process, respectively; (b) scanning electron microscope (SEM) micrograph showing the site of ablation, and additively grown part. A mechanically prepared cross-section is given as inset. (c) A Focused Ion Beam (FIB) milled crosssection of the additively fabricated part. The platinum layer appearing in the micrograph is a protective coating deposited prior to the milling process.

Figure 1 .

 1 Figure 1. Ultrafast laser additive surface structuring (LASS) explained: (a) Laser scan path is indicated by the red arrows: the laser beam movement starts from the far side and advances linearly toward the near side to form a scan track. The scan tracks start from the right side and end on the left. The numbers 1 and 2 represent the beginning and the end of the process, respectively; (b) scanning electron microscope (SEM) micrograph showing the site of ablation, and additively grown part.A mechanically prepared cross-section is given as inset. (c) A Focused Ion Beam (FIB) milled cross-section of the additively fabricated part. The platinum layer appearing in the micrograph is a protective coating deposited prior to the milling process.

Figure 2 .

 2 Figure 2. Cross-section images of laser processed (a) aluminum, and (b) stainless steel 316L, at a fluence of 18 J/cm 2 and pulse repetition rate of 250 kHz. The dashed line boxes are visual guides for highlighting the features inside the ablation grooves; (c) Density snapshot showing plasma plume expansion from aluminum surface 50 picoseconds after irradiation; (d) Multi-pulse simulations of energy deposition on stainless steel surface. Top row N = 0, initial surface; middle row N = one pulse; and bottom row N = five pulses. In the middle and bottom rows, unaffected (left) /affected (right) laser structuring by the presence of nanoparticles of r = 50 nm and concentration of C = 50 µm -2 .

Figure 2 .

 2 Figure 2. Cross-section images of laser processed (a) aluminum, and (b) stainless steel 316L, at a fluence of 18 J/cm 2 and pulse repetition rate of 250 kHz. The dashed line boxes are visual guides for highlighting the features inside the ablation grooves; (c) Density snapshot showing plasma plume expansion from aluminum surface 50 picoseconds after irradiation; (d) Multi-pulse simulations of energy deposition on stainless steel surface. Top row N = 0, initial surface; middle row N = one pulse; and bottom row N = five pulses. In the middle and bottom rows, unaffected (left) /affected (right) laser structuring by the presence of nanoparticles of r = 50 nm and concentration of C = 50 µm -2 .

Figure 3 .

 3 Figure 3. (a) Top view of the re-entrant structure realized by building the additive structures (AS) block from two sides. The dash line and the arrow are the visual indication of a cross-section. The inset is a cross-section of this re-entrant structure; (b) The structure unit shown in (a) is easily implemented on a large surface scale. This surface exhibits isotropic hydrophobicity (lower bottom inset).

Figure 3 .

 3 Figure 3. (a) Top view of the re-entrant structure realized by building the additive structures (AS) block from two sides. The dash line and the arrow are the visual indication of a cross-section. The inset is a cross-section of this re-entrant structure; (b) The structure unit shown in (a) is easily implemented on a large surface scale. This surface exhibits isotropic hydrophobicity (lower bottom inset).

Figure 4 .

 4 Figure 4. (a) Four sub-mm sized pillars made by the ultrafast laser additive surface structuring (LASS) process, plus ultrafast laser substractive ablation at the contour of the pillar blocks to sharpen the edges. The inset shows a single AS unit without its edge being sharpened; (b) Tilted view of the pillars. The pillars can be grown higher, at the cost of pillar diameter, as shown in the inset; (c) Pillars similar to those in (a) are fabricated on a large scale for achieving a superhydrophobicity at the surface, as demonstrated in the inset.

Figure 4 .

 4 Figure 4. (a) Four sub-mm sized pillars made by the ultrafast laser additive surface structuring (LASS) process, plus ultrafast laser substractive ablation at the contour of the pillar blocks to sharpen the edges. The inset shows a single AS unit without its edge being sharpened; (b) Tilted view of the pillars. The pillars can be grown higher, at the cost of pillar diameter, as shown in the inset; (c) Pillars similar to those in (a) are fabricated on a large scale for achieving a superhydrophobicity at the surface, as demonstrated in the inset.

Funding:

The authors thank French ANR for the Equipex MANUTECH-USD support (Investissements d'Avenir ANR-10-EQPX-36-01). This work was carried out for LABEX MANUTECH-SISE financed project ICRAM. This work was also supported by the IMOTEP project within the program 'Investissements d'Avenir' operated by ADEME.

Conflicts of Interest:

The authors declare no conflict of interest.