Da-Jung Cho
email: dajungcho@yonsei.ac.kr

Yo-Sub Han

Kai Salomaa
email: ksalomaa@cs.queensu.ca

Taylor J Smith
email: tsmith@cs.queensu.ca

Site-Directed Insertion: Decision Problems, Maximality and Minimality

Site-directed insertion is an overlapping insertion operation that can be viewed as analogous to the overlap assembly or chop operations that concatenate strings by overlapping a suffix and a prefix of the argument strings. We consider decision problems and language equations involving site-directed insertion. By relying on the tools provided by semantic shuffle on trajectories we show that one variable equations involving site-directed insertion and regular constants can be solved. We consider also maximal and minimal variants of the site-directed insertion operation.

Introduction

Site-directed mutagenesis is one of the most important techniques for generating mutations on specific sites of DNA using polymerase chain reaction (PCR) based methods [START_REF] Reikofski | Polymerase chain reaction (PCR) techniques for sitedirected mutagenesis[END_REF]. The algorithmic applications of mutagenesis have been considered e.g. by Franco and Manca [START_REF] Franco | Algorithmic applications of XPCR[END_REF]. Contextual insertion/deletion systems in the study of molecular computing have been used, e.g. by Kari and Thierrin [START_REF] Kari | Contextual insertions/deletions and computability[END_REF], Daley et al. [START_REF] Daley | Circular contextual insertions/deletions with applications to biomolecular computation[END_REF] and Enaganti et al. [START_REF] Enaganti | A formal language model of DNA polymerase enzymatic activity[END_REF].

Site-directed insertion (SDI) of a string y into a string x involves matching an outfix of y with a substring of x and inserting the "middle part" of y not belonging to the outfix into x. Site-directed insertion has earlier been considered under the name outfix-guided insertion [START_REF] Cho | Outfix-guided insertion[END_REF]. The operation is an overlapping variant of the insertion operation in the same sense as the overlap assembly, a.k.a. chop operation, is a variant of string concatenation [START_REF] Csuhaj-Varju | Self-assembly of string and languages. Theoret[END_REF][START_REF] Enaganti | On the overlap assembly of strings and languages[END_REF][START_REF] Holzer | Descriptional complexity of chop operations on unary and finite languages[END_REF][START_REF] Holzer | The chop of languages[END_REF].

The maximal (respectively, minimal) SDI of a string y into a string x requires that, at the chosen location of x, the operation matches a maximal (respectively, minimal) outfix of y with a substring of x. This is analogous to the maximal and minimal chop operations studied by Holzer et al. [START_REF] Holzer | The chop of languages[END_REF].

Site-directed insertion can be represented as a semantic shuffle on trajectories (SST). Shuffle on trajectories was introduced by Mateescu et al. [START_REF] Mateescu | Shuffle on trajectories: Syntactic constraints[END_REF] and the extension to SST is due to Domaratzki [START_REF] Domaratzki | Semantic shuffle on and deletion along trajectories[END_REF]. Further extensions of the shuffle-ontrajectories operation have been studied by Domaratzki et al. [START_REF] Domaratzki | Interpreted trajectories[END_REF].

Here we study decision problems and language equations involving sitedirected insertion and its maximal and minimal variants. The representation of SDI as a semantic shuffle on a regular set of trajectories gives regularity preserving left-and right-inverses of the operation. By the general results of Kari [START_REF] Kari | On language equations with invertible operations[END_REF] on the decidability of equations, translated for SST by Domaratzki [START_REF] Domaratzki | Semantic shuffle on and deletion along trajectories[END_REF], this makes it possible to decide linear equations involving SDI where the constants are regular languages.

The maximal and minimal SDI operations do not, in general, preserve regularity. This means that the operations cannot be represented by SST [START_REF] Domaratzki | Semantic shuffle on and deletion along trajectories[END_REF] (on a regular set of trajectories) and the above tools are not available to deal with language equations. We show that for maximal and minimal SDI certain independence properties related to coding applications [START_REF] Jürgensen | Codes. In: Handbook of Formal Languages[END_REF] can be decided in a polynomial time. The decidability of whether a regular language is closed under max/min SDI remains open.

In the last section we give a tight bound for the nondeterministic state complexity of alphabetic SDI, where the matching outfix must consist of a prefix and suffix of length exactly one. An upper bound for the state complexity of the general site-directed insertion is known but it remains open whether the bound is optimal.

Preliminaries

We assume the reader to be familiar with the basics of finite automata, regular languages and context-free languages [START_REF] Shallit | A Second Course in Formal Languages and Automata Theory[END_REF]. Here we briefly recall some notation.

Let Σ be an alphabet and w ∈ Σ * . If we can write w = xyz we say that the pair (x, z) is an outfix of w. The outfix (x, z) is a nontrivial outfix of w if x = ε and z = ε. For L ⊆ Σ * , L = Σ * -L is the complement of L.

A nondeterministic finite automaton (NFA) is a tuple A = (Σ, Q, δ, q 0 , F ) where Σ is the input alphabet, Q is the finite set of states, δ : Q × Σ → 2 Q is the transition function, q 0 ∈ Q is the initial state and F ⊆ Q is the set of final states. In the usual way δ is extended as a function Q × Σ * → 2 Q and the language accepted by A is L(A) = {w ∈ Σ * | δ(q 0 , w) ∩ F = ∅}. The automaton A is a deterministic finite automaton (DFA) if |δ(q, a)| ≤ 1 for all q ∈ Q and a ∈ Σ. It is well known that the deterministic and nondeterministic finite automata recognize the class of regular languages.

The so called fooling set lemma gives a technique for establishing lower bounds for the size of NFAs: Lemma 1 (Birget 1992 [1]). Let L ⊆ Σ * be a regular language. Suppose that there exists a set P = {(x i , w i ) | 1 ≤ i ≤ n} of pairs of strings such that: (i) x i w i ∈ L for 1 ≤ i ≤ n, and, (ii) if i = j, then x i w j ∈ L or x j w i ∈ L for 1 ≤ i, j ≤ n. Then, any minimal NFA for L has at least n states.

Finally we recall some notions concerning operations on languages and language equations. Let be a binary operation on languages, and L, R are languages over an alphabet Σ.

(i) The language L is closed under if L L ⊆ L. (ii) The language L is -free with respect to R if L R = ∅. (iii) The language L is -independent with respect to R if (L Σ + ) ∩ R = ∅. (iv) A solution for an equation X L = R (respectively, L X = R) is a language S ⊆ Σ * such that S L = R (respectively, L S = R).
The -freeness and independence properties can be related to coding applications, where it might be desirable that we cannot produce new strings by applying an operation, such as site-directed insertion, to strings of the language. Domaratzki [START_REF] Domaratzki | Trajectory-based codes[END_REF] defines trajectory-based codes analogously with (iii). As we will see, languages that are site-directed insertion independent with respect to themselves have a definition closely resembling outfix-codes of index one [START_REF] Jürgensen | Codes. In: Handbook of Formal Languages[END_REF].

3 Site-Directed Insertion

The site-directed insertion is a partially overlapping insertion operation analogously as the overlap-assembly (or self-assembly) [START_REF] Csuhaj-Varju | Self-assembly of string and languages. Theoret[END_REF][START_REF] Enaganti | On the overlap assembly of strings and languages[END_REF] models an overlapping concatenation of strings. The overlapping concatenation operation is also called the chop operation [START_REF] Holzer | The chop of languages[END_REF].

The site-directed insertion (SDI) of a string y into a string x is defined as

x sdi ← y = {x 1 uzvx 2 | x = x 1 uvx 2 , y = uzv, u = , v = }.
The above definition requires that the pair (u, v) is a nontrivial outfix of the string y and uv is a substring of x. If y = uzv is inserted into x by matching the outfix with a substring uv of x, we say that (u, v) is an insertion guide for the operation. Note that a previous paper [START_REF] Cho | Outfix-guided insertion[END_REF] uses the name "outfix-guided insertion" for the same operation. The site-directed insertion operation is extended in the usual way for languages by setting

L 1 sdi ← L 2 = wi∈Li,i=1,2 w 1 sdi ← w 2 .
We recall that regular languages are closed under site-directed insertion.

Proposition 1 ([2]

). If A and B are NFAs with m and n states, respectively, the language L(A) sdi ← L(B) has an NFA with 3mn + 2m states.

A simpler form of the overlap-assembly operation requires the overlapping part of the strings to consist of a single letter. This operation is called "chop" by Holzer and Jacobi [START_REF] Holzer | Descriptional complexity of chop operations on unary and finite languages[END_REF] but the later definition of the chop-operation [START_REF] Holzer | The chop of languages[END_REF] coincides with general overlap-assembly [START_REF] Enaganti | On the overlap assembly of strings and languages[END_REF]. Analogously we define alphabetic site-directed insertion by requiring that the overlapping prefix and suffix of the inserted string each consist of a single letter.

The alphabetic site-directed insertion of a string y into a string x is

x a-sdi ← y = {x 1 azbx 2 | x = x 1 abx 2 , y = azb, a, b ∈ Σ, x 1 , x 2 , z ∈ Σ * }.
Note that the alphabetic site-directed insertion will have different closure properties than the standard site-directed insertion. For example, it is not difficult to see that the context-free languages are closed under alphabetic sitedirected insertion, while the context-free languages are not closed under general site-directed insertion [START_REF] Cho | Outfix-guided insertion[END_REF].

Decision problems

For a regular language L, it is decidable whether L is closed under site-directed insertion. The algorithm relies on the construction of Proposition 1 and operates in polynomial time when L is specified by a DFA [START_REF] Cho | Outfix-guided insertion[END_REF]. Deciding whether a contextfree language is closed under site-directed insertion is undecidable [START_REF] Cho | Outfix-guided insertion[END_REF].

