Nicolas Haupaix

Philip B Abitua

Cathy Sirour

Hitoyoshi Yasuo

Michael Levine

Clare Hudson
email: hudson@obs-vlfr.fr

Claudia Racioppi

Ashwani K Kamal

Florian Razy-Krajka

Gennaro Gambardella

Laura Zanetti

Diego Di Bernardo

Remo Sanges

Lionel A Christiaen

Ephrin-mediated restriction of ERK1/2 activity delimits the number of pigment cells in the Ciona CNS

Keywords: melanocyte, pigment cell, ascidian, neural crest, oriented cell division

Recent evidence suggests that ascidian pigment cells are related to neural crest-derived melanocytes of vertebrates. Using live-imaging, we determine a revised cell lineage of the pigment cells in Ciona intestinalis embryos. The neural precursors undergo successive rounds of anterior-posterior (A-P) oriented cell divisions, starting at the blastula 64-cell stage. A previously unrecognized fourth A-P oriented cell division in the pigment cell lineage leads to the generation of the post-mitotic pigment cell precursors. We provide evidence that MEK/ERK signals are required for pigment cell specification until approximately 30 minutes after the final cell division has taken place. Following each of the four A-P oriented cell divisions, ERK1/2 is differentially activated in the posterior sister cells, into which the pigment cell lineage segregates. Eph/ephrin signals are critical during the third A-P oriented cell division to spatially restrict ERK1/2 activation to the posterior daughter cell. Targeted inhibition of Eph/ephrin signals results in, at neurula stages, anterior expansion of both ERK1/2 activation and a pigment cell lineage marker and subsequently, at larval stages, supernumerary pigment cells. We discuss the implications of these findings with respect to the evolution of the vertebrate neural crest.

Introduction

The ascidian pigment cells form part of the ocellus and the otolith, light and gravity sensing organs, respectively [START_REF] Jiang | Pigmentation in the sensory organs of the ascidian larva is essential for normal behavior[END_REF][START_REF] Tsuda | Direct evidence for the role of pigment cells in the brain of ascidian larvae by laser ablation[END_REF]. Previously, the ascidian pigment cells have been proposed as the evolutionary precursors of the vertebrate retinal pigment epithelium or pineal organ, based on expression of gene markers and the probable function of the ocellus pigment cell in shielding the photoreceptors [START_REF] Lamb | Evolution of the vertebrate eye: opsins, photoreceptors, retina and eye cup[END_REF][START_REF] Sato | Development of pigment cells in the brain of ascidian tadpole larvae: insights into the origins of vertebrate pigment cells[END_REF]. However, recent evidence using a larger panel of genes supports a closer evolutionary relationship to the cephalic neural crest of vertebrates [START_REF] Abitua | Identification of a rudimentary neural crest in a nonvertebrate chordate[END_REF][START_REF] Ivashkin | Progenitors of the protochordate ocellus as an evolutionary origin of the neural crest[END_REF]. This hypothesis is strengthened by the acquisition of migratory properties upon the misexpression of Twist, a cell behavior exhibited by neural crest.

Of the four founder embryonic lineages of Ciona (A-and B-of the vegetal hemisphere and a-and b-of the animal hemisphere), the central nervous system (CNS) derives from three lineages, A-, a-and b- [START_REF] Nishida | Cell lineage analysis in ascidian embryos by intracellular injection of a tracer enzyme. III. Up to the tissue restricted stage[END_REF]. This study is concerned with the a-line neural lineages, from which the pigment cells arise. At the 64-to 76-cell stage, the a-line neural lineages form one row of six cells (Fig. 1) [START_REF] Lemaire | Early steps in the formation of neural tissue in ascidian embryos[END_REF]. These cells then divide twice along the anterior-posterior axis to generate four rows of six cells at the 6-row neural plate stage (Fig. 1). The 6-row neural plate is arranged with row I posterior-most and row VI anterior-most [START_REF] Nicol | Development of the central nervous system of the larva of the ascidian, Ciona intestinalis L. I. The early lineages of the neural plate[END_REF]. The a-line cells comprise rows III-VI (pink cells in Fig. 1) and the A-line cells, rows I and II. Of the a-line cells, only rows III and IV will undergo neurulation and contribute to the CNS. These two rows generate the anterior part of the sensory vesicle, which is the ascidian larval brain, and also contribute to the oral siphon primordium [START_REF] Christiaen | Evolutionary modification of mouth position in deuterostomes[END_REF][START_REF] Cole | The central nervous system of the ascidian larva: mitotic history of cells forming the neural tube in late embryonic Ciona intestinalis[END_REF][START_REF] Nishida | Cell lineage analysis in ascidian embryos by intracellular injection of a tracer enzyme. III. Up to the tissue restricted stage[END_REF][START_REF] Taniguchi | Tracing cell fate in brain formation during embryogenesis of the ascidian Halocynthia roretzi[END_REF][START_REF] Veeman | The ascidian mouth opening is derived from the anterior neuropore: reassessing the mouth/neural tube relationship in chordate evolution[END_REF]. The anterior two rows, V and VI, generate the palps, an adhesive organ, as well as non-neural ectoderm. The pigment cell lineage is situated in the lateral-most cell of row III. Between the 6-row neural plate and the 12-row neurula stages, each row of cells divides in a specific sequence, with row II cells dividing first, followed by row I, then row III and V and lastly row IV and VI [START_REF] Nicol | Development of the central nervous system of the larva of the ascidian, Ciona intestinalis L. I. The early lineages of the neural plate[END_REF]. In each row, cells in the medial four columns divide prior to those in the lateral columns. At the 12-row neural plate stage, the pigment cell lineage is segregated into the posterior row III (IIIp) cell, a10.97. As we will describe in this manuscript, the a10.97 pigment cell precursors undergo a further and final round of cell division along the anterior-posterior axis, whereby the posterior-positioned daughters, a11.193, intercalate at the midline to become the pigment cells of the otolith and ocellus.

FGFs are secreted ligands that bind to a class of receptor tyrosine kinases, the FGF receptors (FGFRs), and predominantly activate the Ras/MEK/ERK cascade. FGF/ERK signaling is implicated in a vast range of processes during vertebrate neural development including the induction of neural crest [START_REF] Guillemot | From cradle to grave: the multiple roles of fibroblast growth factors in neural development[END_REF][START_REF] Hébert | FGFs: Neurodevelopment's Jack-of-all-Trades -How Do They Do it?[END_REF][START_REF] Stuhlmiller | FGF/MAPK signaling is required in the gastrula epiblast for avian neural crest induction[END_REF]. During ascidian neural development, FGF/ERK signaling is responsible for the specification of different cell types. It is involved in the process of neural induction of a-line neural lineages at the 32-cell stage [START_REF] Bertrand | Neural tissue in ascidian embryos is induced by FGF9/16/20, acting via a combination of maternal GATA and Ets transcription factors[END_REF] and later during patterning of the developing neural plate and neural tube [START_REF] Abitua | Identification of a rudimentary neural crest in a nonvertebrate chordate[END_REF][START_REF] Hudson | A conserved role for the MEK signalling pathway in neural tissue specification and posteriorisation in the invertebrate chordate, the ascidian Ciona intestinalis[END_REF][START_REF] Hudson | Sequential and combinatorial inputs from Nodal, Delta2/Notch and FGF/MEK/ERK signalling pathways establish a grid-like organisation of distinct cell identities in the ascidian neural plate[END_REF][START_REF] Squarzoni | FGF/MAPK/Ets signaling renders pigment cell precursors competent to respond to Wnt signal by directly controlling Ci-Tcf transcription[END_REF][START_REF] Stolfi | Neural tube patterning by Ephrin, FGF and Notch signaling relays[END_REF][START_REF] Wagner | FGF signaling establishes the anterior border of the Ciona neural tube[END_REF]. Recently, Eph/ephrin signaling via RasGAP has been shown to limit the spatial extent of activation of ERK1/2 during several developmental cell fate choices in Ciona embryos including during neural development [START_REF] Haupaix | p120RasGAP mediates ephrin/Eph-dependent attenuation of FGF/ERK signals during cell fate specification in ascidian embryos[END_REF][START_REF] Ohta | Multiple signaling pathways coordinate to induce a threshold response in a chordate embryo[END_REF][START_REF] Picco | Ephrin-Eph signalling drives the asymmetric division of notochord/ neural precursors in Ciona embryos[END_REF][START_REF] Shi | Ephrin signaling establishes asymmetric cell fates in an endomesoderm lineage of the Ciona embryo[END_REF][START_REF] Stolfi | Neural tube patterning by Ephrin, FGF and Notch signaling relays[END_REF]. Here we investigated the role of Eph/ephrin signaling and the MEK/ERK pathway during pigment cell specification at neural plate stages of Ciona intestinalis development.

Materials and Methods

