Arthur Milchior
email: arthur.milchior@lacl.fr

Büchi Automata Recognizing Sets of Reals Definable in First-Order Logic with Addition and Order

This work considers encodings of non-negative reals in a fixed base, and their encoding by weak deterministic Büchi automata. A Real Number Automaton is an automaton which recognizes all encodings of elements of a set of reals. We explain in this paper how to decide in linear time whether a set of reals recognized by a given minimal weak deterministic RNA is FO[IR; +, <, 1]-definable. Furthermore, it is explained how to compute in quasi-quadratic (respectively, quasi-linear) time an existential (respectively, existential-universal) FO[IR; +, <, 1]-formula which defines the set of reals recognized by the automaton. As an additional contribution, the techniques used for obtaining our main result lead to a characterization of minimal deterministic Büchi automata accepting FO[IR; +, <, 1]-definable set.

Introduction

Those results naturally led to the following problem: deciding whether a finite automaton recognizes a FO [IN; +, <]-definable set of d-tuples of integers for some dimension d ∈ IN >0 . In the case of dimension d = 1, decidability was proven in [?]. For d > 1, decidability was proven in [?]. Another algorithm was given in [?], which solves this problem in polynomial time. For d = 1, a quasi linear time algorithm was given in [?].

The above-mentioned results about sets of tuples of natural numbers and finite automata have then been extended to sets of tuples of reals recognized by a Büchi automaton. The notion of Büchi automata is a formalism which describes languages of infinite words, also called ω-words. The Büchi automata are similar to the finite automata. The main difference is that finite automata accept finite words which admit runs ending on accepting state, while Büchi automata accept infinite words which admit runs in which an accepting state appears infinitely often.

One of the main differences between finite automata and Büchi automata is that finite automata can be determinized while deterministic Büchi automata are less expressive than Büchi automata. For example, the language L fin(a) of words containing a finite number of times the letter a is recognized by a Büchi automaton, but is not recognized by any deterministic Büchi automaton. This statement implies, for example, that no deterministic Büchi automaton recognizes the set of reals of the form nb p with n ∈ IN and p ∈ Z Z, that is, the set of reals whose encoding ends with 0 or (b -1) repeated infinitely many times.

A main difference between the two classes of deterministic automata is that the class of languages recognized by deterministic finite automata is closed under complement while the class of languages recognized by deterministic Büchi automata is not. For example, L fin(a) is not recognized by any deterministic Büchi automaton while its complements L inf(a) is recognized by a deterministic Büchi automaton.

However, the set of weak deterministic Büchi automata is closed under complement. A weak deterministic Büchi automaton is a deterministic Büchi automaton whose set of accepting states is a union of strongly connected components. Handling weak Büchi automata is similar to manipulating finite automata. A set is said to be weakly b-recognizable if it is recognized by a weak automaton in base b. The class of weak deterministic Büchi automata is less expressive than the class of deterministic Büchi automata. For example, as mentionned above, the language L inf(a) is recognized by a deterministic Büchi automaton, but this language is not recognized by any weak deterministic Büchi automaton. This implies that, for example, no weak deterministic Büchi automaton recognizes the set of reals which are not of the form nb p with n ∈ IN and p ∈ Z Z, since those reals are the ones whose encoding in base b contains an infinite number of non-0 digits. Furthermore, by [?], weak deterministic Büchi automata can be efficiently minimized. Standard definitions are recalled in Sect. ??. Sets of states of automata reading reals are studied in Sect. ??. Furthermore, a method to efficiently solve automaton problem is introduced. In Sect. ??, given a simple set, an automaton accepting it is constructed. A characterization of minimal deterministic Büchi automata accepting a FO [IR; +, <, 1]-definable set is given in Sect. ??. This characterization is similar to the insight given in [?] and leads to a linear time algorithm deciding whether a minimal RNA recognizes a FO [IR; +, <, 1]-definable set. This algorithm does not return any false positive on weak deterministic Büchi automata which are not RNA. A false negative is exhibited at the end of Sect. ??. Given a minimal weak RNA automaton accepting a simple set, it is shown in Sect. ?? that an existential (respectively, existential-universal) FO [IR; +, <, 1]-formula which defines R is computable in quasi-quadratic (respectively quasi-linear) time.

Definitions

The definitions used in this paper are given in this section. Some basic lemmas are also given. Most definitions are standard.

Let IN, Z Z, Q and IR denote the set of non-negative integers, integers, rationals and reals, respectively. For R ⊆ IR, let R ≥0 and R >0 denote the set of non-negative and of positive elements of R, respectively. ,[a,b)) be the half-open interval equals to the union of (a, b) and of {b} (respectively, {a}). For r ∈ IR let r be the greatest integer less than or equal to r.

Finite and Infinite Words

An alphabet is a finite set, its elements are called letters. A finite (respectively ω-) word over alphabet A is a finite (respectively infinite) sequence of letters of A. That is, a function from [n] to A for some n ∈ IN (respectively from IN to A). A set of finite (respectively ω-) words over alphabet A is called a language (respectively, an ω-language) over alphabet A. The empty word is denoted .

Let w be a word, its length is denoted |w|, it is either a non-negative integer or the cardinality of IN. For n < |w|, let w[n] denote the n-th letter of w. For v a finite word, let u = vw be the concatenation of v and of w, that is, the word of length |v| + |w| such that u

[i] = v[i] for i < |v| and u[|v| + i] = w[i] for i < |w|. Let w [< n] denote the prefix of w of length n, that is, the word u of length n such that w[i] = u[i] for all i ∈ [n -1].
Similarly, let w [≥ n] denote the suffix of w without its n-th first letters, that is, the word u of length |w| -n such that u

[i] = w[i + n] for all i ∈ [|w| -n]. Note that w = w [< i] w [≥ i] for all i < |w|.
Let L be a language of finite words and let L be either a ω-language or a language of finite words. Let LL be the set of concatenations of the words of L and of L . For i ∈ IN, let L i be the concatenations of i words of L. Let L * = i∈IN L i and L + = i∈IN >0 L i . If L is a language which does not contain the empty word, let L ω be the set of infinite sequences of elements of L.

Encoding of Real Numbers. Let us now consider the encoding of numbers in an integer base b ≥ 2. Let Σ b be equal to [b -1]; it is the set of digits. The base b is fixed for the rest of this paper.

The function sending words to the number they encode are now introduced. Let w be an ω-word with exactly one . It is of the form w = w I w F , with

w I ∈ Σ * b and w F ∈ Σ ω b .
The word w I is called the natural part of w and the ω-word w F is called its fractional part. Let [w I ]

I b = |w|-1 i=0 b |w|-1-i w I [i], let [w F ] F b = i∈IN b -i-1 w F [i] and finally, let [w I w F ] R b = [w I ] I b + [w F ] F b
. Some properties of concatenation and of encoding of reals are now stated.