A language L is sdi ←-free, or SDI-free, with respect to R if no string of R can be site-directed inserted into a string of L, that is, if L sdi ← R = ∅.
The language L is SDI-independent with respect to R if site-directed inserting a non-empty string into L cannot produce a string of R. Note that L being SDI-independent with respect to itself resembles the notion of L being an outfix-code of index one [START_REF] Jürgensen | Codes. In: Handbook of Formal Languages[END_REF] with the difference that we require the outfix to be nontrivial. For example, {ab, b} is SDI-independent but it is not an outfix-code of index one.

Theorem 1. For NFAs A and B we can decide in polynomial time whether (i) L(A) is SDI-free (or SDI-independent) with respect to L(B).

(ii) L(A) is alphabetic SDI-free (or alphabetic SDI-independent) with respect to L(B).

For context-free languages deciding SDI-freeness and SDI-independence is undecidable.

Proposition 2. For context-free languages L 1 and L 2 it is undecidable whether

(i) L 1 is SDI-free with respect to L 2 , (ii) L 1 is SDI-independent with respect to L 2 .
For dealing with language equations we express the site-directed insertion operation as a semantic shuffle on a set of trajectories (SST) due to Domaratzki [START_REF] Domaratzki | Semantic shuffle on and deletion along trajectories[END_REF]. The semantic shuffle extends the (syntactic) shuffle on trajectories originally defined by Mateescu et al. [START_REF] Mateescu | Shuffle on trajectories: Syntactic constraints[END_REF]. We use a simplified definition of SST that does not allow content restriction [START_REF] Domaratzki | Semantic shuffle on and deletion along trajectories[END_REF].

The trajectory alphabet is Γ = {0, 1, σ} and a trajectory is a string over Γ . The semantic shuffle of x, y ∈ Σ * on a trajectory t ∈ Γ * , denoted by x t y, is defined as follows.

If x = y = ε, then x t y = ε if t = ε and is undefined otherwise. If x = ax , a ∈ Σ, y = ε and t = ct , c ∈ Γ , then x t ε = a(x t ε) if c = 0, ∅, otherwise. If x = ε, y = by , b ∈ Σ, and t = ct , c ∈ Γ , then ε t y = b(ε t y ) if c = 1, ∅, otherwise.
In the case where all the strings are nonempty, for x = ax , y = by , a, b ∈ Σ, and t = ct , c ∈ Γ , we define

x t y =          a(x t y) if c = 0, b(x t y ) if c = 1, a(x t y ) if a = b and c = σ, ∅, otherwise.
Intuitively, the trajectory t is a sequence of instructions that guide the shuffle of strings x and y: 0 selects the next symbol of x, 1 the next symbol of y (these are as in the original definition of syntactic shuffle [START_REF] Mateescu | Shuffle on trajectories: Syntactic constraints[END_REF]) and σ represents synchronized insertion where the next symbols of the argument strings must coincide. For x, y ∈ Σ * and t ∈ Γ * , x t y either consists of a unique string or is undefined. For T ⊆ Γ * , x T y = t∈T x t y and the operation is extended in the natural way for languages over Σ.

Directly from the definition it follows that the SDI and alphabetic SDI operations can be represented as semantic shuffle on a regular set of trajectories. Proposition 3. Let T sdi = 0 * σ + 1 * σ + 0 * and T a-sdi = 0 * σ1 * σ0 * . Then, for any languages L 1 and L 2 ,

L 1 sdi ← L 2 = L 1 T sdi L 2 , and, L 1 a-sdi ← L 2 = L 1 T a-sdi L 2 .
Now using the strong decidability results of Domaratzki [START_REF] Domaratzki | Semantic shuffle on and deletion along trajectories[END_REF] we can effectively decide linear language equations involving site-directed insertion where the constants are regular languages. The representation of SDI using SST guarantees the existence of regularity preserving left-and right-inverse of the operation. This makes it possible to use the results of Kari [START_REF] Kari | On language equations with invertible operations[END_REF] to decide existence of solutions to linear equations where the constants are regular languages. The maximal solutions to the equations are represented using semantic deletion along trajectories [START_REF] Domaratzki | Semantic shuffle on and deletion along trajectories[END_REF]. For the deletion operation we consider a trajectory alphabet ∆ = {i, d, σ}. Intuitively, a trajectory t ∈ ∆ * guides the deletion of a string y from x as follows: a symbol i (insertion) indicates that we output the next symbol of x, a symbol d (deletion) indicates that the next symbol of y must match the next symbol of x and nothing is produced in the output and a symbol σ (synchronization) indicates that the next symbols of x and y must match and this symbol is placed in the output. The result of deleting y from x along trajectory t is denoted x ; t y and the operation is extended in the natural way for sets of trajectories and for languages.

We can express the left-and right-inverse (as defined in [START_REF] Kari | On language equations with invertible operations[END_REF][START_REF] Domaratzki | Semantic shuffle on and deletion along trajectories[END_REF]) of SDI using semantic deletion along trajectories, and these relations are used to express solutions for linear language equations. Given a binary operation 3 on strings, let 3 rev be the operation defined by x3 rev y = y3x for all x, y ∈ Σ * . Using Theorems 6.4 and 6.5 of [START_REF] Domaratzki | Semantic shuffle on and deletion along trajectories[END_REF] we obtain: Theorem 2. Let L, R ⊆ Σ * be regular languages. Then for each of the following equations it is decidable whether a solution exists: (a)

X sdi ← L = R, (b) L sdi ← X = R, (c) X a-sdi ← L = R, (d) L a-sdi ← X = R. Define T 1 = i * σ + d * σ + i * , T a 1 = i * σd * σi * , T 2 = d * σ + i * σ + d * ,
S b = L(; T2 ) rev R, (c) S c = R ; T a 1 L, (d) S d = L(; T a 2 ) rev R.
The above result does not give a polynomial time decision algorithm, even in the case where the languages L and R are given by DFA's. Semantic shuffle on and deletion along regular sets of trajectories preserve regularity but the operations are inherently nondeterministic and complementation blows up the size of an NFA. Note that deleting an individual string y from a string x along trajectory t is deterministic, but the automaton construction for the result of the operation on two DFA languages is nondeterministic. An explicit construction of an NFA for the syntactic shuffle of two regular languages is given in [START_REF] Mateescu | Shuffle on trajectories: Syntactic constraints[END_REF].

The known trajectory based methods for two variable equations [START_REF] Domaratzki | Semantic shuffle on and deletion along trajectories[END_REF] do not allow the trajectories to use the synchronizing symbol σ that is needed to represent the overlap of SDI. However, if we are just interested to know whether a solution exists (as opposed to finding maximal solutions), it is easy to verify that an equation X 1 sdi ← X 2 = R has a solution if and only if all strings of R have length at least two.

Maximal and minimal site-directed insertion

Holzer et al. [START_REF] Holzer | The chop of languages[END_REF] define two deterministic variants of the chop operation. The max-chop (respectively, min-chop) of strings x and y chooses the non-empty suffix of x overlapping with y to be as long (respectively, as short) as possible.

By a maximal site-directed insertion of string y into a string x we mean, roughly speaking, an insertion where neither the overlapping prefix nor the overlapping suffix can be properly extended. The operation is not deterministic because y could be inserted in different positions in x. At a specific position in x, a string y can be maximally (respectively, minimally) inserted in at most one way.

Formally, the maximal site-directed insertion (max-SDI) of a string y into string x is defined as follows:

x max-sdi ← y = { x 1 uzvx 2 | x = x 1 uvx 2 , y = uzv, u = , v = ,
and there exist no suffix x 1 of x 1 and prefix x 2 of x 2 such that x 1 x 2 = and y = x 1 uz vx 2 , z ∈ Σ * } Equivalently the maximal SDI of x and y is

x max-sdi ← y = { x 1 uzvx 2 | x = x 1 uvx 2 , y = uzv, u = = v, no suffix of x 1 u
of length greater than |u| is a prefix of uz and no prefix of vx 2 of length greater than |v| is a suffix of zv }. For example also the string abacbabab is obtained by site-directed inserting y = acbab into x = ababab. In this operation the prefix a of y is matched with the 3rd symbol of x and the suffix b of y is matched with the 4th symbol of x. However, this operation does not satisfy the maximality condition because after the 3rd symbol of x we can match a longer suffix of y.

The minimal site-directed insertion (min-SDI) operation is defined as follows:

x min-sdi ← y = { x 1 uzvx 2 | x = x 1 uvx 2 , y = uzv, u = , v = ,
no proper nonempty suffix of u is a prefix of u, and no proper nonempty prefix of v is a suffix of v }.

Note that in the definition of min-SDI, u and v are unbordered words. Figure 1 (b) illustrates the defininition of minimal SDI. The alphabetic SDI can be viewed as an "extreme" case of minimal SDI: if the first and last letter of y coincide with a substring of x of length two, then the alphabetic and minimal site-directed insertion of y in that position coincide.

If x and y are unary strings with |x|, |y| ≥ 2, then x min-sdi ← y is the unary string of length |y| + |x| -2 and the operation is undefined for |x| < 2 or |y| < 2.

Note that while the maximal or minimal SDI is considerably more restricted than the unrestricted SDI operation, if a string y can be site-directed inserted to a string x, it can be also maximally or minimally inserted at the same position. The result of an alphabetic insertion is always a minimal insertion. These observations are formalized in the next lemma.

Lemma 2. Let x, y ∈ Σ * . (i) x max-sdi ← y ⊆ x sdi ← y and x a-sdi ← y ⊆ x min-sdi ← y ⊆ x sdi ← y. (ii) x sdi ← y = ∅ iff x max-sdi ← y = ∅ iff x min-sdi ← y = ∅. (iii) It is possible that x min-sdi ← y = ∅ and x a-sdi ← y = ∅.
Since the max-chop and min-chop operations do not preserve regularity [START_REF] Holzer | The chop of languages[END_REF], it can be expected that the same holds for maximal and minimal SDI. The proof of the following proposition is inspired by Theorem 3 of [START_REF] Holzer | The chop of languages[END_REF].