Embryo experiments and constructs

Adult Ciona intestinalis were purchased from the Station Biologique de Roscoff (France) or M-Rep (San Diego, CA). Cell nomenclature, lineage and the fate maps are previously described [START_REF] Cole | The central nervous system of the ascidian larva: mitotic history of cells forming the neural tube in late embryonic Ciona intestinalis[END_REF][START_REF] Conklin | The organisation and cell lineage of the ascidian egg[END_REF][START_REF] Nishida | Cell lineage analysis in ascidian embryos by intracellular injection of a tracer enzyme. III. Up to the tissue restricted stage[END_REF]. Ascidian embryo culture has been described [START_REF] Sardet | Embryological methods in ascidians: the Villefranche-sur-Mer protocols[END_REF]. Electroporation was carried out as described [START_REF] Christiaen | Electroporation of transgenic DNAs in the sea squirt Ciona[END_REF]. U0126 (Calbiochem) was added to artificial seawater at 2μM. All data was pooled from at least two independent experiments.

For the electroporation constructs, the upstream sequences ZicL, Tyr, Mitf, Dmrt, Msx and Fog are previously described [START_REF] Abitua | Identification of a rudimentary neural crest in a nonvertebrate chordate[END_REF][START_REF] Haupaix | p120RasGAP mediates ephrin/Eph-dependent attenuation of FGF/ERK signals during cell fate specification in ascidian embryos[END_REF][START_REF] Rothbächer | A combinatorial code of maternal GATA, Ets and beta-catenin-TCF transcription factors specifies and patterns the early ascidian ectoderm[END_REF][START_REF] Wagner | FGF signaling establishes the anterior border of the Ciona neural tube[END_REF]. These were used to drive expression of LacZ, mCherry, Eph1ΔC, Histone 2B (H2B), unc76GFP, Eph3ΔC, RG(R818E) [START_REF] Abitua | Identification of a rudimentary neural crest in a nonvertebrate chordate[END_REF][START_REF] Haupaix | p120RasGAP mediates ephrin/Eph-dependent attenuation of FGF/ERK signals during cell fate specification in ascidian embryos[END_REF][START_REF] Hudson | Sequential and combinatorial inputs from Nodal, Delta2/Notch and FGF/MEK/ERK signalling pathways establish a grid-like organisation of distinct cell identities in the ascidian neural plate[END_REF][START_REF] Stolfi | Neural tube patterning by Ephrin, FGF and Notch signaling relays[END_REF][START_REF] Wagner | FGF signaling establishes the anterior border of the Ciona neural tube[END_REF]. Following electroporation, embryos were selected at gastrula stages for correct morphology. In Figure 3, Dmrt∷Eph3ΔC electroporated embryos were co-electroporated with Trp∷mCherry. Only fluorescent (i.e. electroporated) embryos were counted for this experiment, in all other experiments, all embryos were counted. In order to assess ocellus and otolith pigment cell type, embryos were mounted in 80% glycerol and slightly compressed. Ocellus type or otolith type pigment cells were defined based on pigment granule morphology; such that tiny dispersed granules were defined as ocellus type and larger, round or flower shaped granules were defined as otolith. The number of ocellus type pigment cells was likely underestimated since it was more difficult to distinguish individual ocelli from one another. In both control and electroporated embryos, even very large ocelli were counted as one.

In situ hybridization and immunofluorescence

In situ hybridization was carried out as previously described [START_REF] Hudson | β-Catenin-Driven Binary Fate Specification Segregates Germ Layers in Ascidian Embryos[END_REF]. Diglabeled probes were synthesized from the following Ciona cDNA clones: Trp [START_REF] Hudson | A conserved role for the MEK signalling pathway in neural tissue specification and posteriorisation in the invertebrate chordate, the ascidian Ciona intestinalis[END_REF], FoxC (cilv050a24) [START_REF] Imai | Gene expression profiles of transcription factors and signaling molecules in the ascidian embryo: towards a comprehensive understanding of gene networks[END_REF], ZicL (cicl002e04) (Imai et al., 2002b), Mitf (cilv41b12) [START_REF] Abitua | Identification of a rudimentary neural crest in a nonvertebrate chordate[END_REF]. Six3/6 (cicl021e08), Dll-B (cicl022f04), ephrinAc (ciad074h16), ephrinAb (cieg037l08), ephrinAd (ciad008n17), Eph3 (cieg009e01), FgfR (citb040h06), Fgf9/16/20 (citb007k01) and Fgf8/17/18 (citb002j04) are all described [START_REF] Imai | Gene expression profiles of transcription factors and signaling molecules in the ascidian embryo: towards a comprehensive understanding of gene networks[END_REF]. Clone numbers refer to clones from the 'Release 1 Gene Collection Plates' [START_REF] Satou | A cDNA resource from the basal chordate Ciona intestinalis[END_REF]. For Dll-B in situ hybridization, DAPI staining was used to verify cell identity. In some batches of embryos, Dll-B was also detected in row IV. These batches of embryos were removed from the analysis. For Trp in situ hybridization in Figure 5, it should be noted that the intensity of the Trp signal increases with developmental time. At the 6-row neural plate stage, the color reaction was developed for approximately 12 hours, whereas at the early tailbud stage, the color reaction time was 1 to 3 hours. dpERK1/2 immunofluorescence is described previously [START_REF] Haupaix | p120RasGAP mediates ephrin/Eph-dependent attenuation of FGF/ERK signals during cell fate specification in ascidian embryos[END_REF]. LacZ immunofluorescence is described previously [START_REF] Stolfi | Neural tube patterning by Ephrin, FGF and Notch signaling relays[END_REF] except that anti-βgalactosidase (Molecular Probes, A11132) was used at 1/500 and the secondary antibody used was goat anti-rabbit Alexa Fluor 488 (Molecular Probes, A11008) at 1/1000.

In our analysis, we refer to embryos as the 6-row neural plate stage to indicate that no row of a-line cells has divided, though cells in row II have sometimes divided. We refer to the 12row neurula stage to indicate that row III cells have divided. Embryos in Figs. 2,6 and Supplementary Fig. 1 were mounted in VECTASHIELD/DAPI (Vector Laboratories). Embryos in Figs. 2,5,6,7 and Supplementary figures were photographed on an Olympus BX51 using Leica DFC310FX camera and those in Figs. 3 and4G on a Zeiss Axio Imager AZ using a SPOT RT3 camera.

Time-lapse movie

The time-lapse sequence was obtained using a Zeiss LSM 700 microscope using a planapochromat 20x objective. Confocal stacks contained 20 optical slices at a thickness of approximately 1μm each and were taken every 3 minutes for 2 hours. Images were rendered in 3D using Volocity 6 with the 3D opacity visualization tool.

Results

Differential activation of ERK1/2 in the neural plate is required for patterning along the A-P axis

It has previously been shown that differential ERK1/2 activity between rows III/IV (CNS) and V/VI (palp) at the 3-row neural plate stage (Fig. 1) accounts for acquisition of their distinct genetic programs [START_REF] Wagner | FGF signaling establishes the anterior border of the Ciona neural tube[END_REF]. ERK1/2 is subsequently differentially activated between rows III and IV at the 6-row neural plate stage with ERK1/2 active in row III cells (Fig. 2A) [START_REF] Hudson | Sequential and combinatorial inputs from Nodal, Delta2/Notch and FGF/MEK/ERK signalling pathways establish a grid-like organisation of distinct cell identities in the ascidian neural plate[END_REF]. This pattern of ERK1/2 activation is required for the differential fate specification of these two sister rows (Fig. 2C). We inhibited MEK/ERK signal transduction by applying U0126, an inhibitor of the MAP kinase kinase, MEK1/2, at precise developmental time points. The following markers were used to assess neural plate patterning: FoxC (rows V and VI), Dll-B (epidermis and rows V and VI), ZicL (rows III and IV), Six3/6 (row IV), Mitf and Trp (row III) [START_REF] Abitua | Identification of a rudimentary neural crest in a nonvertebrate chordate[END_REF][START_REF] Irvine | Non-overlapping expression patterns of the clustered Dll-A/B genes in the ascidian Ciona intestinalis[END_REF][START_REF] Wagner | FGF signaling establishes the anterior border of the Ciona neural tube[END_REF]. As reported previously, application of U0126 at the 76-cell stage disrupts the choice between row III/IV and row V/VI fates [START_REF] Wagner | FGF signaling establishes the anterior border of the Ciona neural tube[END_REF]. Genes expressed in rows III and IV (ZicL, Six3/6, Trp and Mitf) were lost and genes normally restricted to rows V and VI (FoxC and Dll-B) were ectopically expressed in rows III and IV (Fig. 2B andC). In contrast, application of U0126 after the separation of rows III/IV and V/VI, at the early gastrula 3-row neural plate stage (approximate stage 11+ [START_REF] Hotta | A web-based interactive developmental table for the ascidian Ciona intestinalis, including 3D real-image embryo reconstructions: I. From fertilized egg to hatching larva[END_REF]), resulted in loss of row III gene expression (Trp, Mitf) and ectopic expression of the row IV gene, Six3/6, in row III. Thus, inhibition of MEK1/2 signals at these two successive time points results, in each case, in a distinct posterior to anterior fate transformation of sister cells. In the first instance, differential activation of ERK1/2 specifies row III/IV over V/VI fate and then, following division of row III/IV cells, it promotes row III over row IV fates.

