F Radjai

D Wolf

S Roux

M Jean

J J Moreau

FORCE NETWORKS IN GRANULAR PACKINGS

We used a Contact Dynamics algorithnt to investigate some of the statistical properties of the contact network in quasistatically driven assemblies of rigid particles containing from 500 to 4000 particles in two dimensions. We found that the contact network at every stage of deformation is composed of two complementary subnetworks: a "strong" percolating subnetwork of the contacts carrying a force larger than the mean force ( containing about 40% of contacts), and a "weak" subnetwork of the contacts carrying a force lower than the mean force. In the strong subnetwork, all contacts are nonsliding and the probability distribution of forces is well fitted by an exponential decay. Almost the whole dissipation takes place inside the weak subnetwork, where the number of forces decays as a power law. The weak subnetwork contributes only to the mean pressure (about 25%), whereas the strong subnetwork takes over the whole deviatoric load. The strong subnetwork bears the primary anisotropy induced by shear with the same orientation as the stress tensor, but it gives rise to a secondary anisotropy inside the weak subnetwork with an orientation orthogonal to that of the stress tensor.

Introduction

Photoelastic visualizations provide a direct evidence for the heterogeneous distri bution of contact forces in dense granular systems (see Fig. 1), 1 with the following qualitative features: l. Contact-to-contact fluctuations over several orders of magnitude, 2. Correlations on a scale far larger than the particle size, 3. Rapid reorganization during deformation. Micromechanical modeling of granular materials in the dense regime involves a quantitative characterization of both statistical distributions and spatio-temporal correlations of internai variables on the scale of these heterogeneities. [START_REF] Jaeger | [END_REF] The necessity of considering such a detailed microscopie study has been frequently observed since Coulomb, who introduced the first phenomenological concepts in the field. [START_REF] De Coulomb | Mémoires de mathématiques et de physique[END_REF] Recently, a significant effort has been made in this direction through experiments;4• 5 , 6 , 7 nu merical simulations�• 9 • 10 , 11 and theoretical modeling. 1 2 • 13 • 14 • 15 This effort isjustified regarding the fact that the statistical distributions of internai mechanical variables are quite large. [START_REF] Radjai | [END_REF] This means that the mean quantities, commonly used to mode! the quasistatic deformation of granular media, provide only a marginal information.

In this paper, on the basis of numerical results from simulations of a few thou sands of particles in two dimensions, we show that the organization of these variables has a basic bimodal character, which is also reflected in the structure of the stress tensor. We will first briefl.y introduce the simulation method. Then, we will focus successively on force distributions, stress tensor, induced anisotropy, and dissipa tion.

Simulation method

A numerical simulation of a densely-packed system has to tackle a multicontact problem. Every collision in such a medium is a multiple collision that cannot be reduced to a set of independent binary collisions since impulsions propagate through the contact network and may even leave the system. In the same way, the frictional resistance to shear is a collective phenomenon involving the mobilization of friction at kinematically correlated contacts. Another basic problem is that the contact laws are strongly nonlinear. In the approximation of perfectly rigid particles, the normal force at a contact is not given locally as a fonction of the relative displacement of two particles, but rather as a result of the global geometrical configuration of the whole system and the boundary conditions. Furthermore, the basic Coulomb's law of friction is nonsmooth in the sense that the relation between the relative tangential velocity and the friction force cannot be represented as a mathematical fonction. The Contact Dynamics (CD) method, which was used for the investigations reported in this paper, takes these features into account on a mathematical ha.sis derived from Convex Analysis. 16 • 17 On one hand, the conditions of perfect rigidity and exact Coulombian friction are implemented with no resort to any regularization. On the other hand, all kinematic constraints are simultaneously taken into account, together with the equations of dynamics, in order to determine contact forces and particle velocities in the system. The method is thus able to deal properly with the nonlocal character of the momentum transfers in the contact network. Let us underline here the point t.hat dynamics is an essential ingredient of this approach. It is well known that a granular system at static equilibrium is hyperstatic, i.e. for given boundary conditions there is a continuous set of possible contact forces. This is due both to the absence of an internai displacement field (because of perfect rigidity) and to the nonsmooth char acter of the friction Jaw . [START_REF] Radjai | [END_REF] In the CD method, the force network at static equilibrium is determined through the dynamic processes from which it relaxed. In other words, like in real granular systems, the static values of forces are reached asymptotically as the kinematic energy of the system is dissipated in friction and collisions.

Force distributions

Let us begin with the probability distribution PN of normal forces N independently of contact orientations. Numerical results will be presented here for three samples of 4012, 4025, and 4098 particles, referred to as samples A, B, and C. Particles are contained in a rectangular frame composed of two horizontal and two vertical rigid walls. Sample A is biaxially compressed by allowing the inward motion of a horizontal wall and by applying a confining Joad on a vertical wall free to move horizontally. Sample Bi s in relaxation towards static equilibrium under a confining load applied to a free wall. Sample C is in static equilibrium under confining loads.

The acceleration of gravity and the particle-wall coefficients of friction are set to zero. The interparticle coefficient of friction is 0.5 in samples A and C, and 0.2 in sample B. In ail samples, the particle radii are uniformly distributed between 3.8 and 7.5 mm. (1)

Within the statistical precision, the values of exponents a and /3 depend only weakly on the mechanical parameters and the preparation conditions of each sample. In static equilibrium or in quasistatic deformation, the value of a is very close to zero. However, it seems that a increases with the degree of dynamics inside the system and decreases with the coordination number. Let us also remark that, since the mean value (N) separates the two parts of the distribution, a and /3 should be related together by the equation /3 2 = (1 -a:)(2 -a), which is approximately satisfied in our simulations.

As far as the distribution P T of the absolu te values of friction forces T is concerned, we find a power Law decay for forces Lower than the mean friction force (T) (

) 2
This distinction between the forces lower than the mean, to which we will refer as "weak" forces, and th ose larger than the mean, referred to as "strong" forces in the following, has a deep meaning, as we shall see below. Let us only mention here that the exponential distribution of strong forces does not seem to be a finite-size effect. In other words, a simple normalization of the forces with respect to the mean force allows the data to collapse almost on the same curve for samples of 500 to 4000 particles.11

0 •A -�' , o B -1 8 )-) AC � � .. ,. f--< .... Q o.. ..... .... '--' -2 ,_. ' U ,i � b!)
6' : � j 0 'i-l;.,,_ 0 0 � -3 The exponential distribution of strong normal forces, has been observed in experiments. 6 • 7 Weak normal forces and friction forces at individual contacts are technically difficult to measure, and their distributions have not yet been observed experimentally. The power-law decay or the uniform distribution of weak forces, comprising nearly 60% of contacts, indicates that the weak forces are generat.ed through a self-similar branching process from strong forces. In contrast, the strong forces are conditionned by the level of the deviatoric Joad, which sets in effect a characteristic force different from the mean force. This point will become more clear by the study of the stress tensor.

Stress tensor

The stress tensor is the relevant variable in transition to the continuous limit. In contrast to PN and PT , it in volves both the contact forces and the contact orienta tions according to the following classical formula! 9

(3

)
where n is the region inside the sample for which the stress tensor is calculated with a volume equal to V, !;° is the i-component of the force at the contact c, and d 'j is the j-component of the intercenter vector cf. This equation allows to separate the contributions of weak and strong forces to the global stress tensor. The weak tensor

<J"

w and the strong tensor <J" s are given by the above equation when the summation is restricted to only weak contacts and only strong contacts, respectively.

Among our samples, only sample A, due to its uniform stress field, provides enough statistics for the study of the stress tensor. Fig. 5 shows the orientations and the eigenvalues of <J" w and OE"' in sample A at shear peak, i.e. at the maximal value of q = �;+��, (q = 0.18), where OE1 and OE2 are the principal values of the total stress tensor <J" = <J" w + <J" s . We see that <J" w is almost spherical and contributes no more than 3% to the deviatoric part of the total stress tensor OE, whereas <J" 9 represents almost the whole deviatoric load, and its major principal axis has the same orientation as that of the imposed deformation.

The isotropie nature of the weak stress tensor indicates that the weak contacts feel the influence of the deviatoric load only as an average over ail directions. The strong contacts directly support the deviatoric load, whose signature appears as a characterstic force in the exponential decay of strong forces.

Iuduced auisotropy

We now consider the distribution P e of contact orientations. The anisotropie na ture of P e has been extensively studied in the past. 20 • 2 1 • 22 • 9 • 8 Here, we define two separate distributions P9 and Pê for weak and strong contacts, respectively. The polar diagrams of these distributions are shown in Fig. 6 for sample A at shear peak. We see that both distributions are anisotropie, although to a lesser extent in the weak subnetwork than in the strong one. The interesting behavior observed here is that the principal direction of Pê coïncides with that of the stress tensor, whereas the principal direction of P8 is orthogonal! This again confi rms the bimodal na ture of the force network, and clearly shows the complementarity between the two subnetworks: The strong chains need "lateral" weak forces in order to be stabe.