Proposition 4. The maximal and minimal site-directed insertion do not preserve regularity.

Proof. Let Σ = {a, b, $, %} and choose

L 1 = ba + ba + $, L 2 = ba + ba + %$ We claim that (L 1 max-sdi ← L 2 ) ∩ (ba + ) 3 %$ = {ba m ba n ba k %$ | m = n or k < n, m, n, k ≥ 1}
We denote the right side of the equation by L result which is clearly nonregular. Since the strings of L 2 contain the marker % that does not occur in strings of L 1 , when inserting a string y ∈ L 2 into a string of L 1 the overlapping suffix of y must consist exactly of the last symbol $. Consider x = ba i ba j $ ∈ L 1 and y = ba r ba s %$ ∈ L 2 . In order for the resulting string to have three symbols b, a prefix of ba r must overlap with ba j , that is, j ≤ r. In order for the overlap to be maximal we must have r = i or s < j. These relations guarantee that the unique string in

x max-sdi ← y is in L result .
For the converse inclusion we note that, for m

= n or k < n, ba m ba n ba k %$ ∈ ba m ba n $ max-sdi ← ba n ba k %$.
For non-closure under min-SDI we claim that

(L 1 min-sdi ← L 2 ) ∩ (ba + ) 2 %$ = {ba m ba n %$ | n > m ≥ 1} = def L result .
Consider x = ba i ba j $ ∈ L 1 and y = ba r ba s %$ ∈ L 2 . In order for the result of site-directed insertion of y into x to have two b's, ba i ba j must be a prefix of ba r ba s , that is, i = r and j ≤ s. For the site-directed insertion to be minimal, no proper non-empty prefix of ba i ba j can be its suffix, that is i < j. These relations guarantee that the minimal SDI of x and y is in L result .

Conversely, for n > m, ba m ba n %$ ∈ ba m ba n $ min-sdi ← ba m ba n %$. In fact, extending the max-chop and min-chop constructions from Theorem 3 of [START_REF] Holzer | The chop of languages[END_REF] it would be possible to show that there exist regular languages L 1 and L 2

such that L 1 max-sdi ← L 2 (or L 1 min-sdi ← L 2 ) is not context-free.
The maximal or minimal site-directed insertion of a finite language into a regular language (and vice versa) is regular.

Proposition 5. Let R be a regular language and L a finite language. Then the languages R

max-sdi ← L, R min-sdi ← L, L max-sdi ← R, and L min-sdi ← R are regular.
Proof. We show that R max-sdi ← L is regular. The other cases are very similar. Since

R max-sdi ← L = y∈L R max-sdi ← y
and regular languages are closed under finite union, it is sufficient to consider the case where L consists of one string y.

Let A be an NFA for R and y ∈ Σ * . We outline how an NFA B can recognize L(A) max-sdi ← y. On an input w, B nondeterministically guesses a decomposition w = x 1 y 1 y 2 y 3 x 2 where x 1 y 1 y 3 x 2 ∈ L(A), y 1 y 2 y 3 = y and y 1 , y 3 = ε. When reading the prefix x 1 y 1 , B simulates a computation of A ending in a state q, then skips the substring y 2 , and continues simulation of A from state q on the suffix y 3 x 2 .

The above checks that the input is in L(A) sdi ← y and, additionally, B needs to verify that the insertion is maximal. This is possible because B is looking for maximal insertions of the one fixed string y.

(i) When processing the prefix x 1 , the state of B remembers the last |y| -1 symbols scanned. When the computation nondeterministically guesses the substrings y 1 , y 2 , y 3 , it can then check that for no nonempty suffix x 1 of x 1 , x 1 y 1 is a prefix of y 1 y 2 . If this condition does not hold, the corresponding transition is undefined.

(ii) Similarly, when processing the (nondeterministically selected) suffix x 2 of the input, B remembers the first |y| -1 symbols and is able to check that for no nonempty prefix x 2 of x 2 , y 3 x 2 is a suffix of y 2 y 3 .

If the checks in both (i) and (ii) are successful and at the end the simulation of A ends with a final state, this means that the decomposition x 1 y 1 y 2 y 3 x 2 gives a maximal site-directed insertion of y into a string of L(A).

Decision problems for maximal/minimal SDI

From Proposition 4 we know that the maximal or minimal SDI of regular languages need not be regular. However, for regular languages L As we have seen, the maximal and minimal SDI operations are often more difficult to handle than the unrestricted SDI. Using Lemma 2 (ii) we note that deciding maximal (or minimal) SDI-freeness is the same as deciding SDI-freeness and by Theorem 1 we have: Corollary 1. For NFAs A and B we can decide in polynomial time whether or not L(A) is maximal SDI-free (respectively, minimal SDI-free) with respect to L(B).

Also, deciding whether regular languages are max-SDI (or min-SDI) independent can be done in polynomial time.

Theorem 3. For NFAs A and B, we can decide in polynomial time whether or not L(A) is maximal SDI-independent (respectively, minimal SDI-independent) with respect to L(B).

Proof. Let Σ be the underlying alphabet of A and B. We verify that L(A)

←

x 1 y 1 y 2 y 3 x 2 , where the latter insertion uses the outfix (x 1 y 1 , y 3 x 2 ) as insertion guide. The insertion is maximal because the outfix cannot be expanded. In the same way we see that L(A) min-sdi ← Σ + = L(A) sdi ← Σ + . Now the claim follows by Theorem 1. Since the max-SDI and min-SDI operations do not preserve regularity there is no straightforward algorithm to decide whether a regular language is closed under maximal SDI or under minimal SDI. We conjecture that the problem is decidable.

Problem 1. Is there an algorithm that for a given regular language L decides whether or not

L max-sdi ← L ⊆ L (respectively, L min-sdi ← L ⊆ L)?
Using Proposition 5 we can decide closure of a regular language under max/min-SDI with a finite language.

Corollary 2. Given a regular language R and a finite language F we can decide whether or not Recall that the NFA stores in the state a sequence of symbols having length of the inserted string. Strictly speaking, the proof of Proposition 5 assumes that F consists of a single string, but a similar construction works for a finite language. When c F is a constant, the size of B is polynomial in m and we can decide in polynomial time whether or not L(B) ∩ L(A) = ∅.

(i) R max-sdi ← F ⊆ R, (ii) R min-sdi ← F ⊆ R. If R is
The max-SDI and min-SDI operations do not preserve regularity and, consequently, they cannot be represented using semantic shuffle on trajectories. Thus, the tools developed in Section 6 of [START_REF] Domaratzki | Semantic shuffle on and deletion along trajectories[END_REF] to deal with language equations are not available and it remains open whether we can solve language equations involving max-SDI or min-SDI. 5 Nondeterministic state complexity

The site-directed insertion (SDI) operation preserves regularity [START_REF] Cho | Outfix-guided insertion[END_REF] (Proposition 1 above) and the construction can be modified to show that also alphabetic SDI preserves regularity. To conclude, we consider the nondeterministic state complexity of these operations. The upper bound is the same as the bound for the nondeterministic state complexity of ordinary insertion [START_REF] Han | State complexity of insertion[END_REF], however, the construction used for Lemma 4 is not the same. Using Lemma 1 (the fooling set lemma [START_REF] Birget | Intersection and union of regular languages and state complexity[END_REF]) we can establish a matching lower bound. Lemma 5. For m, n ∈ N, there exist regular languages L 1 and L 2 over a binary alphabet having NFAs with m and n states, respectively, such that any NFA for L 1 a-sdi ← L 2 needs at least mn + 2m states.

The above lemmas establish the precise nondeterministic state complexity of alphabetic SDI. Likely the bound cannot be improved but we do not have a proof for the lower bound.

Problem 3. What is the nondeterministic state complexity of site-directed insertion?

and T a 2 =

 2 d * σi * σd * . If a solution exists, a superset of all solutions is, respectively, for the different cases: (a) S a = R ; T1 L, (b)

Fig. 1 .Example 1 .

 11 Fig.1. Insertion of y into x depicted at top left is not maximal when x and y have decompositions as depicted at bottom left.

  1 and L 2 we can decide membership in L 1 max-sdi ← L 2 (or L 1 min-sdi ← L 2 ) in polynomial time. Lemma 3. For DFAs A and B and w ∈ Σ * we can decide in time O(n 6 ) whether w ∈ L(A) max-sdi ← L(B), or whether w ∈ L(A) min-sdi ← L(B).

Σ

  + = L(A) sdi ← Σ + . The inclusion from left to right holds by Lemma 2 (i). Conversely, suppose w ∈ L(A) sdi ← y 1 y 2 y 3 , where w = x 1 y 1 y 2 y 3 x 2 , y 1 , y 3 = ε, x 1 y 1 y 3 x 2 ∈ L(A). Then w ∈ L(A) max-sdi

  specified by a DFA and the length of the longest string in F is bounded by a constant, the algorithm works in polynomial time. Proof. By Proposition 5 the languages R max = R max-sdi ← F and R min = R min-sdi ← F are effectively regular. Suppose R = L(A) where A is a DFA with m states and underlying alphabet Σ and the length of the longest string in F is c F . The NFA B constructed in the proof of Proposition 5 for R max (or R min ) has O(m • |Σ| c F ) states.

Problem 2 .

 2 Let L and R be regular languages. Is it decidable whether the equationX max-sdi ← L = R (respectively, L max-sdi ← X = R, X min-sdi ← L = R, L min-sdi ← X = R) has a solution?

Lemma 4 .

 4 For NFAs M and N having, respectively, m and n states, the language L(M ) a-sdi ← L(N ) can be recognized by an NFA with mn + 2m states.