Eph/ephrin signals are not required for neural plate patterning at the 3-and 6-row neural plate stages

There are several examples during Ciona embryogenesis whereby Eph/ephrin signals control the spatial extent of ERK1/2 activation [START_REF] Haupaix | p120RasGAP mediates ephrin/Eph-dependent attenuation of FGF/ERK signals during cell fate specification in ascidian embryos[END_REF][START_REF] Ohta | Multiple signaling pathways coordinate to induce a threshold response in a chordate embryo[END_REF][START_REF] Picco | Ephrin-Eph signalling drives the asymmetric division of notochord/ neural precursors in Ciona embryos[END_REF][START_REF] Shi | Ephrin signaling establishes asymmetric cell fates in an endomesoderm lineage of the Ciona embryo[END_REF][START_REF] Stolfi | Neural tube patterning by Ephrin, FGF and Notch signaling relays[END_REF]. Three ephrin ligands are expressed in the neural lineages during neural plate and neurula stages and the receptor Eph3 is expressed ubiquitously, becoming upregulated in the pigment cell lineage soon after the 6-row neural plate stage (Supplementary Fig. 1) [START_REF] Imai | Gene expression profiles of transcription factors and signaling molecules in the ascidian embryo: towards a comprehensive understanding of gene networks[END_REF][START_REF] Tassy | The ANISEED database: digital representation, formalization, and elucidation of a chordate developmental program[END_REF]. These gene expression profiles suggest that Eph/ephrin signals could also be involved in the modification of ERK1/2 activity during neural plate patterning. In order to address this possibility, we expressed a dominant negative form of the Eph receptor Eph3, Eph3ΔC [START_REF] Picco | Ephrin-Eph signalling drives the asymmetric division of notochord/ neural precursors in Ciona embryos[END_REF], in the a-line neural lineages. For this, we used the Dmrt promoter which drives expression throughout the a-line neural lineages from the 64-cell stage and has previously been used to disrupt gene function at the 3-row neural plate stage [START_REF] Ikeda | A time delay gene circuit is required for palp formation in the ascidian embryo[END_REF][START_REF] Wagner | FGF signaling establishes the anterior border of the Ciona neural tube[END_REF]. Following electroporation of Dmrt∷Eph3ΔC, we observed that expression of FoxC, Dll-B, ZicL, Six3/6, Mitf and Trp were unaffected at the 6-row stage neural plate stage (Fig. 2B andC). Consistently, the spatial pattern of ERK1/2 activation at the 6-row neural plate stage was not perturbed in these embryos (Fig. 2A). We conclude that Eph/ephrin signals are not required to generate the spatial pattern of ERK1/2 activation in the neural plate during the 3-row or 6-row neural plate stages. A similar conclusion was reached analyzing embryos electroporated with an early-active promoter, Fog, to drive Eph3ΔC in all ectodermal cells from the 16-cell stage [START_REF] Rothbächer | A combinatorial code of maternal GATA, Ets and beta-catenin-TCF transcription factors specifies and patterns the early ascidian ectoderm[END_REF] (Supplementary Fig. 2).

An extra cell division in the pigment cell lineage

Despite little effect on the neural plate genes analyzed, we consistently observed ectopic formation of pigment cells in larvae resulting from embryos electroporated with Dmrt∷Eph3ΔC (Fig. 3). In some cases, five or more pigment cells could be observed. This result suggests that Eph/ephrin signals play a role in neural patterning. We thus set out to understand how Eph/ephrin signals are involved in this process.

In order to study the role of Eph/ephrin signals in pigment cell formation, we first observed the pigment cell lineage in detail, revealing a previously unrecognized cell division (Fig. 4; Supplementary movie 1). We analyzed the time-lapse sequence of embryos electroporated with Dmrt∷H2BYFP (Histone 2B fused with YFP, magenta in images) to label rows III through VI and ZicL∷H2BCFP (green in images) to label rows I through IV. These reporters are thus co-expressed in rows III and IV allowing for the delineation of cell lineages. Analyzing the time-lapse sequence revealed a further cell division of the a10.97 cell, which was previously described as a postmitotic pigment cell precursor [START_REF] Cole | The central nervous system of the ascidian larva: mitotic history of cells forming the neural tube in late embryonic Ciona intestinalis[END_REF][START_REF] Whittaker | Quantitative control of end products in the melanocyte lineage of the ascidian embryo[END_REF]. The pigment cell lineage and cell positions in the neural tube are thus modified to account for this additional division (Fig. 4G). We also recognized this extra division by analyzing Trp expression every 15 minutes from the 6-row neural plate stage until the early tailbud stage (Fig. 5A-H). Trp expression begins at the 6-row neural plate stage in a9.49 (Fig. 5A). Following cell division of a9.49, Trp expression is observed in both daughter cells, but rapidly becomes stronger in the posterior-positioned a10.97 compared to its anterior sister cell, a10.98 (Fig. 5B-D). Next, a10.97 divides into a11.194 and a11.193, both cells retain Trp expression and converge towards the midline (Figs. 4D and5E), touch (Figs. 4E and5F) and begin to intercalate (Fig. 5G). Finally these cells are positioned with the two smaller a11.194 cells side by side anterior to the two larger a11.193 pigment cell precursors intercalated at the midline (Fig. 4F andG; Supplementary movie 1).

MEK1/2 activity is required until approximately 30 minutes after the final division in the pigment cell lineage

Since patterning of the 6-row neural plate was not affected by inhibition of Eph/ephrin signaling (Fig. 2; Supplementary Fig. 2), we hypothesized that the supernumerary pigment cells observed following inhibition of Eph/ephrin signals resulted from a failure to control the spatial extent of ERK1/2 activation after the 6-row neural plate stage. We first analyzed precisely when pigment cell specification is dependent on MEK/ERK signals. We applied U0126 to embryos every 15 minutes from the 6-row neural plate stage to the early tailbud stage, when pigment cell formation has been shown to occur independently of MEK1/2 signaling [START_REF] Squarzoni | FGF/MAPK/Ets signaling renders pigment cell precursors competent to respond to Wnt signal by directly controlling Ci-Tcf transcription[END_REF]. We monitored the precise developmental stage at which embryos were placed in U0126 by analyzing a sample of embryos at each time point for Trp expression (Fig. 5A-I). We then assessed the presence of pigmented cells in resultant larvae (Fig. 5J). This analysis shows that pigment cell formation requires MEK1/2 signaling until approximately 30 minutes after the pigment cell lineage has undergone its final cell division (corresponding approximately to the embryonic stage shown in Fig. 5G). Following this time point, U0126-treatment had little effect on specification of pigment cells, albeit their pigmentation was somewhat reduced.

ERK1/2 is activated in the pigment cell lineage during neurulation

We showed that pigment cell specification requires an intact MEK1/2 signaling pathway until around 30 minutes after the final cell division of this lineage (Fig. 5). Consistent with a direct requirement for the pathway during pigment cell specification, we found that ERK1/2 remains active in the pigment cell lineage following the 6-row neural plate stage. When the neural plate consists of 12-rows of cells (in this analysis all row III cells and medial row IV cells had completed division), ERK1/2 activation was preferentially detected in the posterior daughters of rows III and IV (row IIIp and IVp) (Fig. 6A). At this stage, the pigment cell lineage is segregated into a10.97, the lateral-most cells of row IIIp (Figs. 1 and6A). At the early tailbud stage (corresponding to the stage in Fig. 5F), we observed higher ERK1/2 activity in a11.193, the posterior daughter of a10.97, compared to the anterior daughter a11.194 (Fig. 6D). Thus, ERK1/2 is continuously differentially activated in the pigment cell lineage following each successive A-P oriented cell division, consistent with an ongoing and direct requirement for MEK/ERK dependent signals for pigment cell specification (Figs. 5 and6).

Eph/ephrin signals restrict the spatial extent of ERK1/2 activation during the penultimate division of the pigment cell precursors