Dissipatiou

Particle rotations constitute one of the difficult aspects of the micromechanics of granular materials in quasistatic deformation. The possibility of particles to roll over one another provides a very low-dissipative local mechanism of deformation, so that if each particle could roll over its neighbors, then a dense granular system would essentially behave like a liquid. However, in a quasistatically driven system, the particle rotations are generically frustrated, i.e. particles cannot move and rotate without sliding at some contacts in the medium. This gives rise to long range correlations with patterns that have been partially studied in the case of regular packings. 18 • 23 The question we would like to raise here is how the positions of sliding contacts in the contact network are correlated with the contact forces?

The distinction between weak and strong subnetworks again provides a simple key to the problem. In Fig. 7, we have shown the two subnetworks with different colors and the positions of the sliding contacts. Only 8% of contacts are sliding, and a rapid inspection shows that almost all of them are on the weak subnetwork. In other words, ail strong contacts are nonsliding and all the dissipation takes within the weak subnetwork. This remarkably simple behavior of the sliding contacts with respect to the force subnetworks shows the dynamic nature of the bimodal distribution of forces. The strong subnetwork is completely unstable since ail its contacts are nonsliding. As a result, it tends to buckle under the action of the externat deviatoric load, giving rise to an orthogonal anisotropy and sliding contacts in the weak subnetwork.

Conclusion

The observations briefly presented above provide a consistent picture of the internai mechanical state of a granular packing in quasistatic deformation, at least in two dimensions. The contact network is composed of two complementary subnetworks: l. A "load-bearing" percolating subnetwork composed of strong contacts; 2. A "dissipative" subnetwork composed of weak contacts. The strong subnetwork supports the whole deviatoric load applied on the sy stem, although it contains only nonsliding (nondissipative) contacts. The whole dissipation takes place inside the weak subnetwork. This implies that the scale of heterogeneity of a granular system due to sliding and nonsliding states of contacts is the same as that of the strong subnetwork. From the point of view of the stress tensor, the weak subnetwork behaves like an intersticial liquid, whereas the strong subnetwork has a solid-like behavior since it takes over the whole deviatoric load and thus the stability of the system. From the point of view of the fabric tensor (or contact orientations), the strong subnetwork bears the primary anisotropy induced by shear, but it gives rise to a secondary orthogonal anisotropy inside the weak subnetwork.

This two-phase behavior of the force network opens new perspectives both for microscopie and macroscopic modeling of granular materials in quasistatic defor mation. Let us, however, recall that the analysis presented above concerns a two dimensional system. It is not obvious that it works in the same manner in three dimensional systems. In a two-dimensional packing, two oppositely-oriented arches of strong contacts may surround a region composed of weak contacts alone. This topological feature suggests a mechanism to explain the two-phase behavior in two dimensional systems. Nevertheless, there are reasons to believe that there is a more general mechanism relevant to three-dimensional systems too.

1 0Fi

 1 gur e 1: Contact forèes in• a sheared assembly of d.isks, visualized using the photoelastic effect, and encoded as widths of intercenter segments [Drescher and de Josselin de Jong, 1972].

Figure 2 :

 2 Figure 2: Normal components of the contact forces in sample A (see text) encoded both as the widths of intercenter connecting segments and by the color intensity.