Corollary 3 .

 3 The worst case nondeterministic state complexity of the alphabetic site-directed insertion of an n-state NFA language into an m-state NFA language is mn+2m. The lower bound can be reached by languages over a binary alphabet.It is less obvious what is the precise nondeterministic state complexity of the general SDI. IfA has m states and B has n states, Proposition 1 gives an upper bound 3mn + 2m for the nondeterministic state complexity of L(A) sdi ← L(B).

Cho and Han were supported by the Basic Science Research Program through NRF (2015R1D1A1A01060097) and the International Research & Development Program of NRF (2017K1A3A1A12024971). Salomaa and Smith were supported by Natural Sciences and Engineering Research Council of Canada Grant OGP0147224.


David Gueorguiev
email: dgueorguiev@is.mpg.de

Anis Kaci
email: anis.kaci@etudiant.univ-lille1.fr

Michel Amberg
email: michel.amberg@univ-lille1.fr

Frédéric Giraud
email: frederic.giraud@polytech-lille.fr

Betty Lemaire-Semail

Travelling Ultrasonic Wave Enhances Keyclick Sensation

Keywords: haptic display, tactile perception, ultrasonic vibration, travelling wave, keyclick, button click

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

Haptic interaction is essential to our capacity to use portable interactive screens without physical keyboard [START_REF] Buxton | Issues and techniques in touch-sensitive tablet input[END_REF]. In the last decades, tactile displays have greatly improved with the development of naive on-screen physics that are intuitive to the user [START_REF] Wilson | Bringing physics to the surface[END_REF] and rapid progress in the ability to deliver force-based tactile feedback [START_REF] Vezzoli | Texture rendering strategies with a high fidelity-capacitive visual-haptic friction control device[END_REF][START_REF] Meyer | Tactile paintbrush: A procedural method for generating spatial haptic texture[END_REF]. However, it is still difficult to type a large text on the keyboard of a tablet. The difficulty of this task partly comes from the ergonomics of the screen but also from the lack of tactile feedback that current tactile displays provide to us while typing. At best, they deliver timely vibrations that replace the Fig. 1: a) The apparatus used for the generation of the keyclick. The actuation was performed on an ultrasonic motor. b) The ultrasonic travelling wave was generated by the superposition of two stationary waves, which are shifted by either -90 • , 0 • or +90 • . c) The travelling wave generates an additional tangential force F t+ on the fingertip compared to the stationary ultrasonic vibration. contact mechanics occurring during the push of a classical keyboard button. The absent or impaired sensation compared to an old-fashioned physical keyboard is an important shortcoming of the current smartphones and tablets and one of the major challenges ahead of the realistic rendering of haptic feedback. In addition to the poor user experience, unnatural feedback also impairs the user's typing performance on the device. Several vibration-based technologies for creating a button-click have been suggested. 250 Hz vibration with up and down ramps have proven effective to improve finger-based text entry [START_REF] Hoggan | Investigating the effectiveness of tactile feedback for mobile touchscreens[END_REF]. It was also suggested that a higher fidelity of the vibrotactile signal hence a more pleasant click sensation could be achieved by using piezo actuators instead of conventional vibrating motors [START_REF] Koskinen | Feel-good touch: Finding the most pleasant tactile feedback for a mobile touch screen button[END_REF]. A recent study showed that, in addition to the improved performance, the feeling of an haptic click can be recreated by using three repeated cycles of a 250 Hz sinusoidal signal generated by piezo actuators [START_REF] Chen | Design and evaluation of identifiable key-click signals for mobile devices[END_REF][START_REF] Ma | Haptic keyclick feedback improves typing speed and reduces typing errors on a flat keyboard[END_REF].

However, vibrotactile feedback is inherently different to the force feedback generated by the keys of physical keyboards, which apply contact forces to the fingertip [START_REF] Weir | The haptic profile: capturing the feel of switches[END_REF]. It has been suggested that a button click sensation can be achieved by modulating the friction between a finger and an ultrasonically vibrating surface at the moment of contact in order to recreate the rapid change in force induced by the buckling of a mechanical push button [START_REF] Tashiro | Realization of button click feeling by use of ultrasonic vibration and force feedback[END_REF]. Indeed, the human perception of transient frictional cues is particularly accurate at the onset of the tactile interaction with a surface and [START_REF] Gueorguiev | Touch uses frictional cues to discriminate flat materials[END_REF] and event-base feedback is known to create a more realistic haptic sensation [START_REF] Kuchenbecker | Improving contact realism through event-based haptic feedback[END_REF] compared to position-based feedback. Therefore, frictional modulations driven by the user's behavior are very salient for the sense of touch and small differences in their timing or sharpness can have a large perceptual impact [START_REF] Gueorguiev | Feeling multiple edges: The tactile perception of short ultrasonic square reductions of the finger-surface friction[END_REF].

Earlier work

A recent study has built on these principles to show that a realistic keyclick sensation can be generated by an event-based stepwise modulations of the ultrasonic vibration [START_REF] Monnoyer | Ultrasonic friction modulation while pressing induces a tactile feedback[END_REF]. Two types of stimulation were tried: a step of falling friction and a step of rising friction occurring at a predefined normal force level. Users detected more easily the falling friction than the rising friction and reported to feel it as a convincing keyclick sensation. The proposed method relies on sudden changes in the impedance of the finger [START_REF] Monnoyer | Optimal skin impedance promotes perception of ultrasonic switches[END_REF], which are provoked by the influence of the ultrasonic lubrication [START_REF] Wiertlewski | Partial squeeze film levitation modulates fingertip friction[END_REF][START_REF] Vezzoli | Friction reduction through ultrasonic vibration part 1: Modelling intermittent contact[END_REF] on the compression of the fingerpad. Lateral motion of the finger is generally necessary to the occurrence of friction modulation by ultrasonic lubrication. In its absence, the subtle mechanics generating the keyclick sensation require a high amplitude of ultrasonic vibration to be perceivable and the threshold for perceiving the clickbutton is several times higher than the threshold for perceiving frictional steps during dynamic tactile exploration [START_REF] Gueorguiev | The tactile perception of transient changes in friction[END_REF]. The quality of the sensation was also found to be strongly influenced by the natural impedance of the fingertip with an impaired sensation for extreme impedances.

It is also possible to enhance the modulation of friction hence the tactile sensation generated by ultrasonic actuation on the fingertip through the implementation of an ultrasonic travelling wave instead of a stationary wave. When vibrating, the particles of a surface on which a travelling wave is propagating undergo an elliptic motion. For specific operating conditions, they can help to propel the finger if they move in the same direction as the finger pulp when they come in contact with it. This effect additionally decreases the equivalent friction coefficient compared with a pure stationary wave [START_REF] Ghenna | Enhancing variable friction tactile display using an ultrasonic travelling wave[END_REF]. Conversely, a travelling wave decreases the the friction reduction when the direction is reversed.

Progressive ultrasonic waves can be wisely used to generate a keyclick sensation during pressing on an actuated surface. Our method consists in a stepwise switching on of a travelling ultrasonic wave at a predefined normal force threshold and a reversal of its direction when a second predefined normal force threshold is reached. This method exploits the frictional force exerted by the ultrasonic travelling wave to deliver a click sensation to the user during the pressing of the surface. This study aims to compare both methods for generating a keyclick sensation in terms of psychophysical threshold, quality of the sensation and pressing behavior of the participants. In a first experiment, we let participants free to explore the sensation by not restricting the number of pressings by trial in order The keyclick actuated by the stationary wave was generated by a stepwise switch on of the ultrasonic vibration at a predefined threshold value of the normal force c) For the travelling wave, the stepwise increase in amplitude at f th1 is followed by a second normal force threshold f th2 at which the direction of the ultrasonic wave is reversed.

to see if they would choose different exploratory strategies for the two methods.

In a second experiment, we increased the comparability between the methods by estimating the perceptual threshold when participants were constrained to press only once by trial on the surface.

3 Materials and Methods

Participants

Data were collected from 20 healthy volunteers aged between 22 and 62 (5 females). 10 participated in experiment 1 and 10 additional participants were recruited for experiment 2. Participants were wearing noise-cancelling headphones in order to prevent potential interference from auditory cues. All participants gave written informed consent. The investigation conformed to the principles of the Declaration of Helsinki and experiments were performed in accordance with relevant guidelines and regulations.

Experimental set-up

For this experiment, the stator of a USR60 ultrasonic motor (Shinsei Corporation, Japan) was used (Fig. 1a). It is constituted by a bronze disk on which a ring of 16 piezoelectric actuators is glued. Half of these actuators are arranged so that they can excite the 9 th bending mode denoted by cos hereafter, which is characterized by a resonance frequency of 40kHz, and a wavelength λ = 21mm. The other actuators are arranged with a spatial shift of λ/4 on the ring, thus exciting a doublet of the cos mode, which is denoted sin. The excitation of modes cos and sin in quadrature, i.e. with a temporal phase shift of π/2 (Fig. 1b) produces a travelling wave (Fig. 1c). Changing the sign of the phase shift will invert the direction of the wave; cancelling the phase shift produces a stationary wave. A laser doppler vibrometer (OFV 505, Polytec, Germany) was used to localize the antinodes of the stationary wave, and was marked as a target for the pressing.

The normal force during pressing on the actuated surface was measured by a one-axis force sensor, located below the pressing area, with a resolution of 0.01 N. The acquisition of the force values was performed by a in-house acquisition board at a 42 Hz sampling rate. In addition, the laser vibrometer was used to compute the values in µm corresponding to the arbitrary units (from 1 to 15) controlling the intensity of the ultrasonic vibration (Fig. 2a).

The keyclick rendering when using a stationary wave was performed as in [START_REF] Monnoyer | Ultrasonic friction modulation while pressing induces a tactile feedback[END_REF] by a step increase of the amplitude of vibration when a predefined threshold of the normal force was reached (Fig. 2b). For the travelling wave method, two normal force thresholds f th1 and f th2 were predefined (Fig. 2c). At f th1 , the travelling wave was switched on by a step increase in the amplitude of vibration. Above the normal force threshold f th2 ,which was set 0.33 N higher than f th1 , the direction of the travelling wave was reversed in order to enhance the tactile feedback on the fingertip.