Differential ERK1/2 activity is involved in differential fate specification at both the 3-row and the 6-row neural plate stages (Fig. 2) [START_REF] Wagner | FGF signaling establishes the anterior border of the Ciona neural tube[END_REF]. We showed that Eph/ ephrin signals are not involved in the spatial control of ERK1/2 or neural plate patterning at these stages (Fig. 2; Supplementary Fig. 2). However, we found that Eph/ephrin signals are required to restrict the number of pigment cells (Fig. 3). We also found that ERK1/2 is continuously activated in the pigment cell lineage during neurulation, until the early tailbud stage (Fig. 5). Focusing on the 12-row neural plate stage, we found that Eph/ephrin signals are required to restrict ERK1/2 activation to the posterior daughter cells of row III and IV (row IIIp and row IVp) (Fig. 6B). In Dmrt∷Eph3ΔC-embryos, ERK1/2 activation was observed in both the anterior and posterior daughter cells of rows III and IV. This effect was particularly prominent in the pigment cell lineage with strong ectopic ERK1/2 activation in a10.98, the anterior sister cell of a10.97. Consistent with a critical role for Eph/ephrin signals in restricting pigment cell fate to the a10.97 lineage, we observed ectopic expression of Trp in a10.98 in Dmrt∷Eph3ΔC-embryos (Fig. 7). In these experiments, we also occasionally (3% of embryo halves) observed persistence of Trp expression in row IV cells. It is not clear to us why this happens, since we do not see ectopic expression of row III genes in row IV at the 6-row stage in Dmrt∷Eph3ΔC embryos. Similar results were obtained using Fog∷Eph3ΔC (Supplementary Fig. 2). Conversely, treatment of embryos with U0126 from the 6-row neural plate stage resulted in a strong reduction of Trp expression (Fig. 7). Thus, Eph/ephrin signals are required to restrict ERK1/2 activity at the 12-row neurula stage, but not at earlier stages (3-row and 6-row).

The spatial control of ERK1/2 activation by Eph/ephrin signals is mediated by p120RasGAP in Ciona [START_REF] Haupaix | p120RasGAP mediates ephrin/Eph-dependent attenuation of FGF/ERK signals during cell fate specification in ascidian embryos[END_REF]. This is also likely to be the case during pigment cell specification since electroporation of a dominant negative version of RasGAP, RG(R818E), resulted in a similar phenotype of supernumerary pigment cells in larvae and ectopic activation of ERK1/2 in 12-row neurula, but not 6-row neural plate stage embryos (Figs. 2A, 3 and 6C).

A role for Eph/ephrin at the 12-row stage is consistent with the formation of more than five pigmented cells that we frequently observed in Dmrt∷Eph3ΔC-larvae, since transformation of a10.98 into a a10.97-like fate should result in a pool of a maximum of eight Trp-positive cells instead of the usual four. The presence of more than four pigmented cells also suggests that the subsequent fate choice between a11.194 and a11.193 is also perturbed in many Dmrt∷Eph3ΔC-larvae.

Finally, we did not find any evidence that the choice between ocellus and otolith fates requires Eph/ephrin signals. In a pool of embryos electroporated with Dmrt∷Eph3ΔC, we counted an average of 1.5 otolith and 1.4 ocellus-type pigmented cells (n=299) compared to control embryos, which exhibited an average of 0.8 otolith and 1.2 ocellus-type pigment cells (n=324). The preferential increase in otolith-type pigment cells is consistent with a previous study where the ectopic activation of Ets results in extra pigments cells of the otolith-type. The choice between ocellus and otolith fate is governed by Wnt7, which serves as a positional cue for specifying the posterior ocellus pigment cell [START_REF] Abitua | Identification of a rudimentary neural crest in a nonvertebrate chordate[END_REF].

Discussion

We document an additional division of the pigment cell lineage, which was previously described to become post-mitotic following nine cell divisions after fertilization in Ciona [START_REF] Whittaker | Quantitative control of end products in the melanocyte lineage of the ascidian embryo[END_REF]. We found that disruption of Eph/ephrin signals results in supernumerary pigment cells in larvae. Our results show that ephrin/Eph/RasGAP signaling is required during the 12-row neural plate stage, but not at earlier neural plate stages, to restrict ERK1/2 activation to the posterior daughters of row III (IIIp, as well as row IVp). Removal of this control mechanism results in ectopic activation of ERK1/2 in row IIIa and ectopic Trp expression in a10.98.

Reiterative differential ERK1/2 associated with A-P oriented cell division in the developing nervous system

FGF/MEK/ERK-driven cell fate choices generate cell diversity at multiple steps during ascidian embryogenesis [START_REF] Bertrand | Neural tissue in ascidian embryos is induced by FGF9/16/20, acting via a combination of maternal GATA and Ets transcription factors[END_REF][START_REF] Davidson | FGF signaling delineates the cardiac progenitor field in the simple chordate, Ciona intestinalis[END_REF][START_REF] Hudson | A conserved role for the MEK signalling pathway in neural tissue specification and posteriorisation in the invertebrate chordate, the ascidian Ciona intestinalis[END_REF][START_REF] Hudson | Sequential and combinatorial inputs from Nodal, Delta2/Notch and FGF/MEK/ERK signalling pathways establish a grid-like organisation of distinct cell identities in the ascidian neural plate[END_REF]Imai et al., 2002a;[START_REF] Kim | Role of the FGF and MEK signaling pathway in the ascidian embryo[END_REF][START_REF] Picco | Ephrin-Eph signalling drives the asymmetric division of notochord/ neural precursors in Ciona embryos[END_REF][START_REF] Shi | Ephrin signaling establishes asymmetric cell fates in an endomesoderm lineage of the Ciona embryo[END_REF][START_REF] Shimauchi | FGF signals are involved in the differentiation of notochord cells and mesenchyme cells of the ascidian Halocynthia roretzi[END_REF][START_REF] Squarzoni | FGF/MAPK/Ets signaling renders pigment cell precursors competent to respond to Wnt signal by directly controlling Ci-Tcf transcription[END_REF][START_REF] Stolfi | Neural tube patterning by Ephrin, FGF and Notch signaling relays[END_REF][START_REF] Yasuo | FGF8/17/18 functions together with FGF9/16/20 during formation of the notochord in Ciona embryos[END_REF]. Even within the a-line neural lineage, there are many examples. At the 32cell stage, the a5.3 cell divides to produce the a6.6 cell and the a6.5 cell. The a6.5 cell exhibits ERK1/2 activation in response to the neural inducing FGF signal and adopts a neural fate while the a6.6 cell, with no ERK1/2 activation, adopts an epidermal fate [START_REF] Bertrand | Neural tissue in ascidian embryos is induced by FGF9/16/20, acting via a combination of maternal GATA and Ets transcription factors[END_REF][START_REF] Hudson | A conserved role for the MEK signalling pathway in neural tissue specification and posteriorisation in the invertebrate chordate, the ascidian Ciona intestinalis[END_REF]. Restriction of ERK1/2 activation to the neural precursor depends upon ephrin signals [START_REF] Ohta | Multiple signaling pathways coordinate to induce a threshold response in a chordate embryo[END_REF]. At this stage, a-line neural cells contain both CNS and palp lineages. These cells are prevented from precociously activating the CNSspecific program by a time delay mechanism involving a pair of Blimp1like zinc finger repressors [START_REF] Ikeda | A time delay gene circuit is required for palp formation in the ascidian embryo[END_REF]. From the 3-row neural plate stage, differential ERK1/2 activation is used repeatedly to specify the posterior-most cell fates during at least four successive rounds of A-P oriented cell divisions in the a-line neural lineages. During each division, the pigment cell lineage segregates into the posterior cells. At the 3-row neural plate stage, CNS lineages (row III/IV) segregate from palp lineages (row V/VI) with FGF/MEK/ERK promoting CNS over palp fate in row III/IV [START_REF] Wagner | FGF signaling establishes the anterior border of the Ciona neural tube[END_REF]. Differential activation of ERK1/2 between rows III/IV and V/VI may be achieved simply by the restricted expression of the inducing ligand, since Fgf9/16/20 is expressed in row I/II cells, adjacent to the row III/IV cells (Supplementary Fig. 1) [START_REF] Imai | Regulatory blueprint for a chordate embryo[END_REF]. At the 6row neural plate stage, ERK1/2 activation is restricted to row III of the a-line neural plate. Localized expression of FGF ligands (Fgf9/16/20 and Fgf8/17/18) in row II might also account for the differential activation of ERK1/2 between rows III and IV (Supplementary Fig. 1) [START_REF] Hudson | Sequential and combinatorial inputs from Nodal, Delta2/Notch and FGF/MEK/ERK signalling pathways establish a grid-like organisation of distinct cell identities in the ascidian neural plate[END_REF][START_REF] Squarzoni | FGF/MAPK/Ets signaling renders pigment cell precursors competent to respond to Wnt signal by directly controlling Ci-Tcf transcription[END_REF]. At this stage, differential ERK1/2 activation also drives the cell fate choices between row I and row II sister cells of the A-line neural plate with ERK1/2 activated in row I cells, though it is not clear how this differential activation pattern is established [START_REF] Hudson | Sequential and combinatorial inputs from Nodal, Delta2/Notch and FGF/MEK/ERK signalling pathways establish a grid-like organisation of distinct cell identities in the ascidian neural plate[END_REF].