Fig. 2

 2 displays the normal forces in sample A at an advanced stage of deformation. The force network is in very good qualitative agreement with optical images such as the one shown in Fig. l. Figs. 3( a) and 3(b) dis play the plot of PN on semilog and log-log scales in the three samples. In all cases, independently of the confining Joad, the normal forces lower than the mean normal force (N) have a power-law distribution, whereas the data for forces larger than (N) are well fitted by an exponential decay: PN oc { (�r a e (J(l-N /( N )) N N < (N), > (N) .

Figure 3 :

 3 Figure 3: (a) Semilogarithmic, and (b) -log-log plots of the probability distribution PN o[ normal forces N.

Figure 4 :

 4 Figure 4: (a) Semilogaritlunic, and (b) log-log plots of the probability distribution PT of f r iction forces T.

Figure 5 :

 5 Figure 5: Contributions of weak and strong contacts to the stress tensor in sample A at shear peak.

Figure 6 :

 6 Figure 6: Polar diagram of the distribution of contact orientations in weak and strong subnetworks.

Figure 7 :

 7 Figure 7: Network of normal forces in sample A. Forces are encoded as the widths of intercenter segments. Weak and strong subnetworks are shown with two cl ifferent colors. The filled circles show the positions of slicl ing contacts.

Acknowledgements

It is a pleasure to acknowledge many fruitful discussions with U. Bastolla and L. Brendel.


Olivier Carton
email: olivier.carton@irif.fr

Bruno Guillon
email: guillon.brunocs@gmail.com

Fabian Reiter
email: fabian.reiter@gmail.com

Counter Machines and Distributed Automata

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

Space and time are the two standard resources for solving computational problems. Typically, the more of these resources a computing device has at its disposal, the harder the problems it can solve. In this paper, we consider two types of devices whose usages of space and time turn out to be dual to each other.

On the one hand, we look at counter machines, which can use a lot of space. In the way we define them here, these devices act as language recognizers. Just like classical finite automata, they take a finite word as input, read it once from left to right, and then decide whether or not to accept that word. However, in addition to having a finite-state memory, such a machine also has a fixed number of counters, which can store arbitrarily large integer values (and are initially set to zero). The machine has read access to those values up to some fixed threshold. Whenever it processes a symbol of the input word, it can deterministically change its internal state and simultaneously update each counter x to a new value that is expressed as the sum of values of several counters y 1 , . . . , y n and a constant c. (Every update consumes an input symbol, i.e., there are no epsilon transitions.) Our main concern are two special cases of this model: sumless counter machines, which can increment, decrement and copy counter values but not sum them up, and copyless counter machines, which can compute arbitrary sums but not use the same counter more than once per update step. Both of these conditions entail that counter values can grow only linearly with the input length, and, as we will see, they yield in fact the same expressive power.

On the other hand, we look at distributed automata, which are devices that can use a lot of time. For our purposes, they also act as language recognizers, but their input word is given in form of a directed path graph whose nodes are labeled with the symbols of the word (such that the first symbol is on the source node).

To run a distributed automaton on such a path, we first place a copy of the automaton on each node and initialize it to a state that may depend on the node's label. Then, the execution proceeds in an infinite sequence of synchronous rounds, where each node determines its next state as a function of its own current state and the current state of its incoming neighbor (i.e., the node to its left). Altogether, there are only a finite number of states, some of which are considered to be accepting. The automaton acts as a semi-decider and accepts the input word precisely if the last node of the path visits an accepting state at some point in time. Here, we are particularly interested in those distributed automata whose state diagram does not contain any directed cycles except for self-loops; we call them quasi-acyclic. They have the property that all nodes stop changing their state after a number of rounds that is linear in the length of the input word. Therefore, if a quasi-acyclic automaton accepts a given word, then it does so in linear time.

To sum up, we have a sequential model and a distributed model that consume space and time in opposite ways: given an input word of length n, a sumless or copyless counter machine uses time n and space linear in n, whereas a quasiacyclic distributed automaton uses space n and linear time. 4 The purpose of this paper is to show that there really is a duality between the space of one model and the time of the other. In fact, we will prove that the two models are expressively equivalent. Besides being of independent interest, this result also relates to three separate branches of research.

Cellular automata. In theoretical computer science, cellular automata are one of the oldest and most well-known models of parallel computation (see, e.g., [START_REF] Kari | Theory of cellular automata: A survey[END_REF]). They consist of an infinite array whose cells are each in one of a finite number of states and evolve synchronously according to a deterministic local rule. In this regard, a distributed automaton over a labeled directed path can be viewed as a (one-dimensional) one-way cellular automaton with some permanent boundary symbol delimiting the input word [START_REF] Dyer | One-way bounded cellular automata[END_REF]. This model has been studied as language recognizer, and differences between real time (i.e., time n for an input of length n) and linear time (i.e., time in O(n)) have been highlighted -see [START_REF] Terrier | Language recognition by cellular automata[END_REF] for a survey on language recognition by cellular automata. As explained below, our work initially takes its motivation from distributed computing, hence the choice of "distributed automata" rather than "cellular automata". Nevertheless, the results presented here may be viewed in terms of languages recognized by one-way cellular automata, with the technical difference that the input words are reversed with respect to the usual definition of one-way cellular automata. 5A long-standing open problem in this area is the question whether or not oneway cellular automata working in unrestricted time can recognize every language in DSpace(n), i.e., the class of languages accepted by deterministic Turing Machines working in linear space. The latter actually coincides with the class of languages accepted by (two-way) cellular automata (see, e.g., [START_REF] Kutrib | Cellular automata -A computational point of view[END_REF]). By relating a subclass of one-way cellular automata with counter machines working in linear space, our results might be considered as a new approach towards describing the expressiveness of one-way cellular automata. Our contribution concerns a class of (reversed) languages included in the class of languages recognized by linear-time one-way cellular automata. Indeed, the quasi-acyclic restriction on distributed automata corresponds to a special case of one-way cellular automata in which each cell may change its state only a bounded number of times during an execution [START_REF] Vollmar | On Cellular Automata with a Finite Number of State Changes[END_REF]. This is a strict subcase of one-way cellular automata working in linear time, as can be deduced, for instance, from [START_REF] Vollmar | Some remarks about the "efficiency" of polyautomata[END_REF]Prop 3]. More precisely, quasi-acyclic distributed automata correspond to freezing cellular automata, which are cellular automata in which each state change of a cell is increasing according to some fixed order on the states [START_REF] Goles | Introducing Freezing Cellular Automata[END_REF]. In particular, freezing cellular automata have bounded communication [START_REF] Kutrib | Cellular automata with sparse communication[END_REF]. Conversely, as observed in [START_REF] Goles | Introducing Freezing Cellular Automata[END_REF], each one-way cellular automaton with bounded communication can be easily transformed into an equivalent freezing one.

Counter machines. A classical result due to Minsky states that Turing machines have the same computational power as finite-state machines equipped with two integer counters that can be arbitrarily often incremented, decremented, and tested for zero [START_REF] Minsky | Recursive unsolvability of post's problem of "tag" and other topics in theory of turing machines[END_REF]. Such devices are often referred to as Minsky machines. Their Turing completeness led Fischer, Meyer, and Rosenberg to investigate the space and time complexities of machines with an arbitrary number of counters, viewed as language recognizers. In [START_REF] Fischer | Counter machines and counter languages[END_REF], they paid particular attention to real-time machines, where the number of increments and decrements per counter is limited by the length of the input word. Among many other things, they showed that increasing the number of counters strictly increases the expressive power of real-time machines, and that those devices become even more powerful if we equip them with the additional ability to reset counters to zero (in a single operation). Over four decades later, Petersen proved in [START_REF] Petersen | Simulations by time-bounded counter machines[END_REF] that for machines with a single counter, real time with reset is equivalent to linear time without reset, and that for machines with at least two counters, linear time is strictly more expressive. A further natural extension of real-time machines is to allow values to be copied from one counter to another (again, in a single operation). In [START_REF] Dymond | Indirect addressing and the time relationships of some models of sequential computation[END_REF], Dymond showed that real-time machines with copy can be simulated by linear-time machines without copy.

The general version of the counter machines defined in this paper can also be seen as an extension of the real-time machines of Fischer, Meyer, and Rosenberg. In addition to the reset and copy operations, we allow counter values to be summed up. Our formal notation takes inspiration from cost register automata, which were introduced by Alur et al. in [START_REF] Alur | Regular functions and cost register automata[END_REF]. Moreover, the concept of copylessness is borrowed from there. The authors are not aware of any previous work dealing with the specific counter machines defined in this paper. However, it follows from [3, Thm 2.1] and our main result that sumless and copyless counter machines form a subclass of the linear-time counter machines defined in [START_REF] Fischer | Counter machines and counter languages[END_REF].

Distributed computing and logic. The original motivation for this paper comes from a relatively recent project that aims to develop a form of descriptive complexity [START_REF] Immerman | Descriptive complexity[END_REF] for distributed computing [START_REF] Lynch | Distributed Algorithms[END_REF][START_REF] Peleg | Distributed Computing: A Locality-Sensitive Approach[END_REF]. In that context, distributed automata are regarded as a class of weak distributed algorithms, for which it is comparatively easy to obtain characterizations by logical formulas. Basically, these automata are the same as those described above, except that they can run on arbitrary directed graphs instead of being confined to directed paths. In order to make this possible, each node is allowed to see the set of states of its incoming neighbors (without multiplicity) instead of just the state of its left neighbor. On graphs with multiple edge relations (E 1 , . . . , E r ), the nodes see a separate set for each relation. The first result in this direction was obtained by Hella et al. in [START_REF] Hella | Weak models of distributed computing, with connections to modal logic[END_REF], where they showed that distributed automata with constant running time are equivalent to a variant of basic modal logic on graphs. The link with logic was further strengthened by Kuusisto in [START_REF] Kuusisto | Modal logic and distributed message passing automata[END_REF], where a logical characterization of unrestricted distributed automata was given in terms of a modal-logic-based variant of Datalog. Then, Reiter showed in [START_REF] Reiter | Asynchronous distributed automata: A characterization of the modal mu-fragment[END_REF] that the least fixpoint fragment of the modal µcalculus captures an asynchronous variant of quasi-acyclic distributed automata. Motivated by these connections to modal logic, a field at the frontier between decidability and undecidability, the emptiness problem for distributed automata was investigated in [START_REF] Kuusisto | Emptiness problems for distributed automata[END_REF]. The authors observed that the problem is undecidable for arbitrary automata on directed paths (which implies undecidability on arbitrary graphs), as well as for quasi-acyclic automata on arbitrary graphs. But now, the main result of the present paper supersedes both of these findings: since, by a simple reduction from the halting problem for Minsky machines, the emptiness problem for sumless and copyless counter machines is undecidable, we immediately obtain that the problem is also undecidable for quasi-acyclic distributed automata on directed paths. It must, however, be stressed that such undecidability results have been known for a long time within the community of cellular automata. For instance, it was shown by Seidel in [START_REF] Seidel | Language recognition and the synchronization of cellular automata[END_REF] that the emptiness problem for real-time one-way cellular automata is undecidable (see also [START_REF] Malcher | Descriptional complexity of cellular automata and decidability questions[END_REF]). This was later strengthened by Kutrib and Malcher, who proved in [START_REF] Kutrib | Cellular automata with sparse communication[END_REF] that the problem remains undecidable even if we restrict ourselves to automata with bounded communication. Thereby they provided an undecidability result that is stronger than our corollary, given that quasi-acyclic distributed automata do not necessarily work in real time.

Outline. The remainder of the paper is devoted to proving our main result: Theorem 1. The following three classes of devices are effectively equivalent.

1. Copyless counter machines on nonempty finite words. 2. Sumless counter machines on nonempty finite words. 3. Quasi-acyclic distributed automata on pointed directed paths.

All the necessary definitions are introduced in Section 2. The statement then follows from several translations provided in the subsequent sections: we have "1 → 2" by Proposition 7 in Section 3, then "2 → 3" by Propositions 9 and 10 in Sections 3 and 4, and finally "3 → 1" by Proposition 11 in Section 5. We conclude with a detailed summary of these translations in Section 6 (see Figure 4) and some perspectives for future work.

Preliminaries

We denote the set of nonnegative integers by N = {0, 1, 2, . . . }, the set of positive integers by N + = N \ {0}, and the set of integers by Z = {. . . , -1, 0, 1, . . . }. The power set of any set S is written as 2 S . Furthermore, for values m, n ∈ Z such that m ≤ n, we define the interval notation [m : n] := {i ∈ Z | m ≤ i ≤ n} and the cutoff function cut n m , which truncates its input to yield a number between m and n. The latter is formally defined as cut n

m : Z → [m : n] such that cut n m (i) is equal to m if i < m, to i if m ≤ i ≤ n, and to n if i > n.
Let Σ be a finite set of symbols. A word over Σ is a finite sequence w = a 1 . . . a n of symbols in Σ. We write |w| for the length of w and Σ + for the set of all nonempty words over Σ. A language over Σ is a subset of Σ + .

Example 2 (running). As a running example, we consider the language L of nonempty words in {a, b, c} + whose prefixes all have at least as many a's as b's and at least as many b's as c's: L = {w | for every prefix u of w, |u| a ≥ |u| b ≥ |u| c }, where |w| σ denotes the number of σ's in w, for σ ∈ Σ. For instance, the words aaabbc and aabbac belong to L, whereas the word abacac does not.

Counter machines

Let X be a finite set of counter variables and h be a positive integer. We denote by Ξ(X, h) the set of counter expressions over X and h generated by the grammar e ::= x + e | c , where x ∈ X and c ∈ [-h : h]. An update function for X given h is a map ξ ∈ Ξ(X, h) X that assigns a counter expression to each counter variable.

Definition 3 (Counter Machine).

A k-counter machine with h-access over the alphabet Σ is a tuple M = (P, X, p 0 , τ, H), where P is a finite set of states, X is a set containing precisely k distinct counter variables, p 0 ∈ P is an initial state, τ : P × [-h : h] X × Σ → P × Ξ(X, h) X is a transition function, and H ⊆ P is a set of accepting states.

Such a counter machine "knows" the exact value of each counter that lies between the thresholds -h and h; values smaller than -h are "seen" as -h, and similarly, values larger than h are "seen" as h. Furthermore, it has the ability to add (in a single operation) constants between -h and h to its counters. The technical details are explained in the following.

Let M = (P, X, p 0 , τ, H) be a counter machine with h-access over the alphabet Σ, and let w = a 1 . . . a n be a word in Σ + . A valuation of X is a map ν ∈ Z X that assigns an integer value to each counter variable x ∈ X. The initial valuation is ν 0 = {x → 0 | x ∈ X}. Any valuation ν ∈ Z X gives rise to an extended valuation ν ∈ Z Ξ(X,h) , which assigns values to counter expressions in the natural way, i.e., ν(c) = c and ν

(x + e) = ν(x) + ν(e), for c ∈ [-h : h] and x ∈ X. A memory configuration of M is a tuple C = (p, ν) ∈ P × Z X . The run of M on w is the sequence of memory configurations R = (C 0 , . . . , C n ) such that C 0 = (p 0 , ν 0 ), and if C l = (p, ν) and τ (p, cut +h -h • ν, a l+1 ) = (p , ξ), then C l+1 = (p , ν • ξ).
The machine M accepts the word w if it terminates in an accepting state, i.e., if C n ∈ H × Z X . The language of M (or language recognized by M ) is the set of all words accepted by M .

We call an update function ξ ∈ Ξ(X, h) X sumless if it does not allow sums of multiple counter variables, i.e., if for all x ∈ X, the expression ξ(x) is either c or y + c, for some c ∈ [-h : h] and y ∈ X. Note that such an update function allows us to copy the value of one counter to several others, since the same counter variable y may be used in more than one expression ξ(x). On the other hand, ξ is copyless if every counter variable y ∈ X occurs in at most one expression ξ(x), and at most once in that expression. (However, sums of distinct variables are allowed.) By allowing each counter to be used only once per step, this restriction ensures that the sum of all counter values can grow at most linearly with the length of the input word. A counter machine M is called sumless or copyless if its transition function τ makes use only of sumless or copyless update functions, respectively. As shown in this paper, the two notions are expressively equivalent.

Example 4 (running). The language L from Example 2 is accepted by the sumless and copyless 2-counter machine M = ({p, r}, {x, y}, p, τ, {p}), with τ defined by:

τ s, (c x , c y ), σ =          p, {x := x + 1, y := y } if s = p and σ = a, p, {x := x -1, y := y + 1} if s = p, c x > 0 and σ = b, p, {x := x, y := y -1} if s = p, c y > 0 and σ = c, r, {x := x, y := y } otherwise,
where c x and c y denote the values cut +1 -1 • ν(x) and cut +1 -1 • ν(y) respectively. Intuitively, M uses the counter x to compare the number of a's with those of b's, and the counter y to compare the number of b's with those of c's. The counter x (respectively y) is incremented each time the letter a (respectively b) is read and it is decremented each time the letter b (respectively c) is read. When a counter with value 0 has to be decremented, the machine enters the rejecting sink state r.

Distributed automata

Let Σ be a finite set of symbols. A Σ-labeled directed graph, abbreviated digraph, is a structure G = (V, E, λ), where V is a finite nonempty set of nodes, E ⊆ V ×V is a set of directed edges, and λ : V → Σ is a labeling function that assigns a symbol of Σ to each node. Isomorphic digraphs are considered to be equal. If v is a node in V , we call the pair (G, v) a pointed digraph with distinguished node v. Moreover, if uv is an edge in E, then u is called an incoming neighbor of v.

A directed path, or dipath, is a digraph G = (V, E, λ) that has a distinct last node v last such that each node v in V has at most one incoming neighbor and exactly one way to reach v last by following the directed edges in E. A pointed dipath is a pointed digraph (G, v last ) that is composed of a dipath and its last node. We shall identify each word w ∈ Σ + with the pointed Σ-labeled dipath of length |w| whose nodes are labeled with the symbols of w, i.e., the word a 1 a 2 . . . a n will be identified with the pointed dipath a1 a2 . . . an .

We first give a rather general definition of distributed automata on arbitrary digraphs, and then slightly modify our notation for the special case of dipaths.

Definition 5 (Distributed Automaton

). A (finite) distributed automaton over Σ-labeled digraphs is a tuple A = (Q, δ 0 , δ, F ), where Q is a finite set of states, δ 0 : Σ → Q is an initialization function, δ : Q × 2 Q → Q is a transition function, and F ⊆ Q is a set of accepting states.
Let A = (Q, δ 0 , δ, F ) be a distributed automaton over Σ-labeled digraphs, and let G = (V, E, λ) be a corresponding digraph. The (synchronous) run of A on G is an infinite sequence ρ = (ρ 0 , ρ 1 , ρ 2 , . . . ) of maps ρ t : V → Q, called configurations, which are defined inductively as follows, for t ∈ N and v ∈ V :

ρ 0 (v) = δ 0 (λ(v)) and ρ t+1 (v) = δ ρ t (v), {ρ t (u) | uv ∈ E} .
For v ∈ V , the automaton A accepts the pointed digraph (G, v) if v visits an accepting state at some point in the run ρ of A on G, i.e., if there exists t ∈ N such that ρ t (v) ∈ F . The above definition could be easily extended to cover r-relational digraphs, i.e., digraphs with r edge relations E 1 , . . . , E r , for some r ∈ N + . It suffices to choose a transition function of the form δ : Q × (2 Q ) r → Q, thereby allowing the nodes to see a separate set of states for each of the r relations. With this, one could easily simulate two-way (one-dimensional) or even higher-dimensional cellular automata. However, for our purposes, a single edge relation is enough.

A trace of a distributed automaton A = (Q, δ 0 , δ, F ) is a finite nonempty sequence q 1 , . . . , q n of states in Q such that for 1 ≤ i < n, we have q i = q i+1 and δ(q i , S i ) = q i+1 for some S i ⊆ Q. We say that A is quasi-acyclic if its set of traces is finite. In other words, A is quasi-acyclic if its state diagram does not contain any directed cycles, except for self-loops. In this case, we will refer to = max {n | A has a trace of length n} as the maximum trace length of A. Furthermore, a quasi-acyclic automaton A is said to have at most (k + 1) loops per trace if (k + 1) = max {n | A has a trace containing n looping states}. Here, a looping state is a state q ∈ Q such that δ(q, S) = q for some S ⊆ Q. Notice that every trace of a quasi-acyclic automaton must end in a looping state, since transition functions are defined to be total. (This is why we write "k + 1".)

In this paper, we regard distributed automata as word acceptors, and thus we restrict their input to dipaths. Therefore, in our particular context, a distributed automaton is the same thing as a (one-dimensional, reversed) one-way cellular automaton (see, e.g., [START_REF] Terrier | Language recognition by cellular automata[END_REF]). This allows us to simplify our notation: transition functions will be written as δ :

Q ∅ × Q → Q, where Q ∅ is a shorthand for Q ∪ {∅}.
A node whose left neighbor's current state is p and whose own current state is q will transition to the new state δ(p, q); if there is no left neighbor, p has to be replaced by ∅. Note that we have reversed the order of p and q with respect to their counterparts in Definition 5, as this seems more natural when restricted to dipaths. We say that the language of A (or language recognized by A) is the set of words, seen as pointed dipaths, accepted by A.

As usual, we say that two devices (i.e., counter machines or distributed automata) are equivalent if they recognize the same language.

Example 6 (running). We describe here a distributed automaton A that accepts the language L from Example 2, regarded as a set of dipaths. To this end, we first reformulate the property that every prefix contains at least as many a's as b's and at least as many b's as c's: it is equivalent to the existence of an injective mapping from nodes labeled by b to nodes labeled by a and from nodes labeled by c to nodes labeled by b such that each node can only be mapped to some (possibly indirect) predecessor to its left. Our automaton A implicitly creates such an injective mapping by forwarding all a's and b's to the right until they are "consumed" by matching b's and c's.

The device uses two tracks that may contain the symbols a, b, or "-", i.e., its states are pairs in {a, b, -} × {a, b, -}. Initially, a node labeled by the letter σ ∈ Σ = {a, b, c} is in the state (x, y), where x is equal to "-" if σ = a, to a if σ = b, and to b if σ = c, and y is equal to "-" if σ = c, and to σ otherwise. The first track is the expectation track ; its content indicates which letter the node should receive from its left neighbor in order to eventually accept (the special symbol "-" means "nothing is expected"). The second track is the communication track ; its content is sent to the node's right neighbor (the special symbol "-" means "nothing is sent"). If a node is expecting a letter σ and receives σ from its left neighbor, then that node switches to the state (-, -). This means that the node is no longer expecting any letter and does not transmit anything to its right neighbor (since the letter σ has already been "consumed"). Additionally, A uses two special states ⊥ and , which propagate errors and acceptance, respectively. When a node enters one of these two states, it stays in that state forever. An error always propagates to the right neighbor. In contrast, a node enters state if it receives an acceptance message from the left (i.e., it receives or ∅) and its expectation has been fulfilled.

Figure 1 shows the runs of A on the dipaths aabbac (accepted) and abacac (rejected). Observe that A is not quasi-acyclic, since, for instance, the last node of the dipath aabbac switches from state (-, -) to (-, b) and then again to (-, -).

Translating between counter machines

We start with the translation from copyless to sumless counter machines, followed by two constructions that allow us, in some cases, to focus on counters with non-negative values and 1-access.

Proposition 7. For every copyless k-counter machine with h-access, we can effectively construct an equivalent sumless (2 k )-counter machine with (k •h)-access.

Proof (sketch). The idea is simply to introduce a dedicated counter for each subset of counters Y of the original machine M , and use this dedicated counter to store the sum of values of the counters in Y . Call this sum the value of Y . Since M is copyless, it uses each of its counters at most once in any update function ξ. Therefore, the next value of Y with respect to ξ can be expressed in terms of the current value of some other subset Y and a constant between -|Y | • h and |Y | • h. This allows us to derive from ξ a sumless update function ξ that operates on subsets of counters and uses constants in [-kh : kh].

Sometimes it is helpful to assume that a counter machine never stores any negative values in its counters. For copyless and sumless machines, this does not lead to a loss of generality. We only need the statement for sumless machines, but in fact Proposition 7 implies that it also holds for copyless machines (at the cost of increasing the number of counters). Proposition 8. For every sumless k-counter machine with h-access, we can effectively construct an equivalent machine that is also sumless with k counters and h-access, but whose counters never store any negative values. Proof (sketch). It suffices to represent each counter x of the original machine in such a way that the absolute value of x is stored in a counter and its sign is retained in finite-state memory. As the machine is sumless, we do not have to deal with the issue of computing the sum of a positive and a negative counter value.

In Definition 3, we have introduced counter machines with h-access, for some arbitrary h ∈ N + . This simplifies some of our proofs, but we could have imposed h = 1 without losing any expressive power. The following proposition states this in full generality, although the (easier to prove) restriction to sumless machines would be sufficient to establish our main result. Proposition 9. For every k-counter machine M with h-access, we can effectively construct an equivalent (h • k)-counter machine M with 1-access. If M is copyless or sumless, then so is M . Moreover, if M is sumless, M requires only k counters.

Proof (sketch). The key idea is that M represents each counter x of M by h counters x 0 , . . . , x h-1 over which the value of x is distributed as uniformly as possible. That is, the value of x is equal to the sum of the values of x 0 , . . . , x h-1 , and any two of the latter values differ by at most 1. If M is sumless, there is a simpler way: it suffices to represent x by a single counter storing the value of x divided by h, and to keep track of the remainder in the finite-state memory.

From counter machines to distributed automata

Next, we present the translation from sumless counter machines to quasi-acyclic distributed automata. Proposition 10. For every sumless k-counter machine with 1-access, we can effectively construct an equivalent quasi-acyclic distributed automaton with at most (k + 2) loops per trace.

Proof (sketch). Our construction uses classical techniques from cellular automata theory, similar to simulations of finite automata (see, e.g., [START_REF] Kutrib | Cellular automata -A computational point of view[END_REF]Lem 11]) and counter machines (see, e.g., [START_REF] Goles | Introducing Freezing Cellular Automata[END_REF]Thm 1]) by one-way cellular automata. Let us point out that, contrary to the construction in [START_REF] Goles | Introducing Freezing Cellular Automata[END_REF], we allow the copy operation on counters here. An example of the simulation is shown in Figure 2.

We now explain the main idea. On an input dipath corresponding to some word w, the sequence of states traversed by our distributed automaton at the i-th node is an encoding of the memory configuration (p, ν) that is reached by the simulated counter machine after reading the i-th symbol of w. (The initial configuration is not encoded.) This sequence of states is of the following form: Here, each rectangular block represents a state of the distributed automaton. The symbol σ corresponds to the node's label and ξ is the update function that has been used to enter the memory configuration (p, ν). Counter values are encoded in unary, i.e., the value ν(x) of a counter x is the number of 1's on the associated counter track. (By Proposition 8, we assume the values are never negative.)

• • • σ . . . • • • σ • • • p, ξ 1 • • • 0 p, ξ 1 • • • ⊥ p, ξ 1 • • • p, ξ . . . 1 • • • p, ξ 0 • • • p, ξ ⊥ • • • p, ξ • • • p, ξ • • • p, ξ . . .
1 0 0 ⊥ ⊥ 1 0 1 ⊥ 0 1 0 ⊥ 1 ⊥ 1 1 1 0 1 0 ⊥ 0 ⊥ 1 1 ⊥ 0 1 ⊥ 0 1 1 ⊥ 0 0
The delay phase is used to leave enough time for information to transit. We increase it by 2 at each position, in order to be able to compute decrementation. Hence, at the i-th node, the delay phase lasts for (2i-1) rounds. (This corresponds to the gray states in Figure 2.) Since each counter track associated with a counter x contains a sequence of the form 2i 1 ν(x) 0⊥ ω , we are guaranteed that the simulating distributed automaton has at most (k + 2) loops per trace.

From distributed automata to counter machines

As the last piece of the puzzle, we now show how to convert a quasi-acyclic distributed automaton into an equivalent copyless counter machine. Proposition 11. For every quasi-acyclic distributed automaton with at most (k + 1) loops per trace and maximum trace length , we can effectively construct an equivalent copyless k-counter machine with -access. Proof (sketch). Basically, after our counter machine M has read the i-th symbol of the input word w, its memory configuration will represent the sequence of states traversed by the simulated distributed automaton A at the i-th node of the dipath corresponding to w. This exploits the quasi-acyclicity of A to represent the infinite sequence of states traversed by a node as a finite sequence of pairs in Q × (N + ∪ {∞}), where values other than 1 and ∞ are stored in the counters. An example illustrating the construction is provided in Figure 3. The crux of the proof is the following: if the i-th node remains in the same state for more than rounds, then (by quasi-acyclicity) the sequence of states traversed during that time by the (i + 1)-th node must become constant (i.e., repeating always the same state) no later than the -th round. Thus, to compute the entire state sequence of the (i + 1)-th node, M does not need to know the exact numbers of state repetitions in the i-th node's sequence. It only needs to know these numbers up to threshold and be able to sum them up.

∅ ∞ G x O x G x G x O x O x O x ∞ 1 y y 1 y 1 # 1 I ∞ I ∞ # 1 I ∞ I ∞ I ∞ I ∞ x

Conclusion

We have now completed the proof of Theorem 1, which states the equivalence of (1) copyless and (2) sumless counter machines on finite words and (3) quasi-acyclic distributed automata on pointed dipaths. More precisely, we have established the following translatability results, which are visualized in Figure 4: 1. A copyless k-counter machine with h-access can be translated into an equivalent sumless (2 k )-counter machine with (k • h)-access (by Proposition 7). 2. A sumless k-counter machine with h-access, can be transformed into an equivalent (sumless k-counter) machine that has merely 1-access (by Proposition 9), which in turn can be translated into an equivalent quasi-acyclic distributed automaton with at most (k + 2) loops per trace (by Proposition 10). 3. A quasi-acyclic distributed automaton with at most (k + 1) loops per trace and maximum trace length can be translated into an equivalent copyless k-counter machine with -access (by Proposition 11). This cycle of translations suggests that the number of counters of copyless and sumless counter machines is closely related to the maximum number of loops per trace of quasi-acyclic distributed automata. However, the precise relationship is left open. In particular, as of the time of writing, the authors do not know whether the exponential blow-up of the number of counters in Proposition 7 could be avoided.

Copyless counter machines

In addition, there are several natural directions in which the present work might be extended. First of all, the models of computation concerned by Theorem 1 are special cases of two more general classes of word acceptors, namely the unrestricted counter machines of Definition 3 and the unrestricted distributed automata of Definition 5 on pointed dipaths (or equivalently, reversed one-way cellular automata). It is thus natural to ask whether our result carries over to stronger (sub)classes of counter machines and distributed automata. Instead of counter machines, one might also consider sequential machines with more freely accessible memory, such as restricted read-write tapes. Second, one could conversely try to establish similar connections for weaker classes of devices. In particular, it would be interesting to find a distributed characterization of the real-time counter machines of Fischer, Meyer, and Rosenberg [START_REF] Fischer | Counter machines and counter languages[END_REF], which are both copyless and sumless. Third, all of the models considered in this paper are one-way, in the sense that counter machines scan their input from left to right and distributed automata on dipaths send information from left to right. Hence, another obvious research direction would be to investigate the connections between (suitably defined) two-way versions. Finally, for the sake of presentational simplicity, we have only looked at deterministic models. It seems, however, that our proofs could be easily extended to cover nondeterministic or even alternating devices. We leave this open for future work.

Fig. 1 .

 1 Fig. 1. The runs of the distributed automaton from Example 6 on aabbac and abacac.

  hand side illustrates the run of the 2-counter machine from Example 4 on the word aaabbc. On the right-hand side, this machine is simulated by a quasi-acyclic distributed automaton running on the corresponding {a, b, c}-labeled dipath. Each node of the dipath traverses a sequence of states that encodes the memory configuration reached by the counter machine after reading the node's label. (The initial configuration is left implicit.) Note that only the two counter tracks of the automaton are shown, i.e., the transition track is not depicted. States represented in gray contain the respective node's label σ ∈ {a, b, c} in their transition track, whereas black or white states contain the machine's state p and some counter update function ξ, both determined using the machine's transition function τ .

Fig. 2 .

 2 Fig.2. Simulating a counter machine with a distributed automaton to prove Proposition 10. The depicted counter machine is the same as in Example 4. But the resulting automaton differs from the one given in Example 6. In particular, it is quasi-acyclic.

Fig. 3 .

 3 Fig.3. Simulating a distributed automaton with a counter machine to prove Proposition 11. The left-hand side depicts the run of a quasi-acyclic distributed automaton on the {a, b}-labeled dipath that corresponds to the word babbaaa. This automaton has at most three loops per trace; its set of states Q consists of the states O, G, , I, which have self-loops, and the states , #, which do not. On the right-hand side, the automaton is simulated by a copyless 2-counter machine whose memory configurations encode infinite sequences of states of the automaton as finite sequences of pairs in Q × (N+ ∪ {∞}). Values different from 1 and ∞ are stored in the two counters x and y.

Fig. 4 .

 4 Fig. 4. The translations involved in the proof of Theorem 1.

We assume that counter machines store the values of their counters in unary encoding, and we measure the space usage of a distributed automaton by the number of nodes.

Contrary to distributed automata, one-way cellular automata are usually represented with information transiting from right to left, that is, a cell receives the state from its right neighbor and the leftmost cell decides acceptance of the input, see, e.g.,[START_REF] Kutrib | Cellular automata -A computational point of view[END_REF].

Acknowledgments

We are grateful to the anonymous reviewers for their constructive comments. We also thank Martin Kutrib and Pierre Guillon for interesting discussions, especially concerning the connection of our results with the field of cellular automata. This work was partially supported by the ERC project EQualIS (FP7-308087) and the DeLTA project (ANR-16-CE40-0007).


W Theobald

A Bose

R Yan

R Betti

M Lafon

D Mangino

A R Christopherson

C Stoeckl

W Seka

W Shang

D T Michel

C Ren

R C Nora

A Casner

J Peebles

F N Beg

X Ribeyre

E Llor Aisa

A Colaïtis

V Tikhonchuk

M S Wei

Enhanced hot-electron production and strong-shock generation in

whether they are published or not. The documents may come   L'archive ouverte pluridisciplinaire

Generating strong shocks up to several hundred megabars allows one to explore plasma and material properties at the most-extreme conditions of energy density. It also enables one to develop two-step inertial confinement fusion (ICF) schemes, where ignition is separated from the main compression of the thermonuclear fuel. A promising two-step ignition scheme is shock ignition (SI) [1][2][3][4], where ignition is triggered by a strong shock launched at the end of the implosion and driven by a pressure above ∼300 Mbar. Detailed reviews of the current status and physics issues for SI are found in Refs. [5][6][7]. One of the most critical issues is the high UV laser intensity of 5×10 15 to 1×10 16 W/cm 2 required by the ignitor spike pulse. The spike will excite parametric laser-plasma instabilities (LPI's) in the hot plasma corona surrounding the imploding capsule, thereby transferring a significant amount of laser energy to hot electrons. Recent work [8][9][10] demonstrated that hot electrons can enhance the shock pressure. It is still an open question whether they might preheat a SI target [11] or if the benefits prevail because the areal density is large enough to stop them in the shell and augment the shock strength [12,13]. Another concern pertains to the energy coupling. The spike pulse must couple sufficient energy to the target in order to generate a strong-enough shock. LPI's may reduce the coupling efficiency and prevent the seed shock pressure from reaching the required magnitude.

Directly measuring the pressure at these high intensities is nearly impossible, so it must be instead inferred indirectly. Experiments in planar geometry at the LULI [14], Omega [15], and PALS [16] Laser Facilities have inferred ablation pressures in the range of ∼40 to 90 Mbar, which were limited by lateral heat flow from the laser spots in the planar geometries. The lateral transport was suppressed with the development of a new platform [17,18] that applies spherical targets and x-ray diagnostics. It allows one to evaluate the pressure at SI-relevant laser intensities. The laser launches into the solid target an inwardly propagating shock wave that converges at the center, generating a short x-ray flash that is measured with a time-resolved diagnostic. Several experiments established this scheme as a reliable platform using a variety of laser energies, pulse shapes, and target diameters [18].

There is a continuing interest in exploring new ablator materials in direct-drive ICF research in order to improve the hydrodynamic efficiency [19], mitigate the hot-electron production [20,21], and suppress the Rayleigh-Taylor instability [22][23][24]. Recent theoretical work demonstrated an overall better performance with mid-Z ablators than plastic (CH) by suppressing the threshold of detrimental LPI while preserving the hydrodynamic stability properties [25]. All of this work has been performed, however, at low laser intensities of up to ∼1×10 15 W/cm 2 , which is relevant for the standard hotspot-ignition concept but not for the spike interaction in SI.

This Letter describes for the first time that the ablator plays an important role at SI-relevant laser intensities. The experiment shows that CH produces significantly more hot electrons and stronger shocks than the other materials. This important finding sheds light on the laser plasma-interaction physics in an intensity and plasma regime, which is insufficiently explored and might provide a path to higher energy density states in directdrive geometry.

The experiment used 60 UV (λ = 351 nm) beams from the OMEGA laser [26] with a total energy of 22 to 26 kJ that were focused to an overlapping intensity of up to ∼5×10 15 W/cm 2 on the surface of a spherical solid target. The beams were equipped with small-spot phase plates [27], polarization smoothing [28], and smoothing by spectral dispersion (SSD) [29]. The single-beam intensity was ∼4×10 14 W/cm 2 for SSD on and ∼6×10 14 W/cm 2 for SSD off. The targets with an outer diameter (OD) of 412 to 496 µm consisted of an inner CH core that was doped with Ti with an atomic concentration of 5% and an outer ablator layer with a thickness (t) of 20 to 46 µm of a different material [Fig. 1(a)]. The outer layer was irradiated with the laser pulse shown in Fig. 1(b). A low-power prepulse of ∼1-ns duration produced a plasma corona with which the high-power part of the pulse interacted to generate the shock and the hot electrons. Four ablators (CH, Be, C, and SiO 2 ) with different atomic numbers (Z) were used. Table I summarizes the parameters. The shock wave collapsed in the center, resulting in a short burst of x-ray radiation that was detected spatially and temporally resolved with multiple x-ray framing cameras. Each framing camera was absolutely timed through dedicated timing shots [19,30] with an accuracy of 30 ps. Time-resolved and time-integrated hard x-ray measurements provide a characterization of the hot-electron population (hot-electron temperature and total energy). Details on this can be found in Ref. [18] and references therein. The output from a radiation-hydrodynamics simulation for each target was used as an input for a Monte Carlo electron and photon transport code simulation (ITS 3.0) to calculate the bremsstrahlung emission for each diagnostic channel and compare it to the measurement. The hot-electron energy and temperature were varied until good agreement between calculations and experimental values were achieved. The instrument response function was also modeled with the Monte Carlo code. The Monte Carlo simulation takes the material effects into account and calculates the hot-electron stopping in the compressed target and the resulting hard x-ray emission including opacity effects. Optical backscatter diagnostics measured the amount of backscattered energy at the laser wavelength and provided temporally streaked spectra of the stimulated Brillouin scattering (SBS) and the stimulated Raman scattering (SRS). A quantity α is defined as α = 1 -E 351 /E L , where E 351 is the measured backscattered energy around the laser wavelength and E L is the measured incident laser energy.

Figure 2(a) shows the measured flash time, which is defined as the occurrence of the x-ray flash relative to the start of the laser pulse, for the different ablators with SSD on (squares) and SSD off (circles) in sequence of increasing Z. The measured flash times were adjusted to account for differences in target size, laser energy, and t. One-dimensional (1-D) radiation-hydrodynamics simulations were performed with the code LILAC [33] to analyze the dependence of the flash time on the different variables for each material. The flash times were then adjusted for an ablator thickness that resulted in a constant ablator mass of 20.8 µg, a laser energy of 24 kJ, and a diameter of 372 µm for the Ti doped CH part of the target to obtain a valid comparison for the different targets. The timing adjustments were between 43 ps and 10 ps for CH and smaller than 64 ps for the other materials. The data show the general trend of an earlier flash with increasing Z except for CH, which produced the earliest flash. Turning SSD off advances the flash in CH by ∼70 ps while no significant effect is observed in the other materials. Figure 2(b) shows the measured time- TABLE I. Ablators along with the average outer target diameter (OD), average layer thickness (t), and measured mass density (ρ). Also given are calculated plasma parameters at the quarter-critical density (nc/4) of electron temperature (Te), ion temperature (Ti), radial position of nc/4 (R), and density scale length (L) from radiation-hydrodynamics simulations. The last two columns list calculated intensity thresholds for the two-plasmon decay (TPD) [31] and stimulated Raman backscatter (SRS) [32] instabilities.

Ablator OD (µm) t (µm) ρ (g/cm 3 ) Te (keV) Ti (keV) R (µm) L (µm) IT P D (W/cm 2 ) ISRS (W/cm
integrated conversion efficiency (CE). Plastic stands out by producing by far the most hot-electrons with up to ∼2 kJ of total hot-electron energy (time-integrated CE ∼8%) when SSD was turned off. Nine and seven shots were performed for CH with SSD on and off, respectively, to prove that the observed difference is not an artifact. If CH is treated as an exception, there is the general trend of a slight increase in hot-electron production with higher Z. The inferred hot-electron temperatures lie between 60 and 80 keV and are independent of the ablator and SSD. A higher hot-electron fraction corresponds to an earlier flash time, which indicates that hot electrons play a role in the shock formation and augment its strength. The experimental data provide information about the mechanism of hot-electron generation. A clear correlation between hot-electron production and the SRS backscatter signal is observed [Fig.

E abs ≈ E L -E 351 -2E h = (α -2CE)E L .
Using, e.g., the measured values for CH and SSD off, the absorbed energy is E CH,of f abs ≈ 0.56E L . A very similar value of E CH,on abs ≈ 0.55E L is obtained for SSD on, showing that only about half of the laser energy is absorbed in the plasma. Similar values are obtained for the other materials. The high value of α for CH and SSD off is a result of the large amount of SRS backscattering and hot electron energy. Therefor, absorption is about equal in all the materials and for SSD on and off. The absorbed energy fractions from simulations are in the range of ∼40% to 60% and are consistent with the experimental values within the error. Since only ∼5% of the absorbed energy is coupled to the hydrodynamic drive it is reasonable to conclude that small discrepancies between simulated and experimentally-inferred laser absorptions are negligible compared to the large effects of hot electron energy deposition when it comes to producing higher pressures in the target. The variation in flash time can therefore not be explained by a difference in absorbed energy but is likely the consequence of a difference in E h .

An effective maximum ablation pressure has been inferred [see Fig. 3(a)] from LILAC simulations. The effect of hot electrons was taken into account by increasing the flux limiter [34] so that the flash time was recovered in the simulations for each ablator material. Although it has been shown in Ref. [17] that the pressure increase from hot electrons may be described by an increased flux limiter, this simplified description does not capture important details such as slowing down, preheat, and local energy deposition. Therefore, additional simulations were performed for CH and C that included a detailed hot-electron transport model, which confirmed the pressures shown in Fig. 3(a). The simulation details are discussed in Ref. [17]. Briefly, the measured hot-electron fraction and temperature were used as input in the LILAC simulations as well as the temporal dependence of the hot-electron production. The simulations employed a multigroup radiation diffusion model, an equation-of-state model based on SESAME tables, flux-limited thermal transport, and a hot-electron transport package. A fraction of the laser energy reaching the quarter-critical surface is converted into hot electrons, assuming a single-temperature Maxwellian distribution and an isotropic emission within a 120 • full divergence angle in the forward direction. The hot electrons are transported in straight lines into the target. The simulations show that the hot electrons increase the effective maximum ablation pressure in CH by 77% and in C by 45%.

Figure 3(b) shows the inferred time-resolved CE (red) for two shots with CH (solid) and C (dashed). The black curves represent the corresponding laser pulse shapes. The onset of hot-electron production lags by ∼0.2 ns with respect to the rising edge of the laser pulse. This is explained by a strong SBS backscatter spike with a width of ∼0.2 ns upon the arrival of the main pulse, which reduces temporarily the laser intensity around n c /4 below the thresholds of the SRS and two-plasmon-decay (TPD) instabilities. In addition, the change in temperature and density scale length in this region also directly affects the LPI thresholds. LILAC simulations show that a plateau in the velocity profile develops in the region between n c /10 and n c /4, which promotes a high SBS gain during this time. Averaged over the laser pulse shape and over the full target sphere, SBS scatters back ∼ 2 -3% of the laser energy for CH, while this fraction is below 2% for the other ablators. A comparison of the simulations of the two shots shown in Fig. 3(b) reveals that at the time of the observed SBS spike, there is a difference in the flow velocity gradient of both materials. The velocity profile for CH is much shallower than for C. This probably caused a higher SBS gain in CH than in C. Time-resolved measurements of the SRS backscattering appear closely correlated with the hot-electron production. The time-resolved CE is based on the measured time-resolved hard x-ray emission [35] in the photon energy range between 50 and 100 keV. It is assumed that the instantaneous amount of hot electrons is proportional to the instantaneous hard x-ray emission and that the time-integrated CE equals the measured time-integrated values [see Fig. 2(b)]. The CE reached 13±2% and 4±1% in CH and C, respectively, during the second half of the high-intensity pulse, while the time-integrated CE over the entire pulse, including the laser energy when no hot electrons were generated, yielded 9±1% and 3±1%, respectively, for these shots.

Plasma parameters such as the electron temperature (T e ) and the density scale length (L) play an important role in the development of LPI. Table I provides the relevant coronal plasma parameters from LILAC simulations of the different materials at the n c /4 position and the calculated threshold intensities for TPD and SRS. Slight differences in the plasma parameters and the calculated threshold intensities are observed between materials. First, threshold intensities for SRS are about a factor of 2 lower than for TPD for all materials, which explains why SRS is the dominant hot-electron production mechanism at these high T e 's. Second, SRS thresholds are the same, which suggests that from a hydrodynamic point of view, no difference in hot-electron production for different materials is expected. This is in contrast to the experiment and points to a different cause. Coronal conditions of a full-scale SI target have been calculated at the n c /4 point for a polar-driven shock-ignition design for the National Ignition Facility [13]. At the peak of the laser spike values of T e = 8.5 keV and L = 450 um were calculated, which show that in the OMEGA experiment the temperatures are a factor of ∼2 lower and L is a factor of ∼4 shorter compared to an ignition target. Cross-beam energy transfer (CBET) can limit the ablation pressure in direct-drive implosions. CBET depends on such parameters as the laser spot size relative to the target size, the spectrum of the laser beams, and the damping of ion-acoustic waves (IAW's). Experiments with imploding thin CH shells on OMEGA at an intensity of 5×10 14 W/cm 2 studied the effect of the beam size for ratios of laser-spot radius to target radius from R = 1.1 to 0.5 (Ref. [36]). The experiments reported here employed solid targets with R = 1 for SSD on and R = 0.85 for SSD off, assuming an average of the major and minor axes of the elliptical focus profiles and a standard target radius of 215 µm. Based on the smaller ratio for SSD off, we would expect a reduction in CBET and a corresponding increase in hydrodynamic efficiency. The experiments indicate that the variation in beam size due to SSD does not play a role. With the exception of CH, which has the highest hot-electron production, the flash time [see Fig. 2(a)] is not influenced by SSD. SSD increased the spectral bandwidth to ∼1 Å. Previous experiments and simulations indicate that this width is not sufficient to affect CBET [37]. The damping rates are significantly higher in CH than in C (see below); therefore CBET should be less effective in CH. Although it cannot be ruled out that CBET mitigation does play a role in CH, the increased coupled drive energy in CH is believed to be mainly the result of an increased coupling of hot electrons. It has been demonstrated in Ref. [17] that hot electrons with a total energy of ∼2 kJ play an important role in the shock formation in these experiments. Note that the total internal and kinetic energy supplied to the imploding target is ∼0.6 kJ (∼5% hydroefficiency). Therefore ∼2 kJ of hot-electron energy is sufficient to significantly affect the target dynamics. The experiments demonstrate significant differences between CH and C, indicating that the H species plays an important role in the LPI. Other experiments that are relevant for indirect drive using low-density (n e /n c ∼ 0.1), high-Z Xe plasmas that were doped with low-Z impurity (C 5 H 12 ) have demonstrated an enhanced SRS reflectivity with higher impurity concentration [38,39]. The increased SRS reflectivity has been linked to an increased damping of IAW's, which is especially high for plasmas containing H [40]; however, no hot-electron measurements were reported [38][39][40]. To elucidate the SRS physics of this experiment, 2-D particle-in-cell (PIC) simulations were performed using the code OSIRIS [START_REF] Fonseca | Computational Science -ICCS 2002[END_REF] by comparing simulations with and without H in the vicinity of n c /4. A simulation with CH was compared to one where H was removed in the vicinity of n c /4 (n e > 0.2 n c ). These simulations were designed to identify differences in the fundamental physics of SRS caused by the presence of H. A boundary with matched density between CH in the underdense region and pure C in the higherdensity region ensured that equal conditions are created for the laser pulse propagating through the underdense plasma. The input parameters were obtained from a radiation-hydrodynamics simulation for a CH shot evaluated at 1.5 ns, when peak hot-electron production was observed. The PIC simulations assumed the same initial plasma parameters. The input thermal electron and ion temperatures were T e = 4 keV and T i = 0.8 keV, respectively, and the plasma density ramped linearly from 0.12 n c to 0.30 n c with L = 123 µm. A plane-wave (λ = 351 nm) laser pulse propagated along the x axis with a nominal intensity of 2.6×10 15 W/cm 2 (the same intensity as at n c /4 in the implosion), assuming flattop profiles in both time and space. The effect of SSD was not taken into account in the simulation.

Figures 4(a) and 4(b) show the calculated longitudinal electric-field strength from EPW versus time and laser propagation direction for C and CH, respectively. Distinct differences in the fields are observed. The electromagnetic wave excites strong EPW over a large region in CH compared to C. The wave modes survive longer in CH and couple better with thermal electrons because of a larger k vector. Determined by the phase-matching condition and the dispersion relations, the EPW's at the lower-density region have larger k. These large-k modes can accelerate thermal electrons more efficiently since their phase velocity is closer to the electron thermal velocity than the small-k modes close to n c /4 (Ref. [42]). Figures 4(c) and 4(d) compare the calculated signal level of IAW's, showing a stronger damping in CH compared to C because of the presence of light H ions. The Landau damping rates [43] were calculated for plasma conditions T e = 4 keV, T i = 0.8 keV, k=2k 0 for CH and C, where k and k 0 are the absolute values of the IAW and the laser wave vectors. At 0.25n c , γ = 7.4 × 10 -4 ω 0 (CH) and γ = 2.2 × 10 -5 ω 0 (C), where ω 0 is the laser frequency, while for a lower density of 0.12n c the calculations yield γ = 5.8 × 10 -4 ω 0 (CH) and γ = 1.9 × 10 -5 ω 0 (C). Damping from ion-electron collisions is negligible. This shows that the IAW damping rate in CH is ∼30× of that in C. The calculated CE's from the PIC simulations were 12% and 2% for CH and C, respectively, accounting for electrons with kinetic energy > 50 keV. A likely explanation is that the SRS saturation level is controlled by the secondary parametric decay of the driven EPW or its collapse, similar to the observations reported in Refs. [38,39]. The secondary parametric decay has been discussed in many papers; the experimental demonstration was reported in Ref. [44]. The threshold of the parametric decay is proportional to the IAW damping rate. In the case of a high IAW damping (with H), the threshold is higher and the EPW amplitude can grow to higher level, producing a stronger SRS signal and a larger number of hot electrons.

In conclusion, experiments were performed with CH, Be, C, and SiO 2 ablators at SI-relevant laser intensities. We observed peculiar differences in the hot-electron production and the shock formation and found that CH produced the largest amount of hot electrons and the strongest shocks. Supporting PIC simulations show that the strong damping of IAW's in the CH plasma causes an increased growth of EPWs and hot-electron produc-tion. In contrast to other work [19], which showed that Be ablators are the preferred choice at much lower laser intensity in a regime that is applicable to the standard hot-spot-ignition scheme, we found that among the four investigated materials, Be is the least efficient for SI since it produced the lowest effective ablation pressure inferred from shock velocities at the incident laser intensity of 5×10 15 W/cm 2 . The results demonstrate that the ablator material plays an important role in the energy coupling of the spike pulse and must be carefully considered in the design of ignition-relevant targets. This report was prepared as an account of work sponsored by an agency of the U.S. Government. Neither the U.S. Government nor any agency thereof, nor any of their employees, makes any warranty, express or implied, or assumes any legal liability or responsibility for the accuracy, completeness, or usefulness of any information, apparatus, product, or process disclosed, or represents that its use would not infringe privately owned rights. Reference herein to any specific commercial product, process, or service by trade name, trademark, manufacturer, or otherwise does not necessarily constitute or imply its endorsement, recommendation, or favoring by the U.S. Government or any agency thereof. The views and opinions of authors expressed herein do not necessarily state or reflect those of the U.S. Government or any agency thereof.

FIG. 1 .

 1 FIG. 1. (a) Target design consisting of an outer ablator layer of various materials and an inner Ti-doped plastic core; (b) pulse shape.

FIG. 2 .

 2 FIG. 2. (a) X-ray flash time for different ablators with smoothing by spectral dispersion (SSD) on (squares) and SSD off (circles); (b) measured time-integrated conversion efficiency (CE) of laser energy into hot-electron energy; (c) stimulated Raman scattering (SRS) backscatter signal, and (d) ω/2 signal.

FIG. 3 .

 3 FIG. 3. (a) Inferred effective maximum ablation pressures for the various materials for an incident laser intensity of 5×10 15 W/cm 2 . (b) Inferred time-resolved CE (red) and laser pulse shapes (black) for two shots with CH (solid curves, shot 73648) and C (dashed curves, shot 73645). Both shots were taken with SSD off. The time resolution of CE is ∼100 ps.

FIG. 4 .

 4 FIG. 4. Calculated longitudinal electric-field strength versus time and space (laser propagates from left to right) for (a) C and (b) CH and calculated ion-acoustic wave level for (c) C and (d) CH. The quantities were averaged over the transversal space coordinate and rendered on a logarithmic scale. The C simulation used a CH layer in the underdense portion, and the pure C layer starts at x = 30 µm.

  This work was supported by the DOE NNSA under awards No. DE-NA0001944 and DE-FC02-04ER54789, the Laboratory Basic Science Program, the University of Rochester, and the New York State Energy Research and Development Authority. We acknowledge the OSIRIS Consortium for the use of OSIRIS. R.Y. acknowledges support by the Science Challenge Project of China (No. JCKY2016212A501, No. JCKY2016212A505). Part of this work has been carried out within the framework of the EUROfusion Consortium and has received funding from the European Union's Horizon 2020 research and innovation program under grant agreement No. 633053.

  SSD off)], and Be [0.56±0.04 for both]. Energy conservation requires that E L = E abs + E 351 + E SRS + E h , where E abs is the absorbed energy in the plasma, E SRS is the SRS backscattered energy, and E h is the hot electron energy. E SRS was not measured, but one can argue that it msut be roughly equal to E h . Assuming E SRS = E h , the absorbed energy is

	[Fig. 2(d)].
	The quantity α was measured for the different ab-
	lators. CH produced the highest α [0.62±0.04 (SSD
	on), 0.71±0.03 (SSD off)] followed by SiO 2 [0.60±0.04
	(SSD on), 0.61±0.04 (SSD off)], C [0.60±0.04 (SSD on),
	0.63±0.04 (

2(c)

]. Switching SSD on significantly decreases the SRS signal in all ablators, potentially the result of the suppression of beam filamentation. The detected SRS wavelengths range from ∼560 to ∼680 nm, indicating that SRS is produced in a plasma region between 0.07 n e /n c and 0.20 n e /n c , where n e is the electron density and n c is the critical density for 351nm light. No absolute measurement of the SRS backscatter was available for these shots because of a calibration issue with the diagnostic. The weaker optical emission generated by electron plasma waves (EPW's) with half the laser frequency (ω/2) increases monotonically with Z

* wthe@lle.rochester.edu † On leave from Research Center of Laser Fusion, China Academy of Engineering Physics, Mianyang, Peoples Republic of China