Experimental procedure

In both experiments, participants were asked to press on the actuated surface with their index finger. The target location was chosen on a vibration antinode and labelled with a color marker in order to ensure that participants experienced consistent ultrasonic vibration across trials. The estimation of the psychophysical threshold was performed with a one-up one-down staircase procedure, which targeted the intensity at which a keyclick sensation was felt 50% of the time, a procedure also referred as Bekesy tracking method [START_REF] Békésy | Experiments in hearing[END_REF]. At each trial, after pressing on the actuated surface, the participants had to report if they felt a keyclick sensation or not. We chose a non-forced choice procedure despite its proneness for criterion bias for two reasons: 1/ we wanted the participants to focus on the keyclick sensation rather than on the perception of the variation of the finger-surface friction. 2/ for a given participant, the psychophysical estimation for the progressive and stationary wave are likely to be identically influenced by its criterion bias. Thus, the influence of the criterion on the comparison is lower than if the aim of the study was to estimate the absolute psychophysical threshold. Before each block, participants were allowed to familiarize themselves with the haptic feedback by testing several clicks at maximum intensity.

To avoid potential biases due to prediction of the next stimulation intensity by participants, three staircases with different force thresholds were interlaced (0.11, 0.44 and 0.77N). For each trial, the probability to be presented with a trial from a given staircase was 1/3 (Fig. 3a). The experiment ended when 5 turnovers or 30 trials were achieved for all three staircases. For each staircase, the perceptual threshold was then computed as the mean of the last 3 turnovers. One participant in experiment 2 made less than three turnovers in one of the conditions and we had to discard its data. The experiment was performed two times: one with the stationary wave method and another time with the progressive wave method. The order of the two conditions was pseudo-randomized across participants to avoid learning curve effects.

Results

Multiple clicks

For all tested actuation criteria (0.11N, 0.44N and 0.77N), we computed the 50% detection thresholds for both methods to generate a keyclick sensation (Fig 3 .b). For the stationary ultrasonic vibration, the median value of the individual thresholds for 0.11N, 0.44N and 0.77N were respectively 1.56µm (IQR = 1.98-1.30), 1.65µm (IQR = 2.11-1.21) and 1.60µm (IQR = 2.00-1.39). For the travelling ultrasonic vibration, the median values of the individual thresholds for 0.11N, 0.44N and 0.77N were respectively 1.16µm (IQR = 1.61-0.76), 1.24µm (IQR = 1.54-0.94) and 1.34µm (IQR = 1.62-1.06). The results showed a significantly lower threshold for the rendering technique based on travelling ultrasonic vibration (Friedman test: χ2 = 16.09, p = 0.0066). A further post-hoc analysis with Wilcoxon matched-pairs signed rank test showed that the difference between the two techniques was statistically significant for the 0.11N and 0.77N thresholds (respectively n = 10, W = -44, p = 0.0215 and n = 10, W = -49, p = 0.001) while a trend was observed for the 0.44N threshold (n = 10, W = -37, p = 0.064). Overall, rendering with travelling ultrasonic vibration decreased the detection threshold by around 25-30% compared to actuation with a stationary ultrasonic wave.

In the first experiment, participants were allowed to press as many times as they wanted on the actuated surface for a given trial. For each participant, the average number of presses across the experiment did not differ significantly between the two actuation methods and the three possible force thresholds (nonparametric Friedman test: χ2 = 7.77, p = 0.1693) (Fig. 4a). However, large numbers of consecutive surface presses (clicks) were mostly found close to the psychophysical threshold. Thus, we computed the average number of clicks across participants for each trial number and we compared both techniques for the first 52 trials (Fig. 4b), which was the number of trials available for all participants. The results showed a significantly higher average number of clicks for the actuation by a stationary wave (Wilcoxon matched-pairs signed rank statistical: N = 52, W = 712, p = 0.0006). Similarly, we computed the peak force during pressing for the first 52 trials and compared it for both techniques (Fig. 4c). The peak force during pressing was found significantly higher for the actuation with a stationary wave (Wilcoxon matched-pairs signed rank statistical: N = 52, W = 1022, p < 0.0001). Overall, these results show that, in the case of the stationary wave, the participants tended to press more times and harder when the actuation intensity was close to their psychophysical threshold.

One click

In the second experiment, participants were instructed to press only once per trial on the actuated surface. For the stationary ultrasonic vibration, the median value of the individual thresholds for 0.11N, 0.44N and 0.77N were found to be respectively 1.86µm (IQR = 2.85-1.04), 1.88µm (IQR = 2.73-1.26) and 2.27µm (IQR = 2.85-1.75). For the progressive ultrasonic vibration, the medians of the individual thresholds for 0.11N, 0.44N and 0.77N were respectively 1.49µm (IQR = 1.75-0.51), 1.54µm (IQR = 1.73-0.37) and 1.63µm (IQR =1.82-0.62) (Fig. 4d). The results showed a significantly lower threshold for the rendering technique based on travelling ultrasonic vibration (Friedman test: χ2 = 25.14, p = 0.0001). A further post-hoc analysis with Wilcoxon matched-pairs signed rank test showed that differences were statistically significant for all threshold conditions. (respectively n = 10, W = -42, p = 0.011; n = 10, W = -39, p = 0.019 and n = 10, W = -45, p = 0.004 for 0.11N, 0.44N and 0.77N). Thus, rendering with travelling ultrasonic vibration when only one click was allowed decreased the median detection threshold compared to stationary vibration by similar percentage to the one observed when multiple clicks were possible.

We further compared the psychophysical thresholds of the second experiment to those observed in the first one (Fig. 5a) and although they showed a slight increase, the difference was not significant (Mann-Whitney test: U = 300.5, p = 0.096 for the stationary actuation and U = 373, p = 0.614 for the actuation by a travelling wave). Thus, pressing numerous times did not significantly influence the keyclick perception threshold of the users.

As in experiment 1, we measured the peak normal force that the participant exerted and we averaged its value across all participants for each trial number of the staircase. In the second experiment, 47 trials were available for all participants and we compared the peak forces between the two actuation techniques (Fig. 5b). The results showed a significantly higher average peak force during pressing for the actuation by a stationary wave (Wilcoxon matched-pairs signed rank statistical test: N = 43, W = 946, p < 0.0001). In this experiment, even the early trials with a high amplitude of vibration showed a large difference between both techniques.

In both experiments, we asked participants which technique rendered the more realistic keyclick sensation. Seven out of ten participants preferred actuation with the travelling wave in experiment 1 and five out of ten in experiment 2, suggesting that the travelling wave generates a quality of the keyclick sensation similar to the stationary actuation.

Discussion

Our study shows that the actuation of an ultrasonic keyclick by a travelling wave decreases the amount of vibration amplitude which is necessary to render the click. We also found that the users are less prone to use excessive normal force or click multiple times compared to rendering with a stationary wave. Interestingly, pressing one or multiple times did not significantly influence the psychophysical threshold. This suggests that for a given set of parameters, the keyclick induces a consistent sensation and that the temptation for repeated pressing is mainly done to confirm the sensation of the first click. The difference between both techniques in the pressing normal force was larger when participants were constrained to one click. This suggests that participants felt that they are maximizing their perception of the stationary ultrasonic keyclick by pressing harder hence inducing a larger compression of their fingertip. Although the reflex to push harder when the stimulus becomes subtle was still present, it was less pronounced for the travelling wave, probably because they felt that this type of stimulation mostly induces a lateral force on the fingertip. We explain these results by the capacity of the travelling wave to produce more tangential force contrast than a stationary wave, whose feedback intensity depends on the lateral component of the fingerpad's compression. This larger contrast stems of the wave's constant pushing force F t+ that exists independently of lateral motion of the finger. The strong lateral force component of the actuation by a travelling wave raises the question of the perceived quality of the keyclick sensation since the force exerted by a physical keyboard is purely normal. To that end, we compared the subjective perception of keyclick rendering generated by the travelling wave to the one generated by the stationary wave by asking participants to report their preferred rendering. The reports did not show an overwhelming preference for one of the techniques confirming that the travelling wave method generates a genuine keyclick sensation on the fingertip.

Conclusion

Overall, actuation by travelling ultrasonic wave is a promising technique to create tactile feedback on a finger that is not moving laterally. For the keyclick, this method decreases the threshold for perceiving the click by 25-30% compared to actuation with a stationary ultrasonic wave and the normal force exerted by the participants is also significantly reduced compared to the stationary condition.

In future applications, one can imagine to vary the speed and direction of a travelling wave at a high frequency to create different types of signal on the unmoving finger such as meaningful interactive cues, force-based vibrations or cues for localizing a screen icon. These applications could be complementary to the textures and renderings already available through stationary ultrasonic friction modulation.

Fig. 2 :

 2 Fig.2:a) The correspondance between the arbitrary intensity values and the amplitude of ultrasonic vibration. b) The keyclick actuated by the stationary wave was generated by a stepwise switch on of the ultrasonic vibration at a predefined threshold value of the normal force c) For the travelling wave, the stepwise increase in amplitude at f th1 is followed by a second normal force threshold f th2 at which the direction of the ultrasonic wave is reversed.

Fig. 3 :

 3 Fig.3: a) Typical example of three interlaced psychophysical staircases, which target the 50% perceptual threshold by a one-up one-down paradigm. At each trial, the implemented staircase is chosen at random with a probability of 1/3. b) In experiment 1 (multiple clicks), the 50% perceptual threshold was computed for both actuation techniques. The error bars, the whisker boxes and the horizontal bars show respectively the min. and max. values, their interquartile range and the median value.

  Fig. 4: a) The average number of key presses (clicks) per condition for all six conditions. The boxplots and error bars show respectively the median values and the interquartile ranges. b) Scatter plot of the average number of clicks for a given trial number. c) Scatter plot of the average peak normal force during clicking for a given trial number. d) In experiment 2 (one click), the 50% perceptual threshold was computed for both actuation techniques. The error bars, the whisker boxes and the horizontal bars respectively show the min. and max. values, their interquartile range and the median value.