Here we described an additional differential activation of ERK1/2 in row III and row IV derivatives following their division into rows IIIa, IIIp, IVa and IVp, whereby ERK1/2 activation is again associated with the posterior daughter cells in row IIIp and row IVp (Fig. 6). We show that ERK1/2 activation is spatially restricted to the posterior rows by Eph/ ephrin signals. This mechanism is unlikely to be confined to the pigment cell lineage choice between a10.97 and a10.98 fates, since ectopic ERK1/2 activation is seen broadly in rows IIIa and IVa following inhibition of Eph/ephrin signals. It is not yet clear which ephrin ligands are involved in this process. ephrin-Ad is expressed in rows V-VI from the 6-row neural plate stage and may therefore be involved in the restriction of ERK1/2 activity between rows IVa and IVp [START_REF] Wagner | FGF signaling establishes the anterior border of the Ciona neural tube[END_REF]) (Supplementary Fig. 1). ephrin-Ac and ephrin-Ab are expressed in discrete domains of the neural plate in close proximity to row III and thus might be involved in the spatial control of ERK1/2 activation between row IIIa and IIIp cells (Supplementary Fig. 1). Early in development the Eph3 receptor is expressed ubiquitously, then shortly after the 6-row stage it is upregulated in the pigment cell lineage. Interestingly, this upregulation depends on MEK/ERK signaling, suggesting that MEK/ERK signals render this cell lineage particularly sensitive to Eph/ephrin signals during subsequent stages (Supplementary Fig. 1). Based on ephrin and Fgf ligand and receptor expression profiles, it is unclear how such a precise spatial pattern of ERK1/2 activation is achieved at the 12-row neural plate stage. It is possible that other mechanisms are also involved, however our data show that Eph/ephrin plays an essential role in establishing this pattern (Figure 6).

Following the MEK/ERK-mediated specification of a10.97 as the pigment cell lineage, these cells divide into a11.194 and a11.193 and the posteriorly positioned a11.193 cells become pigmented. It is not yet clear how this fate choice between a non-pigmented and pigmented cell fate is achieved, although differential ERK1/2 may be involved since ERK1/2 is preferentially activated in a11.193. Differentially-expressed gene markers of a11.193 and a11.194 would be required to address this issue. To determine whether Eph/ephrin signals are directly involved will necessitate a means to block signaling specifically after the 12-row neural plate stage. The fact that five or more pigment cells are frequently observed in Dmrt∷Eph3ΔC larvae, suggests that this fate choice is also perturbed in this experimental context.

Finally, the two a11.193 cells from both sides of the neural plate intercalate at the midline and adopt either an ocellus or otolith fate. The post-mitotic pigment cell precursors have been shown to form an equivalence group in another ascidian species, Halocynthia roretzi. These cells intercalate at random and the posteriorly positioned cell adopts the ocellus fate [START_REF] Nishida | Cell lineage analysis in ascidian embryos by intracellular injection of a tracer enzyme. III. Up to the tissue restricted stage[END_REF][START_REF] Nishida | Determination and regulation in the pigment cell lineage of the ascidian embryo[END_REF]. We did not find any evidence that Eph/ephrin signals are involved in this final fate choice. In Ciona, this fate choice is controlled by Wnt7 signals, whereas BMP-Chordin antagonism has been implicated in Halocynthia [START_REF] Abitua | Identification of a rudimentary neural crest in a nonvertebrate chordate[END_REF][START_REF] Darras | The BMP/CHORDIN antagonism controls sensory pigment cell specification and differentiation in the ascidian embryo[END_REF].

If the pigment cell lineage resembles the evolutionary precursors of the vertebrate neural crest, it is relatively easy to envisage how these cell types could both increase in number and adopt a migratory capacity. Simple deregulation of signaling pathways leads to quite a dramatic increase in pigment cell number (Fig. 3) [START_REF] Abitua | Identification of a rudimentary neural crest in a nonvertebrate chordate[END_REF][START_REF] Squarzoni | FGF/MAPK/Ets signaling renders pigment cell precursors competent to respond to Wnt signal by directly controlling Ci-Tcf transcription[END_REF]. A subset of these cells would then need to acquire the expression of a mesenchymepromoting factor such as Twist in order for a primordial neural crest to develop [START_REF] Abitua | Identification of a rudimentary neural crest in a nonvertebrate chordate[END_REF]. [START_REF] Nicol | Development of the central nervous system of the larva of the ascidian, Ciona intestinalis L. I. The early lineages of the neural plate[END_REF]. The 6-row neural plate then divide in an asynchronous but predictable order (see text for details) to produce 12rows of neural plate cells in neurula embryos. At this stage the pigment cell lineage is positioned in the lateral column in row IIIp. This cell undergoes one final division to produce a11.194 and a11.193 prior to their intercalation at the midline (see also Supplementary movie 1 and Fig. 4). A-C) Experimental conditions are indicated on the top panels. Embryos were stained for activated ERK1/2 (dpERK1/2) in red, with nuclei (DAPI) in white. For this analysis embryos were also co-electroporated with Msx∷LacZ or Dmrt∷LacZ followed by LacZ immunofluorescence to ensure our cell identification was correct (not shown). The top panel shows the entire embryo and the bracket indicates the annotated region in the lower panels. The divided rows III and IV are outlined in white and yellow respectively in the middle panel. At the stage of analysis, the lateral precursors of row IV have not yet divided. In the lower panel, only the dpERK immunofluorescence is shown for clarity. The interpretation of the dpERK immunofluorescence intensity is depicted by red and pink dots on the schematic of divided rows III and IV. The percentage of dpERK1/2 detection in each cell of row IIIa and IIIp is indicated on the lower schematic, representing independent scoring for each embryo half. n= number of half embryos scored. D) Early tailbud stage embryo stained for dpERK1/2 (red) and DAPI (white). Enlarged region is indicated by bracket on whole embryo panel.

Fig. 1 .

 1 Fig. 1. The a-line neural lineages of CionaThroughout the indicated stages, the a-line derived neural plate cells are colored pink in the illustrated embryos. Below the embryo illustrations are simplified schematics of the a-line derived neural plate, with the row III-IV CNS lineages in black and the row V-VI palp lineages in grey. Bars indicate sister cell relationships. A red dot indicates the pigment cell lineage at each stage with the corresponding cell nomenclature indicated. After segregation from the non-neural ectoderm, the a-line neural lineage is a single row of six cells at the 76cell stage. During gastrulation, the six a-line neural precursors divide along the anteriorposterior axis, making two rows of six cells. Together with the single row of A-line neural precursors, this makes a 3-row neural plate. All cells of the 3-row stage divide in a specific order to generate the 6-row stage[START_REF] Nicol | Development of the central nervous system of the larva of the ascidian, Ciona intestinalis L. I. The early lineages of the neural plate[END_REF]. The 6-row neural plate then divide in an asynchronous but predictable order (see text for details) to produce 12rows of neural plate cells in neurula embryos. At this stage the pigment cell lineage is positioned in the lateral column in row IIIp. This cell undergoes one final division to produce a11.194 and a11.193 prior to their intercalation at the midline (see also Supplementary movie 1 and Fig.4).

Fig. 2 .

 2 Fig. 2. Role of MEK1/2 and Eph/ephrin signals at the 3-row and 6-row neural plate stage Experimental conditions are indicated above each column of panels. A) dpERK1/2 immunofluorescence at the 6-row neural plate stage showing ERK1/2 activation in row III (arrowhead). B-C) Analysis of gene expression following various treatments. U0126 was added to embryos at the 76-cell stage (76c), or at the late 3-row neural plate stage when endoderm invagination is well underway (3row+). An embryo illustration on the right shows the control expression domains. Percentages indicate the proportion of embryos that the panel represents. For the Dll-B U0126 3row+ panel, the remaining embryos showed Dll-B expression in rows III and IV, although this was often weaker than in rows V and VI, and/or patchy. The red brackets indicate ectopic expression.

Fig. 3 .

 3 Fig. 3. Inhibition of Eph/ephrin signaling results in excess pigment cellsEmbryos were electroporated with the constructs indicated on the panels. Dmrt∷Eph1ΔC and Dmrt∷LacZ were used as controls for electroporation, showing that the results were specific to disruption of Eph3 and RasGAP. Co-electroporation with Tyr∷mCherry (red) shows that the pigment cells derive from Tyrosinase positive cells. The graph (E) shows the proportion of embryos with the number of pigment cells indicated in the key, following electroporation. In embryos exhibiting five or more pigment cells, it was difficult to distinguish each pigment cell, so these embryos were scored as 5+. Scale bars, 50μm.