Lemma 1. Let v ∈ Σ * b , v ∈ Σ + b , w ∈ Σ ω b and a ∈ Σ b . Then: [w] F b = [0 w] R b , [aw] F b = a + [w] F b /b, [va] I b = b [v] I b + a and [v ω ] F b = [v] I b / b |v| -1 .
Some basic facts about rationals are recalled (see e. Following [?], a language L is said to be saturated if for any number r which admits an encoding in base b in L, all encodings in base b of r belong to L. The saturated languages are of the form

L b (R) for R ⊆ IR ≥0 . Note that [L b (R)] R b = R for all sets R ⊆ IR ≥0 . Note also that L ⊆ L b ([L] R b )
, and the subset relation is an equality if and only if L is saturated.

All non-empty sets of reals have infinitely many encodings in base b. For example, for

I ⊆ IN an arbitrary set, 0 * {0, 1} ω \ 0 i 1 ω | i ∈ I is an encoding in base 2 of the simple set [0, 1]
. This language is saturated if and only if I = ∅.

Deterministic Büchi Automata

This paper deals with deterministic Büchi automata. This notion is now defined.

A Deterministic Büchi automaton

A is a 5-tuple (Q, A, δ, q 0 , F ), where Q is a finite set of states, A is an alphabet, δ : Q × A → Q is the transition function, q 0 ∈ Q is the initial states and F ⊆ Q is the set of accepting states. A state belonging to Q \ F is said to be a rejecting state.
From now on in this paper, all automata are assumed to be deterministic. The function δ is implicitly extended on Q × A * by δ(q, ) = q and δ(q, wa) = δ(δ(q, w), a) for a ∈ A and w ∈ A * .

Let A be an automaton and w be an infinite word. A run π of A on w is a mapping π : IN → Q such that π(0) = q 0 and δ(π(i), w[i]) = π(i + 1) for all i < |w|. The run is accepting if there exists a state q ∈ F such that there is an infinite number of i ∈ IN such that π(i) = q. Let A be a finite automaton. Let L ω (A) be the set of infinite words w such that a run of A on w is accepting.

Accessibility and Recurrent States. Some definitions related to the underlying labelled graph of Büchi automata are introduced in this section. A state q is said to be accessible from a state q if there exists a finite non-empty word w such that δ(q , w) = q. Following [?], a state q is said to be recurrent if it is accessible from itself and transient otherwise. Transient states are called trivial in [?]. The strongly connected component of a recurrent state q is the set of states q such that q is accessible from q and q is accessible from q . A strongly connected component C is said to be a leaf if for all a ∈ A, for all q ∈ C, δ(q, a) ∈ C. Let C be a strongly connected component. It is said to be a cycle if for each q ∈ C, there exists a unique s q ∈ A such that δ(q, s q ) ∈ C.

The transient states of the automaton pictured in Figure ?? are q 1 , q 10 , q 11 , q 10 and q 11 . All other states are recurrent. The cycles are {q 0 }, {q 0 , q 0 0 }, {q 10 0 }, {q 10 1 , q 10 10 }, {q 11 0 } and {q 11 1 , q 11 10 }. The strongly connected components which are not cycles are q ∅,A , {q ∞,A } and q [0,1],A .

For q ∈ Q, let A q be (Q q , A, δ, q, F q ), where Q q is the set of states of Q accessible from q, and F q = F ∩ Q q . Note that, if there is no finite word w such that δ(q 0 , w) = q 0 , then Q q Q for all q = q 0 . Quotients, Morphisms and Weak Büchi Automata The Büchi automaton A = (Q, A, δ, q 0 , F ) is said to be minimal if, for each distinct states q and q of A, L ω (A q ) = L ω (A q ). Let A = (Q, A, δ, q 0 , F ) be a Büchi automaton and A = (Q , A, δ , q 0 , F ) be a minimal Büchi automaton. A surjective function µ : Q → Q is a morphism of Büchi automata if and only if µ(q 0 ) = q 0 and, for all

q ∈ Q, L ω (A q ) = L ω A µ(q) .
The Büchi automaton A is said to be weak if for each recurrent accepting state q of A, all states of the strongly connected components of q are accepting. An ω-language is said to be (weakly) recognizable if it is a set of word accepted by a (weak) Büchi automaton. An example of weak deterministic Büchi automaton is now given. This example is used through this paper to illustrate properties of Büchi automaton reading set of real numbers. of A on the ω-word 011 (10) ω is (q 0 , q 0 , q 1 , q 3 , q 11 , q 11 1 , q 11 10 , . . . ), with the two last states repeated infinitely often. The Büchi automaton A does not accept 011 (10) ω since this run does not contain any accepting state. The run of A on ω-word 1 ω is q 0 , q 0 , q [0,1],A , . . . with the last state repeated infinitely often. The Büchi automaton A accepts 1 ω since the accepting state q [0,1],A appears infinitely often in the run.

Example 1. Let R = 1 3 , 2 ∪ 8 3 , 3 ∪ 11 3 ,
The main theorem concerning quotient of weak Büchi automata is now recalled.

Theorem 1 ([?]

). Let A = (Q, A, δ, q 0 , F ) be a weak Büchi automaton with n states such that all states of A are accessible from its initial state. Let c be the cardinality of A. There exists a minimal weak Büchi automaton A such that there exists a morphism of automaton µ from A to A . The automaton A and the morphism µ are computable in time O (n log(n)c) and space O (nc).

The Büchi automaton A R pictured in Figure ?? is weak and is not minimal. Its minimal quotient is pictured in Figure ??. The following lemma states that each strongly connected component of a quotient by a morphism µ from an automaton A is the image of a strongly connected component of A. It allows to prove that some properties, such as being a cycle, is closed under taking quotient.

q0 q10 q∞,R q1 q10 q10 0 q0 q0 0 Q [0,1],R 0 1 0,1 0,1 0,1 0 1 1 1 0 0 0,1
Lemma 2. Let A = (Q, A, δ, q 0 , F ) and A = (Q , Σ b , δ , q 0 , F ) be two Büchi automata. Let µ be a morphism from A to A . Let C be a strongly connected component of A . There exists a strongly connected component C ⊆ Q such that µ(C) = C and such that, for all q ∈ Q \ C accessible from C, µ(q) ∈ C .

Real Number Automata.

For A a Büchi automaton over alphabet

Σ b ∪ { }, let [A] R b denote [L ω (A)] R b . It is said that A recognizes [A] R b . Following [?], a Büchi automaton over alphabet Σ b ∪{ } is said to be a Real Number Automaton (RNA) if it recognizes a subset of Σ * b Σ ω b
and if the language L ω (A) is saturated. The Büchi automata pictured in ?? and ?? are RNA. Clearly, the RNAs are the Büchi automata which recognize saturated languages.

Logic

The logic FO [IR; +, <, 1] used in this paper is introduced in this section. FO stands for first-order. The first parameter IR means that the (free or quantified) variables are interpreted by non-negative real numbers. The + and < symbols mean that the addition function and the binary order relation over reals can be used in formulas. Finally, the last term, 1, means that the only constant is 1. The logic FO [IR; +, <, 1] is denoted by L in [?], where it is proven that this logic admits quantifier elimination. In this paper, all results deal with the quantifier-free, the existential fragment and the existential-universal fragment of FO [IR; +, <, 1] denoted by Σ 0 [IR; +, <, 1], Σ 1 [IR; +, <, 1] and Σ 2 [IR; +, <, 1] respectively.

In the rest of the paper, rationals are also used in the formulas. Admitting rationals does not change the expressivity since all rational constants are Σ 0 [IR; +, 1]-definable. The length of a formula φ is denoted by |φ|. It is such that each symbol takes one bit of space, apart from integers n and rationals n/m which take log(1 + |n|) and log(1 + |n| + |m|) bits of space respectively.

First-Order Definable Sets of Reals. In this section, notations are introduced for the kind of sets studied in this paper: the FO [IR; +, <, 1]-definable sets. Following [?, Sect. 6], the FO [IR; +, <, 1]-definable sets are called the simple sets. By [?, Sect. 6], those sets are the finite unions of intervals with rational bounds. It implies that there exists an integer t R such that for all x, y ≥ t R , x belongs to R if and only if y belongs to R. The least such integer t R is called the threshold of R.

Note that every closed and half-closed intervals is the union of an open interval and of singletons, hence it can be assumed that any simple set R is of the form

R = I-1 i=0 (ρ i,L , ρ i,R ) ∪ J-1 i=0 {ρ i,S }, with ρ i,L , ρ i,S ∈ Q and ρ i,R ∈ Q ∪ {∞}.
The ρ i,L 's are the left bounds, the ρ i,R 's are the right bounds and the ρ i,S 's are the singletons.

For example, let R = 1 3 , 2 ∪ 8 3 , 3 ∪ 11 3 , ∞ as in Ex. ??. Then t R is 4,

I = 3, J = 2, ρ 1,L = 1 3 , ρ 2,R = 2, ρ 2,L = 8 3 , ρ 2,R = 3, ρ 3,L = 11/3, ρ 3,R = ∞, ρ 1,S = 2 and ρ 2,S = 3.

Some Sets of states of Automata Reading Reals

We now introduce five sets of states used in the algorithms of this paper.

Definition 1 (Q ∅,A , Q [0,1],A , Q ∞,A , Q I,A and Q F,A ). Let A = (Q, A, δ, q 0 , F ).
-Let Q ∅,A be the set of states q such that A q recognizes the empty language.

-Let Q [0,1],A be the set of states q such that A q recognizes Σ ω b . -Let Q ∞,A be the set of states q such that A q recognizes the language

Σ * b Σ ω b . -Let Q I,A be the set of states q such that A q recognizes a subset of Σ * b Σ ω b . -Let Q F,A
be the set of states q such that A q recognizes a subset of Σ ω b . In [?], the strongly connected components included in Q ∅,A are called empty and the ones included in Q [0,1],A are called universal.

Intuitively the states belonging to Q I,A and to Q F,A are the states which can be visited while the automaton read the natural and the fractional part of the number respectively.

Let A be the automaton pictured in Figure ??. Let q ∅,A be the state δ(q 10 0 , 1), which is not pictured in Figure ?

?. Then Q [0,1],A = q [0,1],R , Q ∞,A = {q ∞,R } and Q ∅,A = q ∅,A .
Furthermore, the states of Q I,A are pictured in the top row of Figure ??, they are q 0 , q 1 , q 10 , q ∞,R and q ∅,R . Finally, the states of Q F,A are pictured in the second row of Figure ??, they are q 10 , q 10 0 , q 0 , q 0 0 , Q [0,1],R and q ∅,R .

In a minimal weak Büchi automaton A, let q ∅,A , q [0,1],A and q ∞,A denote the only state q such that A q recognizes the languages ∅, Σ ω b and Σ * b Σ ω b respectively. The following lemma states that the five sets introduced in Def. ?? are linear time computable.

Lemma 3. Let A be a weak Büchi automaton with n states. Then the sets

Q ∅,A , Q [0,1],A , q ∞,A , Q I,A and Q F,A are computable in time O (nb).
It is explained how to compute Q ∅,A . The other sets are computed similarly.

Proof. Tarjan's algorithm [?] can be used to compute the set of strongly connected component in time O (nb), and therefore the set of recurrent states. By definition, q ∈ Q ∅,A if and only if A q accept no ω-word. It is equivalent to the fact that no recurrent state accessible from q are accepting. Equivalently, Q ∅,A is the greatest set of states q such that, q is not a recurrent accepting state, and furthermore, for all a ∈ Σ b ∪ { }, δ(q, a) ∈ Q ∅,A . This naturally leads to the following greatest fixed-point algorithm.

Two sets PotentiallyEmpty and ToProcess are used by the algorithm. The algorithm initializes the set PotentiallyEmpty to Q and initializes the set ToProcess to the empty set. The algorithm runs on each recurrent state q. For each state q, if q is accepting, then q is removed from PotentiallyEmpty and added to ToProcess. The algorithm then runs on each element q of ToProcess. For each state q, the algorithms removes q from ToProcess and runs on each predecessors q of q. For each q , if q is in PotentiallyEmpty, then q is removed from PotentiallyEmpty and added to ToProcess. Finally, when ToProcess is empty, the algorithm halts and Q ∅,A is the value of PotentiallyEmpty.

From simple sets to automata

Let us fix a simple non-empty set R R ≥0 . In this section a weak RNA A R which recognize L ω (R) is constructed. Since R is a simple set, there exists an

integer t R ∈ N ≥0 such that [t R , ∞) is either a subset of R or is disjoint from R. Without loss of generality, it is assumed that t R ≥ b.
As seen in Section ??, R can be expressed as

I-1 i=0 (ρ i,L , ρ i,R ) ∪ J-1 i=0 {ρ i,S } with ρ i,j ∈ Q ∩ [0, t R ].
Without loss of generality, it can be assumed that all integers n belonging to [0, t R ] are of the form ρ i,j for some i, j. It suffices either to assume that there is some i ∈ IN such that n is of the form ρ i,S if n ∈ R and of the form ρ i,L and ρ i,R otherwise.

Since the ρ i,j are rationals, their encodings in base b are of the form u i,j,k v ω i,j,k

with u i,j,k ∈ Σ * b Σ * b such that u i,j,k [0] = 0 and v i,j,k ∈ Σ + b .
Since there are at most two encodings, a third index, k, is also required. Up to replacing the words u i,j,k by u i,j,k v n i,j,k , it can be assumed without loss of generality that, for all i, j, k, i , j , k , the word u i,j,k is not a strict prefix of u i ,j ,k and if u i,j,k = u i ,j ,k then v i,j,k = v i ,j ,k . The formal definition of A R is now given.

Definition 2 (A R ). Let R
[0, ∞) be a simple non-empty set. Note that t R > 0. Let A R be the automaton (Q, Σ b ∪ { } , δ, q 0 , F ) where:

-Q contains the states q ∅,A , q [0,1],A , q ∞,A , and a state q w for each strict prefix w of a word u i,j,k v i,j,k . -F contains q [0,1],A , and the q w 's, for w ∈ Σ * b Σ ω b some non-empty prefix of some u i,S,k v i,S,k .

and the transition function is such that, for each word w and for each letter a:

• δ(q , 0) = q .

• For wa a strict prefix of some u i,j,k v i,j,k , δ(q w , a) = q wa .

• For wa of the form u i,j,k v i,j,k , δ(q w , a) = q u i,j,k . It is now assumed that wa is not a prefix of or equal to any u i,j,k v i,j,k .

•

If wa ∈ Σ * b , then δ(q w , a) is q ∞,A if [t R , ∞) ⊆ R and q ∅,A otherwise. • For wa ∈ Σ * b Σ * b , δ(q w , a) is q ∅,R if [wa0 ω ] R b ∈ R and q [0,1],A otherwise. • For q being q [0,1],R , q ∞,R or q ∅,R , δ(q, a) = q. • δ(q ∞,R , ) = q [0,1],R . • For q being q [0,1],A or q ∅,A or q w for w ∈ Σ * b Σ * b , δ(q, ) = q ∅,A . It can be shown that A R recognizes R. Let R = 1 3 , 2 ∪ 8 3 , 3 ∪ 11 3 ,
∞ as in Example ??. The automaton A R is pictured in Figure ??, without the non accepting state q ∅,A . Its minimal quotient is pictured in Figure ??.

A second example is now given, which shows that the minimal number of intervals of a simple set may be exponential in the number of state of the minimal Büchi automaton accepting this set. For every non-negative integer n, let R n be m2 -(n-1) | m ∈ [2 n-1 ] . It is the set of reals which admit an encoding w in base 2 whose suffixes w [≥ n] are either equal to 0 ω or to 1 ω . This set can not be described with less than 2 n-2 intervals and is recognized by the automaton A n :

A n = {q i | i ∈ [n]} ∪ q n+1,
0 , q n+1,1 , q ∅,A , Σ b , δ, q 0 , {q n+1,0 , q n+1,1 } , where the transition function is such that, for a ∈ Σ 2 , and i ∈ [n -1] \ {0}, δ(q 0 , ) = q 1 , δ(q i , a) = q i+1 , δ(q n , a) = q n+1,a , δ(q n+1,a , a) = q n+1,a . For each state q and letter a such that δ(q, a) is not defined above, δ(q, a) = q ∅,A .

Deciding Whether an Automaton Recognizes a Simple Set

It is explained in this section how to decide whether a minimal weak RNA accepts a simple set. The first main theorem of this paper is now given.

Theorem 2. It is decidable in time O (nb) and space O (n) whether a minimal weak Büchi RNA with n states recognizes a simple set.

In order to prove this theorem, a proposition is is now given. This property is a general method used to efficiently decide properties of automata. This method is similar to the method used in [?] and in [?].

Proposition 1. Let A be a class of weak Büchi automata and let L be the class of languages {L ω (A) | A ∈ A }. Let L be a class of languages over an alphabet such that there exists a class A of weak Büchi automata such that:

1. there exists an algorithm α which decides in time t(n, b) and space s(n, b) whether a Büchi automaton belongs to A, for n the number of states and b the number of letters, 2. for each L ∈ L ∩ L , there exists an automaton A ∈ A which recognizes L, 3. the minimal quotient of any automaton of A belongs to A and 4. every language recognized by an automaton belonging to A belongs to L.

The algorithm α decides in time t(n, b) and space s(n, b) whether a minimal automaton of A recognizes a language of L. Furthermore, the algorithm α applied to an automaton belonging to A \ A may not return a false positive.

Proof. Let A be an automaton which recognizes a language L. Let us assume that α accepts A, by Prop. (??), A ∈ A, hence by Prop. (??), L ∈ L.

Let us now assume that A ∈ A and that L ∈ L. By definition of L , L ∈ L , hence L ∈ L ∩ L , thus by Prop ??, there exists A ∈ A which recognizes L. Since A and A recognize the same language, they have the same minimal quotient, which is A. By Prop. ??, A ∈ A. Thus, by Prop. (??), α accepts A.

In this paper, A is the set of RNAs, hence L is the class of saturated recognizable languages. The class of languages L is the class of base b encoding of non-empty sets R R ≥0 . The cases of R = R ≥0 and of R = ∅ being special cases. The class A of automata is now introduced. Definition 3 (A). Let A be the set of weak Büchi automata A, of the form (Q, Σ b ∪ { } , δ, q 0 , F ), such that, for each strongly connected component C ⊆ Q F,A \(Q [0,1],A ∪Q ∅,A ), there exists β <,C and β >,C , two states of Q [0,1],A ∪Q ∅,A , such that, for all q ∈ C: Lemma 4. Let A ∈ A be an automaton with n states recognizing a set R. If A contains a state q ∞,A , as in Definition ??, then

(b n-1 , ∞) ⊆ R, otherwise (b n-1 , ∞) ∩ R = ∅.
Proof (Sketch of proof of Theo. ??). Using Lem. ??, the algorithms checks whether A accepts a subset L of Σ * b Σ ω b , if it is not the case, the algorithm rejects. The algorithms also checks whether

L is ∅ or Σ * b Σ ω b .
If it is the case, the algorithm accepts. It is now assumed that A accepts a non-empty language L Σ * b Σ ω b . Let L be the set of saturated languages and A be the set of RNAs. Let L be the set of encoding of simple non-empty sets R IR ≥0 . In order to prove this theorem, it suffices to show that A admits the four properties of Proposition ??.

Each property of Def. ?? is testable in time O (nb) and space O (n). Therefore, it is decidable in time O (nb) and space O (n) whether a weak Büchi automaton A with n states belongs to A. Hence Property (??) of Prop. ?? holds.

For R R ≥0 a non-empty simple set, the automaton A R of Def. ?? belongs to A. Therefore Property (??) of Prop. ?? holds.

Let A ∈ A be a RNA. Let A be its minimal quotient. It can be proven that A satisfies the properties of Def. ??, hence A ∈ A. Therefore Property (??) of Prop. ?? holds.

Property (??) of Prop. ?? is now considered. Automata satisfying Properties (??), (??) and (??) of Def. ?? are studied in [?]. It is shown that automata satisfying those properties accepts a set R such that R ∩ [i, i + 1] is a finite union of intervals with rationals boundaries for all i ∈ IN. Lemma ?? ensures that furthermore, there is some t ∈ IN such that [t, ∞) is either a subset of R or is disjoint from R. Thus, an automaton of A recognize a finite union of interval with rational boundaries, i.e. a simple set. Therefore Property (??) of Prop. ?? holds.

The algorithm of Theo. ?? takes as input a minimal weak RNA and runs in time O (nb). It should be noted that it is not known whether it is decidable in time O (nb) whether a minimal Büchi automaton is a RNA. However, if the algorithm of Theo. ?? is applied to a weak Büchi automaton which is not a Real Number Automaton, the algorithm returns no false positive. An example of false negative is now given. The not-saturated language L = (00) * (01 + 2) Σ *

3

Σ ω 3 encode the simple set of reals R >0 . However, the minimal automaton recognizing L it is not accepted by the algorithm of Theo. ??.

From Automata to Simple Set

It is explained in this section how to compute a first-order formula which defines the simple set accepted by a weak RNA. The exact theorem is now stated. The proof of Theo. ?? consists mostly in encoding in a first-order formula φ(x) the run of A over an encoding w of x. The following lemma allows to consider two distinct part of the run on the fractional part of w. The first part of the run is of length at most n. The second part on the run begins on a state belonging to a restricted set of states. Lemma 5. Let A ∈ A be minimal with n states and q ∈ Q F,A . Let w I ∈ Σ * b and w F ∈ Σ ω b . Let Q ⊆ Q F,A be a set containing exactly one state of each strongly connected component. Then, there exists s ∈ [n] such that δ(q, w I w F [< s]) ∈ Q.

The following lemma allows to reduce the size of a formula by adding quantifications.

Lemma 6. Let ψ(x, x ) be a formula of length l and

(x i ) i∈[n-1] be n vari- ables. Then i∈[n-2] ψ(x i , x i+1 ) is equivalent to the following formula of length O (n + l): ∀y, y .    i∈[n-2] [y . = x i ∧ y . = x i+1 ]    =⇒ ψ(y, y ).
A sketch of the proof of Theo. ?? can now be given.

Proof (Proof of Theo. ??

). Let R = [A] R b .
As shown in Sect. ??, it can be assumed that A belongs to A. By Lem. ??, in order to construct a formula which defines R it suffices to construct a formula φ(x) which defines R ∩ [0, b n-1 ). The formula φ(x) is the conjunction of four subformulas of size O n 2 b log(nb) . Let x ∈ [0, b n-1 ) and let w be an encoding of x without leading 0 in the natural part.

The first formula, ψ(x, x I , x F ), states that x = x I + x F and that x I ∈ IN. Since x I < b n-1 , in order to state that x I ∈ IN, it suffices to state that x I is of the form

n-2 i=0 a i b i for a i ∈ [b -1]. More precisely, it suffices to state that x I is of the form (c n + b(c n-1 + b(• • • + b(c 0 ) . . . ))) with the c i belonging to [b -1].
This can be stated by existentially quantifying the 2n partial sums and products and taking disjunctions over each c i . This can be done by a formula ψ(x I ) of size O (nb log(b)).

Let q be the state δ(q 0 , w I ). The second formula, φ I (x I , q), states that the state δ(q 0 , w I ) is equal to q. This formula existentially quantifies 2n variables. Those variables encode the n first steps of the runs and the values of w I [< i] for i < n. Each step of the computation can be encoded by a Σ 0 [IR; +, <, 1]-formula of length O (nb log(b)), using the equalities of Lem. ??. Since x I < b n-1 , |w I | < n, the formula φ I (x I , q) have to consider at most n steps of the computation. The formula φ I (x I , q) is a conjunction of n formulas of size O n 2 b log(b) and thus the size of φ

I (x I , q) is O n 2 b log(b) .
Let Q be a set of states as in Lem. ?? and let q be the first state of Q in the run of A on w. The third formula, φ F (q, x F , q , x F ) states that there exists i ∈ [n] such that δ(q, w F [< i]) = q , that q ∈ Q and that x F = [w F [≥ i]] F b . By Lem. ??, i is at most n. Hence, similarly to φ I (x I , q), the size of the formula φ F (q, x F , q , x F ) is O n 2 b log(b) .

Finally, the fourth formula φ F (q , x F ), states that A q accepts w F [≥ i]. Let c be the number of strongly connected components in A. For C a strongly connected components, let n C be its number of state and q C the only state of C ∩ Q. Let us assume that, for each strongly connected component C, there exists a formula φ C (q , x F ) of length O (n C b log(n C b)) which states that A q accepts w F [≥ i]. Then the formula φ F (q , x F ) is a disjunction of c formulas q . = q C ∧ φ C (q , x F ) and its length is O ( C n C b log(n C b)) = O (nb log(nb)).

It is now explained how to construct φ C (q , x F ). Since A ∈ A, by Prop. ?? of Def. ??, strongly connected components of automata included in Q F,A are either q ∅,A , q [0,1],A , or a cycle. In the first two cases, φ C (q , x F ) is the formula False or True respectively. Let us consider the third cases. Let v q be the word of size n C such that δ(q , v q ) = q . Since C is cycle, this word exists and is a unique. Then let y = v ω q F b = [v q ] I b / (b n C -1). Recall that the notations β <,C and β >,C are introduced in Def. ??. Then the formula φ C (q , x F ) states that q ∈ C and that either (x F < y and β <,C ∈ Q [0,1],A ), either (x F = y and q ∈ F ), or (x F > y and β >,C ∈ Q [0,1],A ). It is indeed a formula of length O (n C b log(n C b)).

Finally, in order to reduce the size of the formula to O (nb log(nb)), it suffices to replace the conjunctions of φ I (x I , q) and of φ F (q, x F , q x F ) by a universal quantifications, as explained in Lem. ??.

Conclusion

In this paper, we proved that it is decidable in linear time whether a minimal weak Büchi Real Number Automaton A reading a set of real number R recognizes a finite union of intervals. It is proven that a quasi-linear sized existentialuniversal formula defining R exists. And that a quasi-quadratic sized existential formula defining R also exists.

The theorems of this paper lead us to consider two natural generalization. We intend to adapt the algorithm of this paper to similar problems for automata reading vectors of reals instead of automata reading reals. We also intend to solve the similar problem of deciding whether an RNA accepts a FO [IR, IN; +, <]definable set of reals. Solving this problem requires to solve the problem of deciding whether an automaton reading natural number, beginning by the mostsignificant digit, recognizes an ultimately-periodic set. Similar problems has already been studied, see e.g [?,?] and seems to be difficult. Finally, we also intend to consider how to efficiently decide whether an automaton is a Real Number Automaton or a Real Vector Automaton.

The author thanks Bernard Boigelot, for a discussion about the algorithm of Theo. ??, which led to a decrease of the computation time. He also thanks the anonymous referees of for their remarks and suggestion to improve the paper.

  This paper deals with logically defined sets of numbers encoded by weak deterministic Büchi automata. The sets of tuples of integers whose encodings in base b are recognized by a finite automaton are called the b-recognizable sets. By [?], the b-recognizable sets of vectors of integers are exactly the sets which are FO [IN; +, <, V b ]-definable, where V b (n) is the greatest power of b dividing n. It was proven in [?,?] that the FO [IN; +, <]-definable sets are exactly the sets which are b-and b -recognizable for every b ≥ 2.

A

  Real Vector Automaton (RVA, See e.g. [?]) of dimension d is a Büchi automaton A over alphabet {0, . . . , b -1} d ∪ { }, which recognizes the set of encodings in base b of the elements of a set of vectors of reals. Equivalently, for w an infinite word encoding a vector of dimension d of real (r 0 , . . . , r d-1 ), if w is accepted by A, then all encodings w of (r 0 , . . . , r d-1 ) are accepted by A. In the case where the dimension d is 1, those automata are called Real Number Automata (RNA, See e.g. [?]). The sets of tuples of reals whose encoding in base b is recognized by a RVA are called the b-recognizable sets. By [?], they are exactly the FO [IR, IN; +, <, X b , 1]definable sets. The logic FO [IR, IN; +, <, X b , 1] is the first-order logic over reals with a unary predicate which holds over integers, addition, order, the constant one, and the function X b (x, u, k). The function X b (x, u, k) holds if and only if u is equal to some b n with n ∈ Z Z and there exists an encoding in base b of x whose digit in position n is k. That is, u and x are of one of the two following forms: u = 0 . . . 0 0 . . . 0 1 0 . . . x = . . . . . . k . . . or u = 0 . . . 0 1 0 . . . 0 0 . . . x = . . . k . . . . . . . By [?], a set is FO [IR, IN; +, <]-definable if and only if its set of encodings is weakly b-recognizable for all b ≥ 2. By [?], the logic FO [IR; +, <, 1] admits quantifier elimination. By [?, Sect. 6], the set of reals which are FO [IR; +, <, 1]-definable are finite unions of intervals with rational bounds. Those sets are called the simple sets.

  For n ∈ IN, let [n] represent {0, . . . , n}. For a, b ∈ IR with a ≤ b, let [a, b] denote the closed interval {r ∈ IR | a ≤ r ≤ b}, and let (a, b) denote the open interval {r ∈ IR | a < r < b}. Similarly, let (a, b] (respectively

  g. [?]). The rationals are exactly the numbers which admit encodings in base b of the form u vw ω with u, v ∈ Σ * b and w ∈ Σ + b . Rationals of the form nb p , with n ∈ IN and p ∈ Z Z, admit exactly two encodings in base b without leading 0 in the natural part. If p < 0, the two encodings are of the form u va(b -1) ω and u v(a + 1)0 ω , with u, v ∈ Σ * b and a ∈ [b -2]. Otherwise, if p ≥ 0, the two encodings are of the form ua(b -1) q (b -1) ω and u(a + 1)0 q 0 ω with u ∈ Σ * b , a ∈ [b -2] and q ∈ IN. The rationals which are not of the form nb p admit exactly one encoding in base b without leading 0 in the natural part. Encoding of Sets of Reals. Relations between languages and sets of reals are now recalled. Given a language L which is a subset of Σ * b Σ ω b , let [L] R b be the set of reals admitting an encoding in base b in L. The language L is said to be an encoding in base b of the set of reals [L] R b . Reciprocally, given a set R ⊆ IR ≥0 of reals, L b (R) is the set of all encodings in base b of elements of R. For L a subset of Σ ω b , [L] F b is the set of d-tuples of reals, belonging to [0, 1] d , which admits an encoding in base b in L.

Fig. 1 .

 1 Fig. 1. Automaton AR of Ex. ??

Fig. 2 .

 2 Fig. 2. Minimal quotient of automaton AR of Figure ??

Theorem 3 .

 3 Let A = (Q, Σ b ∪{ } , δ, q 0 , F ) be a be a minimal weak RNA with n states which recognizes a simple set. There exists a Σ 1 [IR; +, <, 1]-formula computable in time O n 2 b log(nb) which defines [A] R b . There exists a Σ 2 [IR; +, <, 1]formula computable in time O (nb log(nb)) which defines [A] R b .


Jean-Michel Heraud

Claire Racaud-Sultan

Daisy Gironcel

Corinne Albigès-Rizo

Thierry Giacomini

Séverine Roques

Véronique Martel

Monique Breton-Douillon

Bertrand Perret

Hugues Chap

Corinne Albige `s-Rizo

Se Thierry Giacominiʈ

´verine Roques

Ve ´ronique Martel

Lipid Products of Phosphoinositide 3-Kinase and Phosphatidylinositol 4,5-Bisphosphate Are Both Required for ADP-dependent Platelet Spreading*

Platelets play a key role in hemostasis by their capacities to adhere and to aggregate in response to vascular injury. The most abundant platelet integrin, the ␣ IIb ␤ 3 complex, is largely responsible for platelet aggregation after binding of soluble fibrinogen. Moreover, ␣ IIb ␤ 3 integrin is required for a complete and irreversible platelet adhesion to the subendothelial matrix (1). In this case, its preferential ligand is the von Willebrand factor, but under certain conditions fibrinogen or fibrin could also act as adhesion substrates. In its resting state, ␣ IIb ␤ 3 integrin is able to recognize immobilized fibrinogen. However, the interaction of soluble fibrinogen with ␣ IIb ␤ 3 complex requires a previous conformational change of the integrin due to an inside-out signaling pathway. When platelets adhere in vitro to a fibrinogen matrix, they undergo several irreversible morphological changes such as rounding and spreading. These responses are sustained by a cytoskeletal reorganization including extension of filopodia, lamellipodia, and controlled orientation of stress fibers. It has been shown that a concomitant granular secretion of ADP from adherent platelets was necessary for spreading (2), and that it controlled specific signals, i.e. p125 FAK and PtdIns 3-kinase1 activations (2,3). Data from Haimovich et al. (4) show that tyrosine phosphorylation of p125 FAK tyrosine kinase seems to be correlated with cell spreading upon platelet adhesion to a fibrinogen matrix. On the other hand, PtdIns 3-kinase activity has been involved in cytoskeletal rearrangements occurring during cell motility or platelet aggregation (5)(6)(7)(8)(9). Moreover, studies in whole cells have demonstrated an association of PtdIns 3-kinase with p125 FAK (10,11) and the small G proteins Rac and Cdc42 (12), all of them being involved in the regulation of cytoskeleton organization. Taking advantage of specific PtdIns 3-kinase inhibitors, LY294002 and wortmannin (8,13,14), we herein demonstrate that PtdIns 3-kinase is involved in the ADP-signaling pathway that controls platelet spreading. Nevertheless, our results suggest that PtdIns-4,5-P 2 , a phospholipid tightly associated with actin-binding proteins in focal contacts and a key regulator of actin polymerization (15), could be a downstream messenger of this signaling pathway.

EXPERIMENTAL PROCEDURES

Materials-Human fibrinogen, ADP, human thrombin, phorbol 12myristate 13-acetate (PMA), apyrase, pyruvate kinase, phosphoenolpyruvate, wortmannin, PtdIns-4-P, PtdIns-4,5-P 2 , fatty acid-free bovine serum albumin, and phosphate-buffered saline (PBS) were from Sigma. Lysophosphatidic acid (LPA), the thrombospondin-1 cell binding do-main peptide H-RFYVVMWK-OH, and the TXA 2 analog U46619 used were, respectively, from Sigma, Bachem (Voisins-le Bretonneux, France), and Calbiochem (Meudon, France). LY294002 and GF109203X were obtained, respectively, from Biomol (Plymouth Meeting, PA) and Glaxo (Les Ulis, France). Synthetic Di-C 16 -PtdIns-3,4-P 2 (dipalmitoyl L-␣phosphatidyl-D-myo-inositol 3, 4-bisphosphate) and Di-C 16 -PtdIns-3,4,5-P 3 were purchased from Matreya (Pleasant Gap, PA).

Preparation of Platelets-Human platelets were isolated from fresh platelet concentrates (Centre Re ´gional de Transfusion Sanguine, Toulouse, France) by centrifugation as described previously (16). All washing procedures were performed at 37 °C in the presence of apyrase (1 unit/ml) as an ADP scavenger. In some experiments, platelet-rich plasma was incubated with 100 M aspirin for 20 min to block cyclooxygenase activity. Platelets were labeled for 90 min with 0.4 mCi/ml [␥-32 P]phosphate (Amersham Pharmacia Biotech, Bucks, United Kingdom), as described previously (16). They were finally resuspended in modified Tyrode's buffer (pH 7.4) containing 2.5 mM CaCl 2 .

Cell Adhesion Assays and Lipid Extract Analysis-Cell culture flasks (75 cm 2 , Greiner Labortechnik, Poitiers, France) were precoated or not (control) with 100 g/ml of fibrinogen and were then blocked with fatty acid-free bovine serum albumin (3). The cell adhesion assay was performed using 5 ml of human platelets (3 ϫ 10 7 platelets/ml) that were added for 60 min at 37 °C to the fibrinogen-coated flasks or to the control flasks. In some experiments, the ADP scavenger pyruvate kinase plus phosphoenolpyruvate (14.3 units/ml and 1 mM, respectively; 10 min) or the protein kinase C (PKC) inhibitor GF109203X (12 M; 60 min) or the PtdIns 3-kinase inhibitors LY294002 (0 -25 M; 10 min) or wortmannin (0 -100 nM; 15 min) were added to the platelet suspension before adhesion. GF109203X, wortmannin, and LY294002 were dissolved in Me 2 SO, which did not exceed 0.06% (v/v). Recovering of adherent cells, evaluation of the extent of cell adhesion, and lipid extract analysis by HPLC were performed as described previously (3).

Spreading Restoration Assays-After elimination of unattached platelets and two washes with PBS, adherent wortmannin-treated platelets were incubated with different agonists (20 M ADP, 5 M LPA, 50 M H-RFYVVMWK-OH, 5 M U46619, 10 nM PMA, or 1 unit/ml thrombin) or phosphoinositides (PtdIns-4-P, PtdIns-4,5-P 2 , Di-C 16 -Pt-dIns-3,4-P 2 , Di-C 16 -PtdIns-3,4,5-P 3 , or a mixture of these lipids, 10 -30 M) in Tyrode's buffer for 30 min at 37 °C. Before use, phosphoinositides were dried, suspended in 10 mM Hepes (pH 7.0), and sonicated in the absence of carrier phospholipids.

Optical Microscopy-At the end of the adhesion step or the spreading restoration assay, unattached platelets were removed by washing with PBS and the buffer was replaced by 1% glutaraldehyde in 0.1 M Na 2 HPO 4 . Fixation was continued at room temperature for 15 min. After washing, adherent platelets were examined by interference light microscopy with a Reichert EMF4 microscope. Micrographs were taken at original magnification ϫ1250.

Immunoprecipitation of Talin-Adherent platelets (4.5 ϫ 10 8 platelets) were scraped off at 4 °C in a lysis buffer containing 20 mM Tris-HCl, pH 8, 137 mM NaCl, 10% glycerol, 1 mM Na 3 VO 4 , 1 mM PMSF, 10 M pepstatin, 10 g/ml leupeptin, and 1% (v/v) Triton X-100. Resting platelets in suspension (4.5 ϫ 10 8 platelets) were centrifuged and resuspended in 600 l of the lysis buffer. After sonication (20 kHz for 2 ϫ 10 s) and centrifugation (12,000 ϫ g for 10 min at 4 °C), the soluble fraction was collected and subsequently precleared for 30 min at 4 °C with protein G-Sepharose 4B fast flow (Sigma). Precleared suspensions were then incubated overnight at 4 °C with the polyclonal anti-talin antibody prepared as described previously at a 1:50 dilution (17). Capture of immune complex was performed by adding 50 l of protein G-Sepharose 4B fast flow. The immunoprecipitates were then washed once with PBS without calcium and magnesium, supplemented with anti-proteases as described above and 0.1% (v/v) Triton X-100, and twice with the same buffer without Triton.

Lipid Extraction and Western Blotting on Talin Immunoprecipitates-For lipid analysis, immunoprecipitation of talin was performed after plating of 32 P-labeled platelets as described above. Lipids were extracted as described previously (3) and separated by TLC following the procedure established by Pignataro and Ascoli (18). Briefly, lipid extracts were applied on oxalate-EDTA-impregnated silica gel plates, which were developed twice for 120 min with CHCl 3 , CH 3 OH, 9.15 M NH 4 OH (40:40:15). Individual lanes containing commercial standards PtdIns-4-P or PtdIns-4,5-P 2 were stained with iodine vapors. After exposition of the plates for 3-7 days, the radioactive spots were visualized and quantitated by a PhosphorImager 445 SI (Molecular Dynamics, Inc). Quantification was also performed after scraping the appropriate areas of the plate and counting in a liquid scintillation counter.

For protein analysis, anti-talin immunoprecipitates were solubilized, separated on 7.5% SDS-polyacrylamide gels, and blotted onto nitrocellulose as described previously (11). Immunodetection of talin was performed with the mouse monoclonal anti-talin antibody 8d4 from Sigma. Antibody reaction was visualized using the ECL chemiluminescence system (Amersham Pharmacia Biotech). Quantification of the different bands was performed by a densitometric analysis, which determines the pixel volume in each area (Gel Doc 1000, Bio-Rad).

RESULTS

Wortmannin and LY294002 Inhibit PtdIns-3,4-P 2 Synthesis Triggered upon Platelet Adhesion-Wortmannin and LY294002 have been largely used in platelets as specific inhibitors of PtdIns 3-kinase, at nanomolar (10 -100 nM) and micromolar (25 M) concentrations, respectively (8,9,19,20). Since we have shown previously that platelet adhesion triggers accumulation of [ 32 P]PtdIns-3,4-P 2 (3), we first assessed the inhibitory effects of wortmannin and LY294002 on the production of [ 32 P]PtdIns-3,4-P 2 as a reflection of PtdIns 3-kinase activation. 32 P-Labeled platelets were preincubated with increasing doses of wortmannin or LY294002, and cells were then plated for 60 min on the fibrinogen matrix before lipid extraction and analysis by HPLC. As shown in Fig. 1, LY294002 and wortmannin inhibited [ 32 P]PtdIns-3,4-P 2 synthesis in a dose-de- pendent manner with 80% inhibition achieved at 12 M and 50 nM, respectively. The production of [ 32 P]PtdIns-3,4-P 2 was totally abrogated at 25 M LY294002 and 100 nM wortmannin, at which concentrations platelet adhesion was not significantly affected (Table I). At these concentrations, among other phosphoinositides (PtdIns, PtdOH, PtdIns-4-P, and PtdIns-4,5-P 2 ), only the PtdIns-4-P level was found to be somewhat decreased, but not significantly in comparison with control Me 2 SO-treated platelets (Fig. 2).

PtdIns 3-Kinase Activation Is Necessary for ADP-dependent Platelet Spreading-As described previously (21), upon adhesion, adherent platelets undergo the following steps of morphological changes: disk to sphere shape change, extension of pseudopodia, and a much slower process, cell spreading (Fig. 3, A andB). Pretreatment of platelets with wortmannin or LY294002 inhibited platelet spreading on fibrinogen (Fig. 3, C andD). However, it should be noted that, although pretreated platelets did not fully spread, they still extended pseudopodia. The inhibitory effect of LY294002 and wortmannin on cell spreading was already detectable at 6 M and 25 nM, respectively. Concentrations of 25 M LY294002 and 100 nM wortmannin completely prevented platelet spreading. After removing wortmannin and LY294002 from the adhesion medium by two washes, we observed that only the inhibitory effect of LY294002 was reversible after 30 min (data not shown). Indeed, LY294002 is a competitive inhibitor at the ATP-binding site of PtdIns 3-kinase (13), whereas wortmannin induces a covalent modification of the catalytic site of the enzyme (14). In agreement with Haimovich et al. (2,4), pretreatment of platelets with the ADP scavenger pyruvate kinase plus phosphoenolpyruvate just before the adhesion assay induced the same effects as treatment with the PtdIns 3-kinase inhibitors, i.e. absence of spreading but persistence of pseudopodal extension (Fig. 3E). After washing, ADP (20 M) was added to adherent platelets to overcome the ADP scavenging system. Addition of ADP restored full spreading of all adherent platelets as shown in Fig. 3F. On the other hand, addition of 20 M ADP to adherent platelets pretreated with wortmannin did not reverse inhibition of platelet spreading (Fig. 3G). These data demonstrate that PtdIns 3-kinase signaling pathway is required for ADP-induced spreading of adherent platelets.

PtdIns-4,5-P 2 but Not Lipid Products of PtdIns 3-Kinase Is Sufficient for a Full Platelet Spreading-Our previous measurements of PtdIns 3-kinase activation in adherent platelets (3) have shown that, although the PtdIns-3,4,5-P 3 level was not significantly modified between 5 and 30 min of adhesion, Pt-dIns-3,4-P 2 accumulated as a function of the adhesion time. Time course of PtdIns-3,4-P 2 production closely paralleled platelet spreading upon adhesion (data not shown). In order to determine whether products of PtdIns 3-kinase could be involved in platelet spreading, we used Di-C 16 -PtdIns-3,4-P 2 and Di-C 16 -PtdIns-3,4,5-P 3 , which were reported to trigger biologic responses when added to whole cells (7,22). As shown in Fig. 4A, addition of Di-C 16 -PtdIns-3,4-P 2 (20 M) on adherent platelets pretreated with wortmannin only partially restored platelet spreading. After 30 min of incubation with Di-C 16 -PtdIns-3,4-P 2 , some adherent platelets have lost their round shape and have undergone pseudopodal and hyalomere extension. Nevertheless, these modifications concerned only a small proportion of adherent platelets (5%), as compared with 35% of spread platelets obtained with non-pretreated control cells (Fig. 4B). Using amounts of Di-C 16 -PtdIns-3,4-P 2 between 10 and 30 M, we obtained a dose-dependent increase in the response rate (detected as early as 15 min of adhesion) and in the proportion of responsive cells (Fig. 4B). In no case did we observe a full spreading of platelets, even after 60 min of incubation. Addition of Di-C 16 -PtdIns-3,4,5-P 3 or PtdIns-4-P or both (data not shown) together with Di-C 16 -PtdIns-3,4-P 2 was not more efficient in restoring full spreading (Fig. 4B). Surprisingly, addition of PtdIns-4,5-P 2 to adherent platelets pretreated with wortmannin triggered full spreading (Fig. 4, A andB). Moreover, the number of fully spread platelets was increased by addition of both Di-C 16 -PtdIns-3,4-P 2 and PtdIns-4,5-P 2 (Fig. 4B). Nevertheless, under these conditions, the amount of fully spread platelets was far below that observed in the control situation. PtdIns-4,5-P 2 effects on cell spreading are unlikely to be dependent on induction of platelet release reaction, as ADP (20 M), LPA (5 M), the thrombospondin-1 cell binding domain peptide (H-RFYVVMWK-OH; 50 M), could not restore spreading of platelets treated with 100 nM wortmannin (Table II). By contrast, the TXA 2 analog U46619 (5 M) triggered full spreading of adherent platelets pretreated with 100 nM wortmannin. However, addition of PtdIns-4,5-P 2 (20 M) to adherent platelets pretreated with aspirin (100 M) and wortmannin (100 nM) was still able to restore full platelet spreading (Table II).

The fact that strong platelet agonists, such as thrombin (1 unit/ml), the TXA 2 analog U46619, and the PKC activator PMA (10 nM), were able to restore spreading of platelets pretreated with 100 nM wortmannin (Table II) might suggest a PtdIns 3-kinase-independent pathway of platelet spreading. In order to determine a possible activation of PKC isoforms by high concentrations of PtdIns-4,5-P 2 (23), we used the specific PKC inhibitor GF109203X (24). Preincubation of platelets with GF109203X (12 M) induced inhibition of platelet spreading as described previously by Haimovich and co-workers (4). When platelets had been pretreated by both GF109203X (12 M) and wortmannin (100 nM) together, exogenous PtdIns-4,5-P 2 was still able to restore full spreading of adherent platelets with a similar efficiency as in the case of a pretreatment with wortmannin alone (Table II). These experiments argue in favor of a specific PtdIns-4,5-P 2 effect on the restoration of cell spreading that is independent on PKC activation. FIG. 3. Effects of wortmannin, LY294002, and ADP on platelet spreading. Platelets were incubated in absence (A) or presence of Me 2 SO (0.03%; B), wortmannin (100 nM; C and G), LY294002 (25 M; D) as described previously in the legend to Fig. 2. In some experiments, the ADP scavenger pyruvate kinase plus phosphoenolpyruvate was added to the platelet suspension before adhesion (E and F) as described under "Experimental Procedures." Adhesion was performed for 60 min, and after two washes, ADP (20 M) was added to the adherent platelets for 30 min (F and G). After fixation, adherent cells were observed by interference light microscopy.

FIG. 4. Effects of different phosphoinositides on spreading of platelets pretreated with wortmannin.

A, platelets were incubated in presence of 0.03% Me 2 SO (A) or 100 nM wortmannin (W, PtdIns-3,4-P 2 , PtdIns-4,5-P 2 ) as described previously in the legend to Fig. 2. Adhesion was performed for 60 min and after two washes, Di-C 16 -PtdIns-3,4-P 2 or PtdIns-4,5-P 2 (20 M) was added to the adherent platelets for 30 min as described under "Experimental Procedures." After fixation, adherent cells were observed by interference light microscopy. Platelets in a fully spread stage are indicated by large arrowheads, whereas those in a partial spread stage are indicated by thin arrowheads. B, different lipids were prepared and added to adherent platelets pretreated with wortmannin (W) as described under "Experimental Procedures." Adherent platelets pretreated with 0.03% Me 2 SO (A) were taken as a control. The histogram was used to express the percentages of platelets in a partial spread stage (black box) or in a full spread stage (hatched box). One hundred randomly chosen platelets were counted from each experiment (n ϭ 2-6), and each experiment has a paired control.

The partial rescue of platelet spreading with lipids suggests that there may be additional components to the PtdIns 3-kinasedependent pathway. We addressed the possibility that the myosin light chain kinase (MLCK) could be involved in platelet spreading. Indeed, inhibitors of MLCK have been shown to disassemble focal adhesions and to reduce their phosphotyrosine staining (25), and wortmannin is a MLCK inhibitor, but at micromolar concentrations (26). Preincubation of platelets with 10 M ML-7 (specific inhibitor of MLCK from Biomol; Ref. 27) during the 30 min before adhesion did not modify platelet spreading (data not shown). We concluded that MLCK does not seem to be involved in platelet spreading.

In Vivo Association of PtdIns-4,5-P 2 with Talin Is Decreased upon Wortmannin Treatment-Since the level of [ 32 P]PtdIns-4,5-P 2 was not significantly modified in vivo upon treatment of platelets with wortmannin, we looked for possible changes of the lipid content of focal adhesion sites. Talin is a prominent actin-binding protein that links integrins and the cytoskeleton and has been shown to be required for cell spreading (28,29). Although some variations could be observed in the amount of talin immunoprecipitated from platelets (Fig. 5A), mean values obtained from two experiments were essentially the same (Fig. 5B). Under these conditions, only traces of PtdIns-4-P were recovered in anti-talin immunoprecipitates from resting platelets, whereas, after adhesion, the amount of PtdIns-4-P increased, PtdIns-4,5-P 2 and traces of PtdIns-3,4-P 2 becoming detectable (Fig. 5C). For instance, the amount of talin isolated from activated platelets was 1.4-and 0.9-fold (two experiments) the amount obtained from control platelets, whereas associated phospholipids were increased by 7.5-and 11-fold, respectively. This indicated that adhesion promoted specific association of phosphoinositides with talin. Moreover, by comparison with the relative amounts of polyphosphoinositides found in total platelets, there was an enrichment in PtdIns-4-P and PtdIns-3,4-P 2 in the anti-talin immunoprecipitates (compare Figs. 2 and5D). Treatment of platelets with wortmannin induced a strong decrease (60 -100%) of these three lipids associated with talin (Fig. 5, C andD). Thus, we conclude that PtdIns 3-kinase inhibitors may modify the association of PtdIns-4,5-P 2 with talin and therefore influence its possible function in platelet spreading.

DISCUSSION

We have shown previously that synthesis of PtdIns-3,4-P 2 in adherent platelets is under the control of the released ADP, since addition of ADP reversed the inhibitory effects of an ADP FIG. 5. Effects of wortmannin treatment on association of polyphosphoinositides with talin in vivo. Platelets were labeled with [ 32 P]orthophosphate (C and D) or not (A and B) and plated on the fibrinogen matrix (A, W) or kept in suspension (C) for 60 min as described in the experimental procedure. In some cases, platelets were pretreated with 100 nM wortmannin before plating (W). There was no detectable difference in the amount of lipid-incorporated 32 P between the adherent and suspended samples. Immunoprecipitation of talin from 4.5 ϫ 10 8 platelets was performed with a polyclonal anti-talin antibody followed by Western blotting (A), and lipids were extracted and separated by TLC (C) as described under "Experimental Procedures." No lipid was precipitated by protein G-Sepharose alone. Quantification of the amounts of talin immunoprecipitated was performed by a densitometric analysis (B), and the lipid content (D) is expressed taking the amount of PtdIns-4-P in assay A as 100% (74 cpm). B and D are means from two independent experiments.

TABLE II

Spreading restoration of wortmannin-treated platelets by different agonists Platelets were incubated with wortmannin (100 nM; 15 min) and/or GF 109203X (12 M; 60 min) and then plated on the fibrinogen matrix for 60 min. In some experiments, platelet-rich plasma was incubated with 100 M aspirin. Spreading restoration assays were performed by addition of 20 M ADP, 5 M LPA, 50 M H-RFYVVMWK-OH, 1 unit/ml thrombin (THR), 5 M U46619, 10 nM PMA, or 20 M PtdIns-4,5-P 2 as described under "Experimental Procedures." After 30 min, efficiency in full spreading restoration was observed by microscopy and was expressed as follows: percentage of adherent platelets in a full spread state (100%) (ϩϩϩϩ), 50% (ϩϩ), 10% (ϩ), or 0% (Ϫ). scavenger on PtdIns-3,4-P 2 synthesis (3). Our present results, in agreement with those of Haimovich et al. (2,4), demonstrate that ADP release occurring upon platelet adhesion is required for full platelet spreading. Thus, ADP released by adherent platelets controls both PtdIns-3,4-P 2 synthesis and cell spreading. In conditions where PtdIns-3,4-P 2 synthesis was totally abolished by inhibitors of PtdIns 3-kinase, we observed an inhibition of platelet spreading while pseudopodal extension was maintained. We demonstrate here that the PtdIns 3-kinase signaling pathway is required for ADP-induced spreading of adherent platelets.

In order to determine which lipid is responsible for platelet spreading, we have added synthetic PtdIns-3,4-P 2 and PtdIns-3,4,5-P 3 to adherent wortmannin-treated platelets. PtdIns-3,4-P 2 appears to be the most efficient in restoring partial spreading, i.e. pseudopodal and hyalomere extension. However, among all phosphoinositides tested, PtdIns-4,5-P 2 alone was able to trigger the full spreading of wortmannin-treated platelets. Although all phospholipid solutions were prepared under similar conditions, their packing into micelles or vesicules was not characterized. Moreover, differences in the acyl chains of PtdIns-3,4-P 2 (palmitate) and PtdIns-4,5-P 2 (stearate and arachidonate) may have influenced their activity. Nevertheless, our results suggest a role for both PtdIns-4,5-P 2 and lipid products of PtdIns 3-kinase in the signal transduction pathway leading to platelet spreading.

We have observed a trend toward a decrease of [ 32 P]PtdIns-4-P in adherent platelets pretreated with PtdIns 3-kinase inhibitors. This result suggests that a wortmannin-sensitive Pt-dIns 4-kinase might exist in platelets, as has been shown in other models (30,31). Nevertheless, in a cell system, wortmannin was reported to inhibit PtdIns 4-kinase at M concentration, and LY294002 has not been described as an inhibitor of known PtdIns 4-kinases (13). Thus, PtdIns 3-kinase activity could be upstream of a PtdIns 4-kinase and/or a PtdIns-4-P phosphatase. Finally, even though we have not measured a significant decrease of [ 32 P]PtdIns-4,5-P 2 in whole platelets pretreated with PtdIns 3-kinase inhibitors, a decrease of Pt-dIns-4-P level could impair the synthesis of a particular pool of PtdIns-4,5-P 2 required for platelet spreading.

Recent studies from the Schlessinger and Rhee laboratories (32,33) demonstrate that ␥ isoforms of phospholipase C (PLC) could be activated by PtdIns-3,4,5-P 3 , either by targeting to cell membrane through their PH domain or by direct activation through their SH2 domain. One could thus expect an increase of PtdIns-4,5-P 2 level when adherent platelets have been pretreated with PtdIns 3-kinase inhibitors. Nevertheless, at least two reasons could explain why in our experiments this variation is not observed. First, in our previous paper (3), we have shown that upon platelet adhesion on a fibrinogen matrix a PLC active on PtdIns-4,5-P 2 was rapidly and transiently stimulated. Maximal increase of PtdOH production and PtdIns-4,5-P 2 decrease was observed as early as 5 min of adhesion. Thereafter, these two metabolites returned gradually to their basal level, and that corroborates the absence of PtdOH and PtdIns-4,5-P 2 variations after 60 min of adhesion, as shown in Fig. 2 of our present article. We thus believe that in the late steps of platelet adhesion PLC activity is not involved. However, it should be of importance to check PLC activity during the early steps of adhesion of platelets treated with PtdIns 3-kinase inhibitors. Second, since our present data show a decrease of PtdIns-4-P level upon platelet treatment with Pt-dIns 3-kinase inhibitors, an eventual increase of the PtdIns-4,5-P 2 level might be impaired.

PtdIns-4,5-P 2 regulates several actin-binding proteins as profilin, gelsolin, ␣-actinin, and vinculin (34). One of the major proteins of focal adhesions, talin, has been shown to be involved in cell spreading (28,29). Its interaction with lipids has been documented in vitro and could be of importance for talin nucleated actin polymerization (34). Here, we show that PtdIns-4,5-P 2 as well as PtdIns-4-P and PtdIns-3,4-P 2 become associated with talin upon platelet adhesion. Moreover, treatment of platelets by wortmannin strongly reduces the amounts of polyphosphoinositides recovered in the anti-talin immunoprecipitate. Even though it remains to be determined whether this association is direct or not, our results support the notion of a possible regulation by PtdIns 3-kinase of a pool of PtdIns-4,5-P 2 potentially involved in cell spreading.

Hartwig et al. (35) have reported that D3 and D4 polyphosphoinositides uncap F-actin in resting permeabilized platelets. At low concentrations (10 M), PtdIns-4,5-P 2 and PtdIns-3,4-P 2 are more effective than PtdIns-3,4,5-P 3 . Synthesis of PtdIns-4-P and PtdIns-4,5-P 2 , which are correlated with the exposure of barbed filament ends, seem to be under the control of the small G protein Rac (35). This small G protein has been shown to regulate extension of peripheral lamellipodia (36), to associate in vivo with both PtdIns 3-kinase and PtdIns-4-P 5-kinase (12), and it was suggested that PtdIns 3-kinase functions upstream of Rac (37,38). Moreover, PtdIns-4,5-P 2 and PtdIns-3,4-P 2 both regulate, in vitro, the severing and capping of the protein gelsolin (9), whose genetic defect is responsible for the absence of lamellae although the filopod formation is maintained, upon platelet activation (39). Thus, in our model, Pt-dIns 3-kinase could regulate actin remodeling directly through PtdIns-3,4-P 2 synthesis and/or indirectly through PtdIns-4,5-P 2 synthesis.

Recent results from King et al. (40), showing that spreading of COS 7 cells attached to fibronectin is delayed after treatment by wortmannin and LY294002, support the view that the Pt-dIns 3-kinase signaling pathway is required for cell spreading, as controlled by integrins and/or by tyrosine kinase receptors (41). It has been suggested that ADP released from adherent platelets supports some specific signals such as Vav phosphorylation via an indirect mechanism involving activation of ␣ IIb ␤ 3 (42). Furthermore, an integrin-associated protein agonist peptide triggers activation of ␣ IIb ␤ 3 integrin resulting in platelet spreading on immobilized fibrinogen (43). Thus, upon platelet adhesion to immobilized fibrinogen, it remains to be clarified whether platelet spreading is secondary to the ␣ IIb ␤ 3 integrin engagement.

FIG. 1 .

 1 FIG. 1. Dose-dependent inhibition of adhesion-induced [32P]-PtdIns-3,4-P 2 synthesis by wortmannin and LY294002. Washed platelets were pretreated with wortmannin (15 min) or LY294002 (10 min) at different concentrations and then were plated on the fibrinogen matrix for 60 min. After washing, adherent cells were scraped off and their lipid extract was analyzed by HPLC after deacylation. [ 32 P]PtdIns-3,4-P 2 was quantified as described under "Experimental Procedures."

FIG. 2 .

 2 FIG. 2. Effects of wortmannin and LY294002 on 32 P labeling of various phospholipids from resting and adherent platelets. Washed platelets were pretreated in absence (A) or presence of wortmannin (100 nM; 15 min), LY294002 (25 M; 10 min), or Me 2 SO (vehicle; 0.03%; 15 min) and were plated on the fibrinogen matrix for 60 min. Control resting platelets (C) were added to a flask without fibrinogen. Control and adherent platelets were then recovered, and their lipid extracts were analyzed by HPLC after deacylation as described under "Experimental Procedures." 32 P radioactivity incorporated into various phosphoinositides is expressed in counts/min from 3 ϫ 10 8 platelets, and data are means Ϯ S.E. from three independent experiments. Radioactivity of [ 32 P]PtdIns-3,4-P 2 was undetectable in samples of non-adherent platelets or platelets treated with PtdIns 3-kinase inhibitors and is not represented.

The abbreviations used are: PtdIns 3-kinase, phosphoinositide 3-kinase; PtdIns, phosphatidylinositol; PtdIns-4-P, phosphatidylinositol 4Јphosphate; PtdIns-3,4

-P 2 ,

phosphatidylinositol 3Ј,4Ј-bisphosphate; Pt-dIns-4,5-P 2 , phosphatidylinositol 4Ј,5Ј-bisphosphate; PtdIns-3,4,5-P 3 , phosphatidylinositol 3Ј,4Ј,5Ј-trisphosphate;PtdOH, phosphatidic acid; LPA, lysophosphatidic acid; PLC, phosphatidylinositol-specific phospholipase C; PKC, protein kinase C; MLCK, myosin light chain kinase; PMA, phorbol 12-myristate 13-acetate; PBS, phosphate-buffered saline; HPLC, high pressure liquid chromatography; TXA 2 , thromboxane A 2 ; Di-C 16 , dipalmitoyl.

Vol. 273, No. 28, Issue of July 10, pp. 17817-17823, 1998 © 1998 by The American Society for Biochemistry and Molecular Biology, Inc. Printed in U.S.A.This paper is available on line at http://www.jbc.org

by guest on December 15, 2017 http://www.jbc.org/ Downloaded from

Acknowledgments-We thank Dr. B. Payrastre and D. Bacqueville for helpful discussions.

* This work was supported in part by the Association pour la Recherche sur le Cancer, Paris, and the Conseil Re ´gional Midi-Pyre ´ne ´es, Toulouse, France.


Xavier Ribeyre
email: ribeyre@celia.u-bordeaux1.fr

Vladimir Tikhonchuk

HIGH FREQUENCY GRAVITATIONAL WAVES GENERATION IN LASER PLASMA INTERACTION

Keywords:

Estimates of the emitted power and the metric perturbation of the gravitational waves generated in laser plasma interaction are performed. The expected intensities are too low to be detected with the present day instruments.

Introduction

Existence of gravitational waves is postulated in the theory of general relativity by Einstein, 1 but no direct detection of such waves has been made so far. The best evidence of their existence is due to the work of 1993 Nobel laureates Taylor and Hulse. 2 The search for gravitational waves (GW) radiated by extraterrestrial sources is carried out by large gravitational interferometer detectors LIGO and VIRGO. 3 These detectors address the low frequency spectral band between 10 Hz and 10 kHz. Recently, astrophysical sources of high frequency gravitational waves (HFGW: ν > 100 kHz) were considered and this renew an interest for a GW Hertz experiment, 4 which consists in generation and receiving the GW signal on Earth. One of the first considerations of the gravitational Hertz experiment in laboratory was done by Weber 5 in a low frequency domain. In the high frequency domain the possibilities of GW generation in laboratory were considered by Rudenko 4 and by Chapline. 6 In particular, Rudenko proposed a GW Hertz experiment associated with high power electromagnetic waves and acoustic impulsive or shock waves travelling and interacting with a non-linear opto-acoustic medium.

GW generation with lasers

The GW emission is proportional to that the third time derivative of the quadrupolar mass momentum Q(t) is no zero. The power emitted by a local source of GW writes: P GW G ... Q 2 /5c 5 and the metric perturbation h GW is given by

h GW G Q/Rc 4
, where G, c are the gravitational and light celerity constants and R is the distance between the GW generator and the detector.

As lasers actually are the most powerful sources of electromagnetic energy on earth, we present here analytical estimates and numerical simulations of generation of the HFGW in interaction of high power laser pulse with a medium in different geometries. First, during the laser plasma interaction, a strong shock driven by the ablation pressure is generated in the bulk material. In this configuration, material is accelerated in the shock front and in the ablation zone. Because of a short laser pulse duration (ns) GW are generated in the GHz domain. During the laser interaction with a planar thick foil (more than 100µm thickness) the laser launch a shock with a velocity V s , this shock accelerates the medium along the z axis and produces a quadrupolar mass momentum Q zz . The time dependence of the quadrupolar mass momentum in shock is

Q zz = Sρ 0 V 3 s t 3
, where S is the surface of laser focal spot. The shock velocity V s P s /ρ 0 depends on the ablation pressure P s and the material density ρ 0 . Moreover, P s is directly connected to the laser intensity I L as: P s 112(I L ) 2/3 (for the laser wavelength 0.35 µm), where I L is in PW/cm 2 and P s in Mbar. [START_REF] Atzeni | Physics of the Inertial Fusion[END_REF] With these relations the radiated GW power reads: P GW [erg/s] 7 × 10 -18 P 2 L /ρ 0 and h GW 3 × 10 -37 E L /R √ ρ 0 , where, P L the laser power is in PW, ρ in g/cc, E L is the laser energy in MJ and R in cm. For achievable laser parameters: P L = 0.5 PW, ρ = 30 mg/cc (foam material) and E L = 0.5 MJ, we have P GW 6 × 10 -17 erg/s and h GW 10 -39 for the detection distance of R = 10 m (we believe that a distance of a few meters is needed to protect the detector from strong broadband electromagnetic perturbations created in laser interactions).

In the case of GW generation in the laser ablation zone, the rarefaction wave propagates with the sound velocity C s P L /ρ 0 . The expression for Q zz is similar to the shock wave problem, and C s have the same magnitude as V s . Hence, P GW and h GW have the values that are similar to the shock wave GW generation problem. In the laser matter interaction, the GW in the shock wave and in the rarefaction wave are produced at the same time and in the same space region. Then we can add these two contributions having, P GW 10 -16 erg/s and h GW 4 × 10 -40 .

Another GW source is a thin foil accelerated by a high ablation pressure produced by the laser heating and ablation. [START_REF] Atzeni | Physics of the Inertial Fusion[END_REF] In this case, the quadrupolar mass momentum writes: Q zz (t) M z 2 , where M is the initial mass foil. We can assume that the mass ablated during the laser interaction is negligible, then the GW emitted power writes: P GW GM 2 ( ż z) 2 /5c 5 and h GW GM ż2 /c 4 R. With a high energy laser of a MJ class a velocity ż 300 km/s is achievable in 2 ns for a foil mass about 2 mg. Then, P GW 5 × 10 -19 erg/s and h GW 1.5 × 10 -40 with R = 10 m.

HFGW could be produced with high power laser facilities dedicated to the inertial confinement fusion like the National Ignition Facility (NIF, USA), the Laser Megajoule (LMJ, France), or the European project for the inertial fusion energy HiPER. [START_REF] Ribeyre | [END_REF] The laser driven implosion fusion can radiate HFGWs if the implosion of cryogenic deuterium-tritium (DT) micro-sphere would be asymmetric and produce a quadrupolar momentum Q zz . In the case, Q zz M z 2 , where represents the non-symmetric part of the explosion. Such an asymmetric DT can be created by launching a bipolar shock. [START_REF] Ribeyre | [END_REF] With this ignition scheme the asymmetry 0.2 is achievable. The laser Megajoule can implode a mass around 0.2 mg, with a velocity ż around 3 × 10 8 cm/s. The time scale of the explosion is around 20 ps. With these parameters, we have P GW 2 × 10 -14 erg/s and h GW 3 × 10 -39 with R = 10 m. The fusion reactions produce in the central DT core high velocity jets, which radiate HFGW in 50 GHz domain during the plasma expansion of less than 100 ps. Another possibility to generate GWs in the THz domain would be to use a high intensity picosecond laser pulse. 9 A circular polarized pulse with intensity I L 10 21 W/cm 2 pushes a matter via the ponderomotive forceit it accelerates to the velocity V p = I L /cρ 0 , which could be of the order of 10 9 cm/s or more. The radiated power reads:

P GW 5 × 10 -25 P 3 L /ρ 0 Φ 2 [erg/s],
where Φ is the laser focal spot diameter (in cm) and P L in PW. Moreover, the metric perturbation writes: h GW 8 × 10 -40 P L τ L /R, where P L is in PW and τ L in ps. A power about 7 PW during 1 ps, with a focal spot about 30 µm on a plastic target (ρ 0 = 1 g/cc), will be achievable on PetaWatt Class laser facilities (PETAL, NIF-ARC). With these parameters: P GW 2 × 10 -17 erg/s and h GW 6 × 10 -42 for a detection at the distance of 10 m.

Conclusion

Although all considered schemes have quite different geometries sizes and time scales, the generated GW powers and metric perturbations are not much different. This follows created by the observation that h GW from a point-like source can be estimated as GE/Rc 4 , where E is the available energy. With the maximum laser energy available today of 1 MJ, h GW cannot be larger at the distance of few metters than 10 -39 . The noise detection level (h GW ) min 10 -30 given in Ref. 4 is many order of magnitude higher. We conclude that available today laser sources are insufficient to generate HFGW on a detectable level. The limitation that we found for the point-like sources (with the size of the order of the emission wavelength) apply also to the sources of a larger size that might use interference effects to collimate emission in a certain solid angle. Although this may increase the intensity at the detector by one or two orders of magnitude, this do not affect the total emission power, which is still far away from the detection threshold.