Fig. 5 :

 5 Fig. 5: a) Comparison of the perceptual thresholds between the multiple clicks and one click conditions for both actuation techniques. The boxplots and error bars show respectively the median values and the interquartile ranges. b) Scatter plot of the average peak normal force during pressing for a given trial number.

Acknowledgment The authors would like to thank the CNRS/IRCICA -USR 3380 research center, which hosted the research. This work was funded by the MATRICE project (ERDF / Région Nord-Pas-de-Calais-Picardie, France).


Patrick Chaquin
email: chaquin@lct.jussieu.fr

Franck Fuster

François Volatron

Bonding/antibonding Character of "lone Pair" Molecular Orbitals from their Energy Derivatives; Consequences for experimental Data

The derivative of molecular orbitals (MO) energies with respect to a bond length (dynamic orbital force, DOF) is used to estimate the bonding/antibonding character of valence MOs along this bond, with a focus on lone pair MOs, in a series of small molecules: AH (A = F, Cl, Br), AH2 (A = O, S, Se) AX3 (A = N, P, As; X = H, F) and H2CO. The HOMO DOF agrees with the calculated variation of bond length and force constant in the corresponding ground state cation, and of bond length variation by protonation. These results also agree with available experimental data. It is worthy to note that the p-type HOMOs in AH and AH2 are found bonding. The lone pair MO is bonding in NH3, while it is antibonding in PH3, AsH3, and AF3.

Introduction How to define the bonding/antibonding character of a MO ?

The bonding/antibonding character can be based on essentially two criteria, energy or force, with different possible definitions on these criteria.

The IUPAC Gold Book 1 prefers the energy point of view, a bonding MO being characterized by "an increase in the total bonding". This generally corresponds also to a MO energy lower than the mean energy of the AOs constituting this MO. These definitions involve the whole molecule. Nevertheless, for the chemist, it is important to characterize local MO properties, i.e. their bonding/antibonding character along a bond, or more generally with respect to geometrical parameters. From this point of view one can consider that a MO is bonding along a given bond if its occupancy increases the bond dissociation energy.

Other definitions are based on force concepts. A MO will be said bonding if its electrons exert an attractive force on the nuclei of concern. For this purpose, a useful guideline is provided by the "Berlin function" f(x, y, z) which performs a partition of the space into bonding and antibonding areas. [START_REF] Berlin | [END_REF] With the notations of Scheme 1, for a diatomic molecule AB, the forces FeA and FeB exerted by an electron density  on nuclei A and B are (Eq. 1) : The bonding/antibonding zones are thus characterized by a positive/negative value of the function f. They are separated by a non-bonding surface given in Fig. 1 for a symmetrical A2 molecules and the unsymmetrical HF one. On this basis, the total electron density is decomposed into MO densities and thus into additive orbital forces which quantify their bonding character. 3,4,5 Another concept of "orbital forces" was proposed by Tal and Katriel 6 . It is built up from the MO energy derivatives with respect to nuclear coordinates. According to the Koopmans theorem 7 , the MO energy can be expressed as Eq. 2:

𝐹 𝑒𝐴 = 𝐹 𝑒𝐵 = -
𝜀 𝑖 = 𝐸 0 -𝐸 𝑖 + (2)
where E° is the Hartree-Fock (H-F) energy of a neutral species and Ei + the energy of the frozen orbital cation resulting from the removal of one electron from the i th spin-orbital i. For a diatomic molecule, the derivative with respect to the internuclear distance R yields (Eq. 3):

𝑑𝜀 𝑖 𝑑𝑅 = 𝑑𝐸 0 𝑑𝑅 - 𝑑𝐸 𝑖 + 𝑑𝑅 (3)
At the equilibrium value Re of the neutral species, dE 0 /dR = 0 and (Eq. 4):

( 𝑑𝜀 𝑖 𝑑𝑅 ) 𝑅=𝑅 𝑒 = -( 𝑑𝐸 𝑖 + 𝑑𝑅 ) 𝑅=𝑅 𝑒 (4)
Eq. 4 means that if 'i = di/dR is positive, the ion energy E + i tends to decrease by lengthening R which characterizes a bonding i MO. These orbital forces are not additive since the total H-F energy is not the sum of occupied MO energies. The term of "dynamical orbital forces" (DOF) was proposed by Averill and Painter for these derivatives because they arise from electron removing (whereas the additive Bader orbital forces appear as "static orbital forces"). 8 These forces are closely related to the Mulliken's criterion of the "bonding power" of an electron. 9 Because canonical MOs are delocalized on the whole molecule, a given MO can be more or less bonding along a given bond and antibonding along another one. These characters can be evaluated by calculating the energy derivative (DOF) with respect to each bond by a finite difference of length. In most of cases, a small variation of one bond length, typically a few 10 -3 Å, has a negligible effect on the other internal coordinates and the resulting DOF can be regarded as a reliable measure of the local (on a given bond) bonding/antibonding character. Because Eq. 4 involves the neglect of MO relaxation and correlation energy, the question arises if the DOF correctly predicts the variation of geometry (and eventually of other properties) following the ionization. At least, one can expect that this quantity reflects a trend which indicates the sign of this variation. As a matter of fact, this assumption has been fully validated in a recent work 10 , in which were reported the DOFs of the valence shell MOs of a panel of 19 diatomic species and of HCN, HNC and CH3CN, focusing our attention on the "lone pairs" MOs of some coordinating species. Very few works have been devoted to the study of canonical MO derivatives 11,12,13 . Tal and Katriel 6 have determined the bonding/antibonding character of the MOs of diatomic homonuclear molecules of the Li-F period. Also, the variation of the DOFs of selected MOs along a reaction coordinate (RC) highlights the nature of the reorganization of these MOs and what stage of the RC it occurs. Moreover, the shape of the DOF curves reveals the existence and precise location of MO avoided crossings. 14 Because Kohn-Sham MO energy also approximate ionisation energy 15 , its derivative was used successfully by several authors as a criterion of bonding character. 8,16,17 In this work, we will focus on the MOs associated to "lone pairs" of small molecules AH (A = F, Cl, Br), AH2 (A = O, S, Se), AH3, AF3 (A = N, P, As) and H2CO. It has been already pointed out that "lone pair" and "non-bonding pair" are not synonymous and, using the localization procedure of Ciolkowski, Chesnut 18 showed that the participation to bonding in some of the preceding molecules is approximately 10-15%. From a qualitative point of view, most of time no "visual" criterion, based on the presence or not of nodal surfaces cutting the bond, can be used to decide whether such MOs are more or less bonding or antibonding. The results will be compared with the variation of observable physical data upon ionization and protonation involving these lone pairs: bond lengths, vibration frequencies and forces constants, computed at a reliable level, and experimental available results.

Calculation details

Calculations of MO energy derivatives (Dynamic Orbital Forces, DOF) have been performed at the HF/6-311G** level, and for sake of comparison, at the B3LYP/6-311G** level, after optimization of geometrical parameters at the same level. The derivatives are computed by finite difference of the length of equivalent bonds by 2-3.10 -3 Å. In a previous work 10 it was stated that that higher level basis sets do not improve significantly the DOF values. The DOFs have been visualized using red (antibonding)/blue (bonding) arrows, whose thickness is proportional to their value in percent of the maximum DOF of the occupied MOs.

The geometry of neutral molecules, positive ions and protonated species were computed at the CCSD(T)/cc-pVTZ level. Vibration frequencies and force constants were computed at the B3LYP/cc-pVTZ level. The GAUSSIAN 09 series of program [START_REF] Gaussian | Gaussian[END_REF] was used.

Results and discussion

Molecules HF, HCl and HBr

The results are gathered in Table 1. The DOFs of the valence shell are visualized in Figure 2 in the case of HF.

Figure 2. DOF of valence shell MOs of HF. Blue/red arrows indicate a bonding/antibonding character, with a thickness proportional to the % of maximum DOF

The Table 1 indicates that 1 and 2 usually referred as  bonding MO and sp lone pair MO respectively are almost equally bonding. The  MOs, usually described as "purely non-bonding" have in fact a marked bonding character. This character is partly due to the presence of empty p MOs of hydrogen in an extended basis set. Nevertheless, even at the STO-3G level, this character remains (0.011 au for HF), though the overlap with the 1s AO of hydrogen is zero. It means that the pure atomic p density on atom A is intrinsically bonding, i.e. exerts an attractive force on the H nucleus. It can be understood qualitatively from Figure 1: the non-bonding surface does not divide equally the 2p density which can be seen slightly more localized in the bonding region.

x  y   The bonding character of  MOs agrees with the calculated bond lengths of neutral and cationic ( 2 ) species: in each case the cation HF + , HCl + , HBr + exhibit a bond lengthening (Rion > 0) with respect to the neutral molecule. As also expected, the ionization results in a decrease of the vibration frequency and force constant. The protonation results also in a bond lengthening, but less marked than in ionization: it can be viewed essentially as a partial electron removing from one  MO because the HAH + angle is close to 90° (111° for A= F, 94° for A = Cl and 92° for A = Br). Experimental results available in the NIST database 20 , reported in Table 1, agree with the bonding character of the HOMO, with an increase of the bond length and a decrease of the vibration frequency, close to calculated values. Also, an increase of the bond length from 0.917 Å to 0.961 Å has been observed in H2F + . [START_REF] Fujimori | [END_REF] We can note that the B3LYP DOF values are in qualitative agreement with H-F ones and close to them for the HOMO, but may differ significantly in some other cases.

Molecules H2O, H2S and H2Se