Fig. 4 .

 4 Fig. 4. A revised pigment cell lineage This figure accompanies Supplementary movie 1. A-F) Embryos were electroporated with ZicL∷H2BCFP (green) to label rows I-IV and Dmrt∷H2BYFP (magenta) to label rows III-VI. Still images from the movie are shown on the left. On the right are the same still images with false-labeled nuclei to highlight the positions of row III and IV derivatives in orange and blue respectively. The a10.97 lineage is marked in pink, highlighting the extra division (D). G) An embryo that has been electroporated with Mitf∷Unc76GFP (green), Msx∷H2BmCherry (red) to show the lineage derivatives of a10.97 and a9.49 respectively. The position of each cell is labeled on the tailbud stage embryo.

Fig. 5 .

 5 Fig. 5. Pigment cell formation depends on MEK1/2 signals until early tailbud stage A-H) Expression of Trp at different stages of the pigment cell lineage as indicated by the colored boxes. See text for details. Time points are hours post fertilization (hpf) at 18°C, the time indicated reflects the embryological stage seen for the majority of embryos at each time point (as shown in I). I-J) In these experiments, one half of the embryos were fixed for Trp in situ hybridization (I) to determine the precise stage of U0126 treatment (n= minimum 36), the other half were treated with U0126 until larval stages in order to monitor pigment cell formation (J) (n= minimum 34). I) The color code of the graph represents the stage of the pigment cell lineage, defined as a9.49 (blue), a10.97 (red) and a11.193 (green). Bars are further broken down into the proportion of embryos representing the precise embryological stage, as represented in A-H. J) Bars represent the proportion of embryos with any

Fig. 6 .

 6 Fig. 6. Eph/ephrin signals control the spatial extent of ERK1/2 activation at the 12-row neurula stage

Fig. 7 .

 7 Fig. 7. Ectopic Trp expression in a10.98 following inhibition of Eph/ephrin signals Expression of Trp at 12-row neurula stage in control embryos, embryos electroporated with Dmrt∷Eph3ΔC or embryos treated with U0126 just after the 6-row stage (U0126 6row+). In these experiments, U0126-treatment began once embryos started to leave the 6-row neural plate stage and the cells in row II begin to divide. Each embryo half was scored independently and the quantification is shown in the graph.

Dev Biol. Author manuscript; available in PMC 2015 October 01.

Acknowledgments

We thank Nori Satoh and colleagues for the Ciona gene collection plates. We thank Filomena Ristoratore and Lionel Christiaen for communicating data prior to publication. N.H is supported by PhD fellowships from the Ministère de la Recherche (2009)(2010)(2011)(2012) and the Fondation ARC pour la Recherche sur le Cancer (DOC20120604723; 2012-2013). The group of H.Y is supported by the Centre National de la Recherche Scientifique (CNRS), the Université Pierre et Marie Curie, the Fondation ARC pour la Recherche sur le Cancer (1144) and the Agence Nationale de la Recherche (ANR-09-BLAN-0013-01). P.B.A is supported by a graduate fellowship from the US National Science Foundation. Work in the laboratory of M.L is supported by a grant from the US National Institutes of Health (NS 076542).

Supplementary Material

Refer to Web version on PubMed Central for supplementary material.

Highlights


François Bidet
email: francois.bidet@polytechnique.edu

Éric Goubault
email: goubault@lix.polytechnique.fr

Sylvie Putot
email: putot@lix.polytechnique.fr

O Hasan

S Tahar

U Siddique

Work in Progress: Reachability Analysis for Time-triggered Hybrid Systems, The Platoon Benchmark

This article presents an extension of the method of [1] to time-triggered hybrid systems, providing over-and under-approximations of the set of reachable states. Our results on the vehicles platoon benchmark [2] compare favorably to the state of the art tools Flow* and SpaceEx, with more precise over-approximations. Moreover, we provide a measure of the approximation's accuracy using the ratio of under-to overapproximation.

Introduction and presentation of the platoon benchmark

Different algorithms have been proposed to compute safe approximations of reachable states of hybrid systems, subject to uncertain initial conditions, parameters, and environment. These reachable states are key in analyzing the behavior of systems, for instance for proving that a region of the state-space will eventually be reached, while avoiding some unsafe set of states. In this short paper, we experimentally compare the behavior of different reachability tools on a benchmark that was specifically chosen to study their behavior in case of timetriggered transitions. We chose as benchmark the vehicle platoon proposed in the ARCH workshop [START_REF] Makhlouf | Networked cooperative platoon of vehicles for testing methods and verification tools[END_REF] for applied verification of hybrid systems. We will compare the results obtained on our small Taylor methods based reachability prototype with state of the art reachability tools Flow* and SpaceEx.

The model represents a platoon of three vehicles following a leader, a vehicle which can be controlled by a human, on a one-dimensional road. As illustrated in Figure 1, each vehicle i is localized with respect to its predecessor by a distance d i = d ref,i + e i with d ref,i the reference distance and e i the spacing error. Because the reference distance d ref,i is constant, the dynamic is independent of d ref,i , each vehicle i is described by its acceleration a i , its spacing error e i and the variation of this error ėi . The system is driven by the leader and described by its acceleration a L .

The behavior of the system can be described as a simple hybrid system with two modes : the first one, q c (see Figure 2b), in which each vehicle has access to information about the whole system, by communicating with each other, and the second one, q n (see Figure 2c), in which each vehicle has just access to its own state, because of a loss of communication. The switch between the two modes is time-triggered (i.e. each guard only depends on time and not on state variables), as shown in Figure 2a.

The goal of this benchmark is to find the minimum reference distance between vehicles such that we can ensure that for all i, d i > 0, which is equivalent to e i > -d ref,i . If e i ≤ -d ref,i then d i ≤ 0 and vehicule i collides with vehicle i -1 (or the leader if i = 1). Unlike in article [START_REF] Makhlouf | Networked cooperative platoon of vehicles for testing methods and verification tools[END_REF], we choose here a full loss of communication in mode q n , which means that all vehicles lose communication. It results in a slightly different matrix A n . Also, compared to the results given in [START_REF] Makhlouf | Networked cooperative platoon of vehicles for testing methods and verification tools[END_REF], we will investigate several transitions between the two modes (with and without communication) of the system. 1

Approaches and tools for reachability analysis

We developed a prototype extending the method of [START_REF] Putot | Forward inner-approximated reachability of non-linear continuous systems[END_REF] for reachability analysis of uncertain continuous systems, to the case of time-triggered hybrid systems, that is hybrid systems that change modes at certain specified times.

To compute the continuous state in one mode of the system, we use a combination of affine arithmetic [START_REF] De Figueiredo | Affine arithmetic: Concepts and applications[END_REF] and Taylor models [START_REF] Makino | Verified integration of odes and flows using differential algebraic methods on high-order taylor models[END_REF], as in [START_REF] Putot | Forward inner-approximated reachability of non-linear continuous systems[END_REF]:

affine arithmetic: Each uncertain quantity x ∈ R n is represented by x = x 0 + p i=1
x i i with for all i = 0, . . . , p x i ∈ R n and i ∈ [-1, 1]. Unlike interval arithmetic, it allows to encode dependencies between different quantities, e.g. let

x = 1 + 2 1 ∈ [-1, 3], then x -x = 1 -1 + (2 -2) 1 = 0 in affine arithmetic, whereas [-1, 3] -[-1, 3] = [-4, 4].
Taylor model: A Taylor model of function x of t ∈ [0, T ] is a pair (p, I) where p is a polynomial in t and I is a set called remainder (typically an interval) such that ∀t ∈ [0, T ], x(t) ∈ p(t) + I.

We improved the method of [START_REF] Putot | Forward inner-approximated reachability of non-linear continuous systems[END_REF] by adding the possibility for the analyzer to adapt the time step by the naive algorithm: if no over-approximation is found with the interval Picard operator [START_REF] Makino | Verified integration of odes and flows using differential algebraic methods on high-order taylor models[END_REF], we reduce the time step by half, otherwise we enlarge the time step by 10%. Because our prototype is based on Taylor models, the time is an implicit variable in our system, and the state at a given time instant can be precisely bounded by evaluating the Taylor model at that time. Time-triggered transitions can thus be evaluated without any loss of precision. Moreover, in addition to over-approximations, our prototype is able to compute under-approximations (as will be demonstrated in Section 3.3) following the algorithm of [START_REF] Putot | Forward inner-approximated reachability of non-linear continuous systems[END_REF] : we thus compute an over-approximation of the solution [z](t, z 0 ) for a particular initial condition z 0 ∈ z 0 and an over-approximation of the Jacobian matrix of the solution [J ](t, z 0 ) at each time t. Similarly, the interpretation of guards for time-triggered systems does not lose any precision.

The prototype has been programmed in C++ with the library "aaflib" [START_REF]aaflib -an affine arithmetic c++ library[END_REF] for the affine forms and the library "FADBAD++" [START_REF] Stauning | Fadbad++ -flexible automatic differentiation using templates and operator overloading in c++[END_REF] for the derivations (Taylor models and Jacobian matrix).

Other reachability tools experimented here

Flow* [START_REF] Chen | Decomposed reachability analysis for nonlinear systems[END_REF] also uses Taylor Models [START_REF] Chen | Taylor model flowpipe construction for non-linear hybrid systems[END_REF], but there are some significant differences with our approach. First, the Taylor models are not built and evaluated in affine arithmetic like in our approach. Moreover, the physical time of the system is not directly accessible to evaluate transitions' guards. We have to add a "timer" variable to know how much time we passed in each mode, as shown in Figure 2a. The relation between state variables and system time are thus not as direct as in our approach, and transitions become non-deterministic, inducing over-approximations.

SpaceEx [START_REF] Guernic | Flowpipe approximation and clustering in space-time[END_REF][START_REF] Donzé | Modular, hierarchical models of control systems in spaceex[END_REF] uses different (sub-)polyhedra to over-approximate states combined with different approaches to model time dependence. Like for Flow*, dependence of the system to physical time is not directly expressed, and accuracy is lost in time-triggered transitions. Also, contrarily to Flow* and our approach, it is restricted to affine systems.

3 Experiments 2

Transient, but certain acceleration

The original benchmark [START_REF] Makhlouf | Networked cooperative platoon of vehicles for testing methods and verification tools[END_REF] presents some results for a velocity step of 1 m/s. Here, we chose to add a transient acceleration for the leader of 1 m.s -2 during 3 seconds (a velocity variation of 3 m.s -1 in total). We suppose that vehicles lose communication during 1 second every 2 seconds (i.e. c 1 = 1 and c 2 = 1 in Figure 2). As shown in Figure 3a, Flow* produces an over-approximation which clearly diverges. SpaceEx (Figure 3b) produces an over-approximation wich width increases with time. Our prototype (Figure 3c) on the contrary is able to prove that the system stabilizes to a zero error e 1 : the width of the over-approximation is of the order of 10 -9 at time 30 s.

Constant, but uncertain acceleration

We now set c 1 = c 2 = c (same duration of communication and loss of communication) and we run multiple analyzes with various values for c, in [START_REF] Putot | Forward inner-approximated reachability of non-linear continuous systems[END_REF][START_REF] Donzé | Modular, hierarchical models of control systems in spaceex[END_REF]. We also assume that the leader acceleration a L is uncertain but constant in [-9, 1]. We fix initial state variables to 0 (no spacing error and no acceleration), except for a L that is set to be the interval [-9, 1]. As mentioned in section 1, each vehicle is described using 3 variables (the spacing error e i from the reference distance, the derivative of this error ėi and acceleration of the vehicule a i ). We only present results for e 1 as a function of time in this section, but we obtain similar results with e 2 and e 3 .

Settings and results with Flow*

We use an adaptative time step between 10 -5 and 10 -1 seconds, a remainder estimation of 10 -8 , a cutoff threshold of 10 -12 and a precision of 100 bits (for the MPFR library). These parameter values were obtained after several tests, in order to make the simulation successful (by reducing the time step) and reduce divergence (by adapting the cutoff threshold and remainder estimation). To reduce divergence of the over-approximation, we increased the Taylor Model order up to 16. Results of simulations however still diverge after about 14 seconds as shown in Figure 4. Interestingly, the analysis takes more time with order 4 Taylor Models (we stopped it after 10 minutes) than order 16 for which results for same time horizon 17 were obtained in 106 seconds. We expect the analysis is refining a lot the time step in order to try to control the increasing approximation error.

2 All experiments can be downloaded on http://www.lix.polytechnique.fr/Labo/Francois.Bidet/

Settings and results with SpaceEx

We used the STC Support Function with octagons, without set aggregation, an absolute flowpipe tolerance of 1 and a relative of 0, a local time horizon of 5 s (for c < 5), a maximum number of iterations of 30, a relative error of 10 -12 and an absolute error of 10 -15 . We reduced the absolute flowpipe tolerance to 10 -2 without significative difference. We also used uniformly distributed directions instead of octagons (with 12 directions) but had to stop the simulation after about 10 minutes of computation (with less than 12 directions, we obtained an error). Figure 5 shows that the analysis behaves well for c = 3, but diverges for fast switching, that is with

Comparing accuracy and efficiency with our prototype

As shown in Figure 6, our prototype was able to compute an over-approximation of e 1 without significant divergence even when c is small, e.g. when c = 1. We used Taylor models of order 4, an adaptative time step between 10 -5 s and 10 -1 s, and a cutoff threshold of 10 -5 (for each affine form, we regroup all noise terms with coefficient smaller than this threshold into a single noise term). The two analyzes represented in Figure 6 seem to reach an almost periodic behavior, which is the expected behavior. For a switching time period c = 3, our prototype's over-approximation is slightly more accurate than that of SpaceEx but both are comparable. But when the switching frequency is higher (c = 1), our prototype is clearly more accurate than SpaceEx and Flow*. As already hinted, these tools lose precision when localizing and taking the time-triggered transitions.

A time comparison is difficult because we used order 4 Taylor models in our prototype and order 16 Taylor model in Flow* (but the latter is faster than its own order 4 analysis with same other parameters). But we can note that for c = 1, our analysis takes 36 seconds for time horizon 30, while Flow* takes 106 seconds for time SpaceEx is running on a virtual machine with only 4Go of RAM against 8Go for our machine. In this setting, our prototype is between two and three times faster on this example.

Under-approximation

In addition to the over-approximation, our prototype produces an under-approximation of the reachable states (see the case of purely continuous systems in [START_REF] Putot | Forward inner-approximated reachability of non-linear continuous systems[END_REF]). An under-approximation (or inner-approximation) corresponds to a set of states that are sure to be reached from some initial value.

The under-approximation is useful as a complement of an over-approximation in many applications. It can be used to obtain a measure of precision of the approximation (e.g. the ratio of the under-to the overapproximations). It can also be used to invalidate some properties. Over-approximations ensure that if they do not intersect a set of "bad" states, then the systems' executions are safe. In the case of the platoon benchmark, such "bad" states are when the distances between two consecutive vehicles become negative (e i < -d ref,i ). If the under-approximation intersects the set of bad states, then we are bound to run into an erroneous state, for some initial state. We can see on Figure 7b that if we fix d ref,3 ≥ 11, we will never have a collision between vehicles 2 and 3 in the next 60 seconds following the acceleration of the leader a L ∈ [-9, 1] (over-approximation). Conversely, if we fix d ref,3 = 10, we are sure that there is a value of the acceleration of the leader a L ∈ [-9, 1] for which we will have a collision between vehicles 2 and 3 (under-approximation at time 7 seconds).

As in [START_REF] Putot | Forward inner-approximated reachability of non-linear continuous systems[END_REF], we can also use the ratio of the under-approximation's width to the over-approximation's width as an indicator of the accuracy of our approximations. The higher that ratio, the better the approximations are. If the ratio is equal to 1, then we have the exact set of reachable states. For instance, in Figure 7a, the ratio decreases from 1 (the set of initial states is known) to about 0.935 where it levels off. So the under-approximation of e 1 contains more than 93.5% of the real set of reachable states at the end of the simulation.

Conclusion and future work

Our prototype is able to compute over-approximation of reachable states of time-triggered system faster and with more accuracy than Flow* and SpaceEx for a challenging benchmark (the platoon benchmark). This is because we use a combination of affine arithmetic and Taylor models, with adaptative time steps, and because we use the time value as part of our Taylor models and not as an extra state variable, making guards for such time-triggered hybrid systems much simpler to interpret. The under-approximation allows us to refute hypotheses and to define an accuracy measure of our approximation as a ratio of under-to over-approximation's width.

We do not yet handle problems due to floating-point arithmetic. They potentially result in small errors on the over-and under-approximations' widths. This can be taken care of by carefully rounding (in the right direction) the affine forms coefficients, this will be included in the prototype in the near future.

Another limitation of our prototype is the exact time of transition guards. The next step of our development is the analysis of arbitrary switching, e.g. guards like t ∈ [t 1 , t 2 ] or t ≥ t 1 . Once done, we will be able to compare our performance with other platoon models (arbitrary loss of communication or loss at nondeterministic times) presented in [START_REF] Althoff | Arch-comp17 category report: Continuous and hybrid systems with linear continuous dynamics[END_REF].

1 d ref,1 e 1 Figure 1 Figure 2 :

 1112 Figure 1: Platoon Benchmark description

Figure 3 :

 3 Figure 3: e 1 as a function of time for a transient acceleration of 3 seconds