The results are gathered in Table 2. The DOFs are visualized for H2O in Figure 3. The 1a1 and 1b2 MOs correspond to the  bonds of AH2; they appear with almost equal bonding character. The 2a1 MO is associated to the sp lone pair and is also bonding, but significantly less than the corresponding ones in AH molecules. Like in the AH species, the HOMO is essentially a p AO of atom A, nevertheless slightly bonding in H2O and very slightly bonding in H2S and H2Se. This character agree with the lengthening of the A-H bonds in cations AH2 + ( 2 B1) and protonated AH3 + species as well as a decrease of both (in-phase and out-of-phase) stretching vibrations frequencies and of corresponding force constants. Experimental results for some vibration frequencies agree with the bonding character of the HOMO of these species: the a1 and b2 modes of H2O at respectively 3652 cm -1 and 3757 cm -1 drops to 3213 cm -1 and 3259 cm -1 in H2O + ; 20 similarly the a1 mode of H2S (2615 cm -1 ) and H2Se (2345 cm -1 ) slightly decreases in H2S + (2496 cm -1 ) and H2Se + (2267 cm -1 ) respectively 20 .

2b1 2a 1 1b 2 1a 1
Also, an increase of the bond lengths is observed by protonation of H2O (from 0.958 Å to 0.974 Å) 22 and of H2S (from 1.336 Å to 1.359 Å) 23 .

Molecules NH3, PH3 and AsH3

The results are gathered in Table 3. The MOs 1a1 and e, associated to the  bonds have DOFs of the same order of magnitude. A remarkable point is the fact that the 2a1 MO associated to the lone pair is bonding for NH3 and antibonding for PH3 and AsH3, which is visualized in Figure 4. Available experimental results agree with the bonding character of the HOMO of NH3 whose vibration frequency drops in NH3 + from 3444 cm -1 to 3389 cm -1 (e) and from 3337 cm -1 to 3177 cm -1 (a1). 20 Protonated species NH4 + in Ne matrix absorbs at 3357.5 (e) 24 , very close to NH3 + . Again, B3LYP DOF values agree qualitatively with H-F ones though important differences in absolute values. All computed physical properties are consistent with DOF results : NH3 + and NH4 + exhibit longer bond lengths than NH3, while PH3 + and PH4 + on the one hand, AsH3 + and AsH4 + on the other hand have shorter bonds than PH3 and AsH3 respectively. Similarly, ionisation and protonation result in a decrease of stretching vibration frequencies and force constants for NH3 and an increase of the same quantities for PH3 and AsH3. To understand this difference, the corresponding planar structures were studied: the lone pair 2a1 MO is now pure p, and its DOF becomes positive for all three species as it can be seen in Table 4. The corresponding cations have longer bond lengths. The evolution of the bonding character of the lone pair from NH3 to PH3 may appear paradoxical. As depicted in scheme 2, this lone pair results, by pyramidalization, from a destabilizing mixing with  (out-of-phase) and a stabilizing mixing with * (in-phase). Moreover, it has been shown there is a stronger mixing of p with * in PH3 than in NH3 and though an increase in the in-phase participation of hydrogens 25 . But, at the same time, due an increase of its s character, the "lone pair" density is repelled out of the A-H bond, in the antibonding force region, a phenomenon which appears in the MOs of Fig. 4.

Table 3. Molecules NH3, PH3 and AsH3: DOF (au) of valence MOs with respect to A-H length at the H-F(B3LYP) levels; bond lengths (Å) of neutral R(AH3), cationic R(AH3 + ) and protonated R(AH4

Scheme 2. Interacting MOs in NH3 and PH3 lone-pairs.

A similar evolution could be expected for the sp a1 "lone pair" in the series H2O-H2S-H2Se. Indeed, the DOF drops from 0.098 to 0.040 and 0.032 for this MO which remains nevertheless bonding.

Molecules NF3, PF3 and AsF3

The results are gathered in Table 5. For all three molecules, the a1 MO associated to the lone pair is strongly antibonding. The graphical representation of this MO in NF3 shows that it results from an out-of-phase mixing of the sp hybrid of the central atom with 2p AOs of fluorine atoms, a priori antibonding; but the density in yellow in Fig. 5, can be viewed as a bonding interaction through the N-F bonds, the balance of which is not self-evident. The antibonding nature of a1 is clearer for PF3 and AsF3. Accordingly, we observe a marked shortening in bond lengths of the corresponding cations.

Frequencies and force constants of the e vibration increase in cations. This effect is weak in a1 vibrations of PF3 and AsF3, and even a weak decrease is observed for NF3.

Molecule H2CO

In Table 6, we report the DOFs corresponding to derivatives with respect to the various atom distances: CO and CH bond lengths and HH distance. In the latter case, this distance variation was obtained by variation of HCH angle, i.e. keeping constant both CO and CH lengths. The DOFs of the three highest MOs are graphically presented in Fig. 6. The HOMO 2b2 is antibonding along CO, in agreement with the shortening of this bond and the increase of force constant upon ionization (the lowering of the frequency is due to an increase of reduced mass in the cation).

Regarding the C-H bonds, the variation by ionization of their lengths and of the force constant of the vibration in which they are involved agree with an bonding character of the HOMO along them, predicted by the B3LYP DOF (but not at the H-F level).

The calculated DOF with respect to H…H distance (i.e. with HCH angle) of the HOMO is near zero at the H-F level and positive (0.015) at the B3LYP one. By ionization, we observe an increase of this distance and a decrease of the forces constants in the a1  mode (in-plane deformation), which agrees with the bonding character found at the B3LYP level.

The effect of protonation is more difficult to discuss because several MOs are strongly perturbed.

Regarding for example the variation of CO bond length, we deal with the 2b2 (antibonding) and 3a1 (bonding) associated to each "lone pair" of oxygen, but the b1 (p) is expected to become more located on oxygen and thus less bonding along CO.

Concluding remarks

The dynamic orbital force (DOF) appears as a good criterion of the bonding/antibonding character of MOs along a given bond. For canonical H-F MOs, this quantity is the force exerted by electrons on nuclei if one electron occupying a given MO is removed, all other electrons being frozen. Indeed, it allows the prediction, with very few exceptions, of the bond length variation upon ionization and protonation, as summarized in Fig. 7. The relative bond lengths variations by ionization,R/Re, are plotted as a function of the H-F (7a) and B3LYP (7b) DOFs. In the blue areas, both DOF and R/Re are positive, corresponding to a lengthening of bonds by removing an electron from a bonding MO. In the red areas both DOF and R/Re are negative, corresponding to a shortening of bonds by removing an electron from an antibonding MO. A very rough relation appears between R/Re and the Hartree-Fock DOFs. It means that, though these DOFs involve the neglect of MO relaxation and of correlation energy, they provide a reliable predictive index for the variation of experimental data upon ionisation, in confirmation to a previous work mainly devoted to diatomic species 10 . The same relation between R/Re and DOF is observed from B3LYP DOFs, with even a better linear correlation.

From a practical point of view, the DOFs are easy to compute and are stable with respect to the basis set, provided double zeta or higher levels are used. 10 Generally, it is no more the case with the classical overlap population which can be strongly dependant on the basis set, especially with extended ones or when diffuse OAs are included. Another criterion for the MO bonding/antibonding character along a bond A-B consists in comparing the MO energy of the mean energy of the AOs of A and B fragments involved in this MO, which is not straightforward in the practice.

(a) (b) The DOFs are also in qualitative agreement with the variation of forces constants in vibration normal coordinates when the molecule is ionized. It is worthy to note that the relatively important bonding character found for the p MOs of halogen hydride is somewhat counterintuitive. Also, it can be surprising at first glance that the "lone pair" of NH3 is bonding, while those of PH3 and AsH3 are antibonding.

1 ) 1 .

 11 Scheme 1. Forces acting in a diatomic molecule AB

Figure 1 .

 1 Figure 1. Bonding (f > 0, yellow) and antibonding (f < 0 dark blue) zones for diatomic A2 and HF molecules.

Figure 3 .

 3 Figure 3. Molecule H2O.Graphical representation of H-F DOFs of valence shell MOs. Blue/red arrows indicate a bonding/antibonding character, with a thickness proportional to the % of maximum DOF

Figure 4 .

 4 Figure 4. Molecules NH3, PH3 and AsH3. Graphical representation of H-F DOFs of the HOMO lone pair. Blue/red arrows indicate a bonding/antibonding character, with a thickness proportional to the % of the maximum DOF

Fig. 5 .

 5 Fig. 5. a1 HOMO lone pairs of NF3, PF3 and AsF3

Figure 6 .

 6 Figure 6. Molecule H2CO. Graphical representation of H-F DOFs of valence shell MOs. Blue/red arrows indicate a bonding/antibonding character, with a thickness proportional to the % of the maximum DOF Some discrepancies appear between HF and B3LYP calculated DOFs. For examples, the 2b2 and 3a1 MOs are found bonding along C-H at HF level and antibonding at B3LYP level.

Figure 7 .

 7 Figure 7. Relative bond length variation upon ionization as function of DOF of the removed electron; (a) DOF at the HF level; (b) DOF at the B3LYP level.

Table 1 .

 1 Molecules HF, HCl and HBr: DOFs (au) of valence MOs at the H-F(B3LYP) levels; bond lengths (Å) of neutral R(AH), cationic R(AH + ) and protonated R(AH2 + ) species; vibration frequency (cm-1 ) and force constant of neutral (AH) and cationic (AH + ) species. a 6-311 G** b CCSD(T)/cc-pVTZ; c B3LYP/ cc-pVTZ; d experimental values from the NIST database(ref. 20)

		HF	HCl	HBr
	MO		DOF H-F(B3LYP) a
	1	0.201 (0.167)	0.103 (0.082)	0.085 (0.063)
	2	0.212 (0.118)	0.111 (0.067)	0.093 (0.058)
	(HOMO)	0.056 (0.047)	0.013 (0.013)	0.008 (0.008)
			Bond lengths b
	R(AH)	0.9173	1.2772	1.4129
	R(AH + )	1.0023	1.3175	1.4451
	Rion (calc)	0.0850	0.0403	0.0322
	Rion (exp) d	0.097	0.040	0.034
	R(AH2 + )	0.9617	1.3068	1.4370
	Rprot	0.0444	0.0296	0.0241
	
		Stretching vibration frequency (force constant) c
	(AH)	4088.0 (10.42)	2936.8 (5.26)	2620.5 (4.13)
	(AH + )	2992.3 (5.58)	2616.8 (4.18)	2372.9 (3.39)
	ion (calc)	-1095.7	-320	-247.6
	ion (exp) d 	-1225.	-318.	-207.

Table 2 .

 2 Molecules H2O, H2S and H2Se: DOFs (au) with respect to A-H length of valence MOs at the H-F(B3LYP)

	levels; bond lengths (Å) of neutral R(AH2), cationic R(AH2 + ) and protonated R(AH3 + ) species; vibration frequencies
	(cm -1 ) and force constants of neutral  (AH2) and cationic (AH2 + ) species a 6-311 G** b CCSD(T)/cc-pVTZ; c
	B3LYP/ cc-pVTZ.
		H2O	H2S	H2Se
	MO		DOF HF(B3LYP) a
	1a1	0.283 (0.224)	0.146 (0.111)	0.127 (0.091)
	1b2	0.294 (0.195)	0.156 (0.107)	0.132 (0.091)
	2a1	0.098 (0.038)	0.040 (0.015)	0.032 (0.014)
	1b1(HOMO)	0.042 (0.038)	0.003 (0.007)	0.003 (0.005)
			Bond lengths b
	R(AH2)	0.9595	1.3406	1.4583
	R(AH2 + )	1.0012	1.3607	1.4747
	Rion	0.0417	0.0201	0.0164
	R(AH3 + )	0.9778	1.3549	1.4688
	Rprot	0.0183	0.0143	0.0105
		Stretching vibration frequency (force constant) c
			AH2
	(a1)	3801.0 (8.89)	2685.3 (4.40)	2391.7 (3.44)
	(b2)	3901.3 (9.70)	2699.4 (4.46)	2406.2 (3.48)
			AH2 +
	(a1)	3326.4 (6.80)	2562.8 (4.01)	2324.2 (3.24)
	(b2)	3372.3 (7.28)	2565.3 (4.033)	2331.8 (3.27)

Table 4 .

 4 Planar NH3, PH3 and AsH3. DOF of the HOMO a1 at the H-F level; bond lengths of AH3 and AH3 + species (CCSD(T)/cc-pVTZ.

	MO	NH3	PH3	AsH3
	HOMO DOF a1	0.037	0.005	0.009
	R(AH3)	0.9952	1.3802	1.4595
	R(AH3 + )	1.0223	1.3955	1.4752
	Rion	0.0271	0.0153	0.0157

Table 5 .

 5 Molecules NF3, PF3 and AsF3: DOF (au) of the HOMO a1 with respect to A-F length at the H-F(B3LYP) levels; bond lengths (Å), stretching vibration frequencies (cm -1 ) and force constants for neutral R(AF3) and cationic R(AF3 + ) species. a 6-311 G** b CCSD(T)/cc-pVTZ; c B3LYP/cc-pVTZ

		NF3	PF3	AsF3
	MO		DOF HF (B3LYP) a
	HOMO a1	-0.169 (-0.154)	-0.161 (-0.129)	-0.116 (-0.078)
			Bond lengths b
	AF3	1.3717	1.5762	1.706
	AF3 +	1.2839	1.5051	1.648
	Rion	-0.0878	-0.071	-0.058
		Stretching vibration frequency (force constant) c
			AF3
	(a1)	1050.4 (9.90)	871.2 (10.0)	720.0 (6.77)
	(e)	895.6 (7.19)	837.4 (9.38)	686.3 (6.34)
			AF3 +
	(a1)	988.5 (9.80)	907.6 (10.1)	753.8 (6.90)
	(e)	1234.8 (13.60)	1063.2 (15.4)	798.1(8.81)

Table 6 .

 6 Molecule H2CO: DOFs (au) with respect to C-O, C-H and H-H distances at the H-F(B3LYP) levels; bond lengths (Å), stretching vibration frequency (cm-1 ) and force constants for neutral H2CO, cationic and protonated H2COH + . a 6-311 G** b CCSD(T)/cc-pVTZ; c B3LYP/cc-pVTZ.

	H2C=O


Vincent Marre
email: vincent.marre@isae.fr

Guilhem Michon
email: guilhem.michon@isae.fr

Vincent Manet
email: vincent.manet@liebherr.com

PERFORMANCE OF NONLINEAR TARGETED ENERGY TRANSFER UNDER STOCHASTIC AND DETERMINISTIC EXCITATIONS

INTRODUCTION

In this paper, a theoretical and experimental investigation of a linear oscillator coupled to a cubic Nonlinear Energy Sink (NES) is presented. During the past decades, NES have been studied extensively in a deterministic framework whereas in practice solicitations are mainly random. Indeed, it is widely recognized that most of engineering structures are submitted to random excitation. This is the case for example for earthquakes, environmental loads (wind, waves, etc ...) and also in service vibration on vehicles. The main idea of the presentation is to propose a simplified approach to estimate the stability threshold of NES under random excitation.

Historically, the principle of Targeted Energy Transfer (TET) was initiated by the work of Gendelman et al. [?] [?]. This allows to highlight the efficiency of a NES to mitigate the impact of vibration on structures. The theoretical analysis (Complexification Averaging, Fixed Point and Asymptotic Analysis) of the NES coupled to a linear oscillator presented herein are based on [?], [?] and [?]. The determination of the optimal parameters for the NES under deterministic excitation was based on the appearence of the detached resonance curve as discussed in [?].

On the basis of these results, the Extreme Response Spectrum (ERS) proposed by Lalanne [?] is investigated in order to evaluate its capability of defining an equivalent white noise able to trigger the instability on previously designed NES. In order to check that our case study lies in the range of application of the ERS method a stochastic analysis is performed to estimate the steady-state joint probability density function governed by the Fokker-Planck equations. To conclude, experimental results for deterministic and stochastic excitations are presented in order to confirm the relevance of the method.

DETERMINISTIC ANALYSIS

The aim of this section is to determine the optimal characteristics for a NES dedicated to control the first natural frequency (around 350Hz) of our experimental setup. The excitation is supposed to be a 2g sine-sweep between 5Hz and 2kHz. The system is governed by the set of equation of motion and was modeled with Nastran software.

With the assumption that the first mode is uncoupled with each other and has a linear behavior, the full finite element model was reduced (Craig & Bampton) to a classical two DOF system. The equations of motion were then projected on the Craig & Bampton basis (with one component mode and one physical degree of freedom). And then, the equations are simplified and rewritten in a classical form. Finally, the steady-state response regimes and their stability are computed and the optimal characteristics of the NES are evaluated (see figure 1)

Thanks to that results a NES made of a lever pulling transversely on two stainless steel cables (cubic stiffness) was proposed.

STOCHASTIC ANALYSIS

The aim of this section is to evaluate a white noise excitation that could trigger the NES which has been defined previously. The idea is to propose a simplified and equivalent method to evaluate the random excitation associated to the NES thresholds.

This method is based on the Extreme Response Spectrum (ERS) method (see Ref.

[?]).

ERS accel ( f ) = π f QG z( f )ln( f .T ) ( 1
)
Where f is the frequency (Hz), Q the amplification factor, T the duration (in seconds) and G z is the spectrum in g/Hz.

Then considering the ERS of a 2g harmonic excitation we can estimate an equivalent white noise with a PSD amplitude of 0.031 g/Hz.

The validity of the ERS method was verified by calculating the steady-state joint probability density function governed by the Fokker-Planck Kolmogorov (FPK) equations.

EXPERIMENTAL RESULTS

The setup was tested experimentally with and without the NES in order to estimate its efficiency to mitigate vibration for both type of excitation. The response of the system with the NES under 2g sine sweep between 5Hz and 2kHz is depicted in figure 2 when the excitation frequency approach 350Hz. We can observe a Strong Modulated response that occurs for this forcing amplitude. This figure presents the velocity measured on the main oscillator and on the NES. In each case, a Hilbert Transform is performed to obtain the instantaneous frequency (bottom view) to illustrate the resonance capture.

In the same way, figure 3 presents the experimental results for a white noise (0.031 g/Hz). As observed previously for the harmonic excitation, a strong modulated response appears on the secondary oscillator. That leads to a relevant attenuation on the amplitude response of the main oscillator.

CONCLUSION

In this presentation, the behavior of a linear oscillator with an embedded NES under deterministic and stochastic excitation was investigated theoretically and experimentally. At first a NES was designed to control our experimental setup and to exhibit a strong modulated response under 2g harmonic excitation using a classical approach. In a second time, the Extreme Response Spectrum method allowed us to estimate the NES threshold and to determine a white noise excitation able to trigger an instability on the NES. Despite some discrepancies, the experimental results show a good agreement with the theory for harmonic as well as random excitation. That confirms that the ERS method is relevant for designing a NES under Random Excitation.

FIGURE 1 :

 1 FIGURE 1: a) Fixed point response : dot line (...) denotes system response without NES and solid line (--) system response with NES b) zone 1 : The detached resonance, zone 2 : NES is not activated and zone 3 : NES is activated with Strong Modulated Response -optimal zone

FIGURE 2 :

 2 FIGURE 2: Deterministic excitation : Response on main oscillator (left) and NES (right)-Transient response (Top view) and Instantaneous Frequency (Bottom view)

FIGURE 3 :

 3 FIGURE 3: Stochastic excitation : Response on main oscillator (left) and NES (right)-Transient response (Top view) and Instantaneous Frequency (Bottom view)