Figure 4 :

 4 Figure 4: Flow*: e 1 as a function of time

(a) c = 1 ,Figure 5 :

 15 Figure 5: SpaceEx: e 1 as a function of time c = 1, confirming that some accuracy is lost in transitions.

  c = 3, time horizon = 180 s (computation time = 142 seconds)

Figure 6 :

 6 Figure6: Our prototype: e 1 as a function of time horizon 15, for less accurate results. SpaceEx is running on a virtual machine with only 4Go of RAM against 8Go for our machine. In this setting, our prototype is between two and three times faster on this example.

  e3 as a function of time

Figure 7 :

 7 Figure 7: Our Prototype: over-and under-approximation (for c = 1 ; computation time 239 seconds)

The models and sources of experiments are downloadable on http://www.lix.polytechnique.fr/Labo/Francois.Bidet/


Éric Goubault
email: eric.goubault@lix.polytechnique.fr

Jérémy Ledent
email: jeremy.ledent@lix.polytechnique.fr

Samuel Mimram
email: samuel.mimram@lix.polytechnique.fr

Brief Announcement: On the Impossibility of Detecting Concurrency

Keywords: 2012 ACM Subject Classification Theory of computation → Concurrency concurrent specification, concurrent object, linearizability Digital Object Identifier 10.4230/LIPIcs.DISC.2018.50 1

We identify a general principle of distributed computing: one cannot force two processes running in parallel to see each other. This principle is formally stated in the context of asynchronous processes communicating through shared objects, using trace-based semantics. We prove that it holds in a reasonable computational model, and then study the class of concurrent specifications which satisfy this property. This allows us to derive a Galois connection theorem for different variants of linearizability.

Introduction

A common setting to study distributed computing is the one of asynchronous processes communicating through shared objects. In this context, the question of how to formally specify the behavior of the shared objects arises: what we want is an abstract, high-level specification, that does not refer to a particular implementation of the object. This is easy to achieve when the objects that we consider are concurrent versions of sequential data structures, such as lists or queues. Namely, we can simply take the usual sequential specification of the object, and extend it to a concurrent setting using one of the many correctness criteria found in the literature: atomicity [START_REF] Misra | Axioms for memory access in asynchronous hardware systems[END_REF], sequential consistency [START_REF] Lamport | How to make a multiprocessor computer that correctly executes multiprocess programs[END_REF], serializability [START_REF] Papadimitriou | The serializability of concurrent database updates[END_REF], causal consistency [START_REF] Raynal | From serializable to causal transactions for collaborative applications[END_REF], or linearizability [START_REF] Herlihy | Linearizability: A Correctness Condition for Concurrent Objects[END_REF]. However, we also want to be able to specify objects with an intrinsically concurrent nature, such as those found in the area of distributed computability [START_REF] Herlihy | Distributed Computing Through Combinatorial Topology[END_REF]: consensus and set-agreement objects, immediate snapshot. Another example is Java's Exchanger object: two processes that call the Exchanger object concurrently can swap values. A process calling the Exchanger alone fails and receives an error value.

A very general way of specifying such objects was proposed by Lamport [START_REF] Lamport | On interprocess communication[END_REF]. The specification of a concurrent object is simply the set of all the execution traces that we consider correct for this object. For example, a correct execution trace of the Exchanger object is depicted below:

T = i 4 0 • i 6 2 • r 6 0 • r 2 2 • i 7 1 • r Fail 1
The trace T consists of invocation events i x i meaning that the object was called by process i with input x, and response events r y i meaning that process i returned with output value y. This trace can be seen as an abstraction of the real-time execution pictured above, where the horizontal axis represents global time. Formally, for a fixed set V of values and n processes, the set of actions is:

A = {i x i | 0 ≤ i < n and x ∈ V} ∪ {r y i | 0 ≤ i < n and y ∈ V}
A trace is a word T ∈ A * such that for every process i, the projection of T on i starts with an invocation and alternates between invocations and responses. We write T for the set of all traces. Then, a concurrent specification in the sense of [START_REF] Lamport | On interprocess communication[END_REF] is simply a subset of T . This notion of concurrent specification is not convenient to use when reasoning about distributed systems. In fact, the correctness criteria such as linearizability can be regarded as more convenient ways of defining such concurrent specifications: starting from a sequential specification σ, we obtain Lin(σ) ⊆ T which is the set of all the traces that are linearizable w.r.t. σ. The advantage of this is that sequential specifications are much easier to describe than general concurrent specifications. To specify objects with a more concurrent flavor, variants of linearizability have been described: set-linearizability [START_REF] Neiger | Set-Linearizability[END_REF] (a.k.a. concurrency-aware linearizability [START_REF] Hemed | Modular Verification of Concurrency-Aware Linearizability[END_REF]) and interval-linearizability [START_REF] Castañeda | Specifying Concurrent Problems: Beyond Linearizability and up to Tasks[END_REF]. The last one is the most expressive: it captures all the distributed tasks, in the sense of [START_REF] Herlihy | Distributed Computing Through Combinatorial Topology[END_REF].

Contribution.

In the following, we restrict to a class of concurrent specifications: those satisfying the undetectability of concurrency property. As it turns out, they correspond exactly to the concurrent specifications definable using interval-linearizability. We show that these are the only relevant concurrent specifications, and prove a theorem showing how the different notions of linearizability relate to this property.

Results

A concurrent specification σ ⊆ T satisfies the undetectability of concurrency property if the following two conditions hold, where a is an action of some process j = i.

(1) invocations commute to the left: [START_REF] Richard J Lipton | Reduction: A method of proving properties of parallel programs[END_REF]: (1) and ( 2) assert that invocations and responses are left/right movers, respectively. Pictorially, these two properties mean that if we take a correct execution trace (a) and "expand" the intervals, then the resulting trace (b) must also be considered correct. Intuitively, in (b), the two processes failed to see each other and acted as in the sequential trace (a). Intuitively, the reason why Theorem 1 holds is that calling an object or returning a value does not communicate any information to the other processes. If a process idles right after invoking, or just before returning, it is invisible to the other processes. The undetectability of concurrency property is naturally enforced by the usual specification techniques such as linearizability, so by using these tools we do not have to worry about this property: we get it for free. Proposition 2. Let σ be a sequential specification. Then Lin(σ), the set of all linearizable traces, satisfies properties (1) and (2).

if T • a • i x i • T ∈ σ, then T • i x i • a • T ∈ σ, (2) responses commute to the right: if T • r y i • a • T ∈ σ, then T • a • r y i • T ∈ σ.

Such properties come up in Lipton's reduction proof technique

We now write SSpec for the set of sequential specifications, and CSpec for the set of concurrent specifications which satisfy the undetectability of concurrency. Proposition 2 says that we can view Lin as a map from SSpec to CSpec. Conversely, there is also a map in the other direction U : CSpec → SSpec which, given a concurrent specification, forgets about all the concurrent behaviors and keeps only the sequential ones.

Theorem 3. The functions Lin and U are monotonous w.r.t. inclusions, and form a Galois connection, i.e., for every σ ∈ SSpec and τ ∈ CSpec, Lin(σ) ⊆ τ ⇐⇒ σ ⊆ U(τ ).

The fact that we imposed the undetectability of concurrency property on CSpec is crucial in order to establish Theorem 3. This theorem can be understood as follows: given a sequential specification σ, we want to extend it to a concurrent one. Then any τ ∈ CSpec that contains σ must also contain Lin(σ), i.e., Lin(σ) is the smallest extension of σ which is in CSpec. Thus, Lin(σ) can be described as follows: we start with the set of all sequential traces of σ, then close it under the two properties (1) and [START_REF] Hemed | Modular Verification of Concurrency-Aware Linearizability[END_REF].

Finally, note that analogues of Proposition 2 and Theorem 3 still hold when we replace linearizability by set-or interval-linearizability. In particular, Theorem 3 for intervallinearizability gives us the following characterization of interval-linearizable objects: Corollary 4. The concurrent specifications which are definable using interval-linearizability are exactly the ones satisfying the undetectability of concurrency.

Theorem 1 .

 1 As a naive attempt at specifying the Exchanger object, we might have wanted to allow (a) and forbid (b). But implementing such a specification would have been hopeless, as we show in a reasonable trace-based computational model: The semantics P of any program P satisfies properties (1) and (2).

50:2 On the Impossibility of Detecting Concurrency

	Exchange(4)	6
	P0
		Exchange(7) Fail
	P1
	Exchange(6)	4
	P2
	© Éric Goubault and Jérémy Ledent and Samuel Mimram;
	licensed under Creative Commons License CC-BY
	32nd International Symposium on Distributed Computing (DISC 2018).
	Editors: Ulrich Schmid and Josef Widder; Article No. 50; pp. 50:1-50:4
	Leibniz International Proceedings in Informatics
	Schloss Dagstuhl -Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany