Dune Ridges

France ) Van Vliet-Lanoe
email: .brigitte.vanvlietlanoe@univ-brest.fr

Le Cornec

HOLOCENE FORMATION AND EVOLUTION OF COASTAL

Keywords: dunes, Holocene, climate, sand starvation, anthropic perturbation

Holocene coastal dune formation under a continuously rising Sea-Level (SL) is an abnormal response to increasing storm frequency. The aim of this work is to understand the coastal sedimentary budget and the present-day sand starvation, controlled by climate and man. Dating in Brittany shows that aeolian deposition initiated from c.4000 cal BP, with the slowing-down of the SL rise. Prehistorical dunes appeared here from c.3000 cal BP, without SL regression. After, further building phases recycled the same stock of sands. Historical dunes I developed from c.350 AD. Major storms between 900 -1200 AD resulted in the construction of washover coastal ridges, the Historical dunes II. A part of the sand was evacuated offshore. From c.1350 AD, the pre-existing ridges are reworked forming the Historical dunes III, leading to a rapid coastal erosion and inland drift. Holocene dunes with a rising SL, constitute a temporary anomaly, mostly forced by man, soon erased by storms in Brittany.

INTRODUCTION

Coastal dunes are connected to sea-level vicinity, and storminess, as a function of sedimentary supply [START_REF] Einsele | Marine depositional events controlled by sediment supply and sea-level change[END_REF][START_REF] Orford | Holocene coastal dune initiation in Northumberland and Norfolk, eastern UK: climate and sea-level changes as possible forcing agents for dune initiation[END_REF][START_REF] Maüz | Aeolian beach ridges and their significance for climate and sea level: Concept and insight from the Levant coast (East Mediterranean)[END_REF]. In that way, anthropic perturbations, such as agro-pastoral practices, may favour sand remobilisation on a regional scale [START_REF] Pye | Holocene sea-level variations and geomorphological response: an example from northern Brittany (France)[END_REF].

Most studies link the aeolian coastal deposits to regressive phases [START_REF] Pye | Holocene sea-level variations and geomorphological response: an example from northern Brittany (France)[END_REF][START_REF] Maüz | Aeolian beach ridges and their significance for climate and sea level: Concept and insight from the Levant coast (East Mediterranean)[END_REF], and only a few to a rising SL [START_REF] Pye | Holocene sea-level variations and geomorphological response: an example from northern Brittany (France)[END_REF][START_REF] Pye | Holocene sea-level variations and geomorphological response: an example from northern Brittany (France)[END_REF][START_REF] Szkornik | Aeolian sand movement and relative sea-level rise in Ho Bugt, western Denmark, during the `Little Ice Age[END_REF]. A link between historical dune building and periods of limited marine regression (c. 50 cm) has been suggested [START_REF] Lamb | Climate, History and the Modern World[END_REF][START_REF] Orford | Holocene coastal dune initiation in Northumberland and Norfolk, eastern UK: climate and sea-level changes as possible forcing agents for dune initiation[END_REF]. Dunes formation in a context of rising Relative Sea-Level (RSL) results from the reworking or overstepping of the coastal foredune or storm ridge.

The history of the Holocene RSL on the North West European Shelf is a continuous rise followed by decelerating steps [START_REF] Shennan | Holocene land-and sea-level changes in Great Britain[END_REF][START_REF] Goslin | France): dynamiques régionales et réponses locales[END_REF]. An increased storminess is responsible for numerous episodes of sand drift and dune building along the western European coast, especially during the coolest part (AD 1570(AD -1900) ) of the Little Ice Age (LIA,1350(LIA, -1880;;[START_REF] Lamb | Climate, History and the Modern World[END_REF][START_REF] Bärring | Multi-indices analysis of southern Scandinavian storminess 1780-2005 and links to interdecadal variations in the NW Europe-North Sea region[END_REF][START_REF] Clarke | The impact of North Atlantic storminess on western European coasts: A review[END_REF]. The degree of preservation of dunes is largely constrained by the speed of the RSL rise and the wave energy regime, expressed here in terms of storm activity [START_REF] Pye | Holocene sea-level variations and geomorphological response: an example from northern Brittany (France)[END_REF]. The availability of sediment for dune building is controlled by sediment accumulation in the nearshore environment (<10 m deep; [START_REF] Einsele | Marine depositional events controlled by sediment supply and sea-level change[END_REF]. Firstly, this requires low energy waves that allow an accumulation of sand on the beach profile and permit its drift in the form of a foredune [START_REF] Short | Wave, beach and dune interactions in southeastern Australia[END_REF]. Secondly, it requires prevailing onshore winds to blow this sand inland. The source of available sands can be variable and include the reworking by RSL rise of past periglacial deposits, saprolites, or old marine deposits with some importation to the shore by river [START_REF] Kelley | Sand budgets at geological, historical and contemporary time scales for a developed beach system[END_REF]. Additionally, large shelfs, such as the shallow English Channel and North Sea, are generally excellent sediment suppliers, compared to the narrow Armorican platform surrounding the dune coastal ridges studied in the present paper.

From a general point of view, in summer, dissipative beaches present a wide foreshore, a low gradient, and fine sands that are less resistant to wind flow, and are more conducive for aeolian sand transport than the steeper reflective beaches [START_REF] Hesp | The beach backshore and beyond[END_REF]. Reflective beaches are much less favorable for aeolian transport [START_REF] Hesp | The beach backshore and beyond[END_REF]. The dune building process mostly results from the impact of recurrent storm periods that lower the beach profile, especially at the High Water Mark (HWM; [START_REF] Hallégouët | Les crêtes littorales dunifiées du Massif Armoricain : formation et évolution[END_REF][START_REF] Ruz | Influence of high water levels on aeolian sand transport: upper beach/dune evolution on a macrotidal coast, Wissant Bay[END_REF]. The beach profile becomes dissipative as it was the case in Brittany in springs of 2010, 2013 and 2014: a thick foredune was formed in summer 2010 at Guisseny (Fig. 1a; [START_REF] Suanez | Dune recovery after storm erosion on a high-energy beach: Vougot beach, Brittany (France)[END_REF] following a spring storm. Extreme storm events are responsible for erosion processes and over the course of a single extreme event, thick sediment deposition from the upper shoreface to the lower foreshore can occur [START_REF] Houser | Post-hurricane airflow and sediment transport over a recovering dune[END_REF][START_REF] Fruergaard | Major coastal impact induced by a 1000-year storm event[END_REF]. They can also provoke erosive processes on the coast by offshore exportation of sand [START_REF] Goff | Sedimentary differences between the 2002 Easter storm and the 15th Century Okoropunga tsunami, southeastern North Island, New Zealand[END_REF]. This seems to be the case for western Brittany, after the long period of extreme waves in February 2014 (Fig. 2).Vegetation is also a major factor controlling the formation and morphology of coastal dunes (Hesp, 2002, Pye and[START_REF] Pye | Holocene sea-level variations and geomorphological response: an example from northern Brittany (France)[END_REF]. Plant cover is responsible for roughness and reduction in the wind velocity, which increases the trapping of sands [START_REF] Hesp | Storm wind flow over a foredune, Prince Edward Isl[END_REF]. Climate and anthropogenic activities may thus influence dune formation.

Brittany is one of the most exposed coasts in France, characterized by a limited sand supply on a very flat polygenetic rocky platform, especially along the western and northern coasts. The coastal accumulations usually form ridges, topped with a thin dune, isolating partly (lagoon) or totally (marsh). depressions or valleys Today, the RSL keeps rising [START_REF] Cazenave | Sea level and Climate: observation and causes of changes[END_REF] and coastal retreat occurs at a rate of about 1m/yr in the bay of Audierne (1966to 1988 ;[START_REF] Faye | Evolution récente de la ligne de rivage en Baie d'Audierne : de Penhors à la Pointe de la Torche[END_REF]. Extreme storms mostly develop when the North Atlantic Oscillation (NAO) mode is negative on the decennial scale, although the NAO can be interrupted by shorter positive events, especially during a high Atlantic Multidecadal Oscillation mode (AMO; Van Vliet-Lanoë et al., 2014b). Since 2007, storms frequency is rising, reactivating the coastal retreat, with no marked drift of sands. The aim of this paper is to synthetize the conditions, timing and meaning of dune formation in Brittany.

GEOLOGICAL AND GEOMORPHOLOGICAL SETTING

From a geodynamical point of view, Brittany's peninsula is related to the post-rift subsidence of the Atlantic margin [START_REF] Ziegler | European cenozoïc rift system[END_REF]. The recent Holocene RSL curve established for Brittany [START_REF] Goslin | France): dynamiques régionales et réponses locales[END_REF] indicates an estimated subsidence rate of ca. -0.3 mm/year for the last 2000 years. Reconstructed Regional Relative Sea Level (RRSL) shows progressively a progressive slow-down of the rise, with clear inflexion points around 7000 cal BP (calibrated years before present), 6000 cal BP, 4500 cal BP and around the 3-2000 cal BP period, without any distinct oscillation or step-wise character [START_REF] Goslin | France): dynamiques régionales et réponses locales[END_REF]. The tidal platform is mostly rocky, usually wide (one to several kilometres), and deepens very regularly to -30 m offshore. Regional tidal regimes are mostly macrotidal. The offshore sedimentary cover is thin and limited, dominated by rock outcrops. Generally, terrigeneous sediment supply by rivers is limited. Southern Brittany, especially to the East, is an exception due to important rivers and old marine formations that provide a larger sand supply. Soil erosion is the main provider for coastal sands via the rivers [START_REF] Fan | River flooding, storm resuspension, and event stratigraphy on the northern California shelf: observations compared with simulations[END_REF][START_REF] Guillén | Sediment dynamics during wet and dry storm events on the Têt inner shelf (SW Gulf of Lions)[END_REF]. Slash and burn practices produced a limited forest clearance from c. 4000 cal BP (Early Bronze Age; [START_REF] Marguerie | Evolution de la végétation sous l'impact humain en armorique, du néolithique aux périodes historiques[END_REF] exposing to interglacial rainfall a relictual periglacial topography [START_REF] Vliet-Lanoë | Evolution de l'enregistrement pédosédimentaire depuis 150 ka en France du NO et en Belgique: biorhexistasie et bilans sédimentaires[END_REF] 1), exclusively in connection with dune building phase, with a calibration using the CALIB 7.0. Software [START_REF] Stuiver | CALIB Radiocarbon Calibration[END_REF] and the radiocarbon calibration (IntCal13; [START_REF] Reimer | Intcal13 and Marine13 Radiocarbon Age Calibration Curves 0-50,000 Years Cal BP[END_REF]. Considering the regional scarcity in 14 C datable material, we used all available information existing in the literature. In this paper, we discuss 81 pertinent dating of dunes and coastal ridges from Brittany, Normandy and Picardy, directly compiled on Figure 1b.

Palaeo-storm events were identified through sedimentary fabrics [START_REF] Buynevich | Sedimentary records of intense storms in Holocene barrier sequences[END_REF]. Palaeostorminess traces have already been discussed and events were extracted from the Holocene prism stratigraphy (Van Vliet-Lanoë et al., 2014b). The RSL curve for Brittany [START_REF] Goslin | Holocene relative sea-level chnages in western Brittany (France) between 7600 and 400 cal. BP.c Reconstruction from basal-peat deposits[END_REF][START_REF] Goslin | France): dynamiques régionales et réponses locales[END_REF] was calibrated with the local tidal range, using a multi-proxy analysis based on the combined of geochemical, micromorphological and isotopic indicators.

SEA-LEVEL AND STORMINESS MORPHOLOGICAL IMPACT

The effects of storms on Holocene sedimentary sequences are particularly important since the mid-Holocene period, when the regional RSL reached a position close to the modern one. The sedimentary record of RSL rise and particularly the High Stands (HS) were perturbed by the increased strength of storm surges, mostly after Roman times [START_REF] Meurisse-Fort | Enregistrement haute résolution des massifs dunaires ; Manche, mer du Nord et Atlantique[END_REF]. Large-scale (pluridecimetric to metric) pseudo-oscillations observed in SL reconstructions (e.g. [START_REF] Morzadec-Kerfourn | Variations de la ligne de rivage armoricaine au Quaternaire : analyses polliniques de dépôts organiques littoraux[END_REF]; are the expression of disturbances of the sedimentary record induced by storms [START_REF] Goslin | Holocene relative sea-level chnages in western Brittany (France) between 7600 and 400 cal. BP.c Reconstruction from basal-peat deposits[END_REF]Van Vliet-Lanoë et al., 2014a). Extreme storms or several days' gales could be responsible for major morphological changes, in the former ridge and back-ridge zones. From our observations, pseudo "HS" seem to be perched notches preserved in sands dunes or depositional terraces, situated at 1-10 m above the HWM, that may form as a result of dispersive swash action [START_REF] Mckenna | Storm swash terraces: a previously overlooked element of the cliff-shore platform system[END_REF] and commonly forming in lagoons perched washover fans. Low standing storm ridges result from run-up erosion of the crest, favouring breaching (Fig. 2). Storm-cut platforms develop in soft material down the ridge at the level of the average Low Water Mark (LWM; Retallack and Roering, 2012 ; Fig. 2). It allows to interpret "low surface" as erosion surface formed as the result of sediment export by storm (Fig. 2). Recurrent severe storms may accentuate the erosion. After the storm, the restoration of the normal beach profile and of the coastal ridge by swell and wind may take some time, following the sediment supply of the beach.

DUNES BUILDING PHASES: DATA

Aeolian deposits are rarely resting directly on rock but commonly found on beach deposits, or resting on cultivated soils or peats. Stabilisation periods are often marked by humic soil or peat formation and these are often interrupted by thin aeolian sand sheets, or, more rarely, by thin colluvial loamy deposits (in the vicinity of cliffs). Convolute deformations can be observed in several sites. In washover fans, they are often associated with load casts (Lindström 1979), although in some places they result from cattle. It is debated whether the swash or animal treading hurts oversaturated sands [START_REF] Allen | Sedimentary Structures, Their Character and Physical Basis[END_REF]. Today, in Ireland, cattle commonly visit the dunes and shores. In Picardy, the coast was pastured by the marsh little ox [START_REF] Meurisse-Fort | Enregistrement haute résolution des massifs dunaires ; Manche, mer du Nord et Atlantique[END_REF]. For the Merovingian dunes of northern Brittany, sheep and goats are probably responsible for the small-sized trampling deformations.

The pre-historical dunes, 3050 à 2300 cal BP (Fig. 1b)

The base of Penhat dune (Crozon, Fig. 1a), attest to the oldest sand drift (c. 5280 cal BP; [START_REF] Meurisse-Fort | Enregistrement haute résolution des massifs dunaires ; Manche, mer du Nord et Atlantique[END_REF]. At Audierne (Gwendrez; Fig. 1a), the onset of dune accretion was later than 5000 cal BP (< 4950 cal BP; [START_REF] Haslett | Geomorphologic and palaeoenvironmental development of Holocene perched dune systems in Brittany, France[END_REF]2000). In the Kermor marshes (Fig. 1a), a "brackish" sandy peat resting on a fresh water peat yields an age of c. 5122 cal BP at +0.7 m NGF, perhaps attesting to the breach of coastal ridges by storms with limited aeolian sand drift. At the Anse du Verger (NE Brittany), a date of 3600 cal BP was obtained for the onset of dune building [START_REF] Pye | Holocene sea-level variations and geomorphological response: an example from northern Brittany (France)[END_REF].

After the construction of the first coastal ridge, peat began to accumulate in back-ridge depressions during the Halstatt period, as in the Bay of Audierne (c. 2450 cal BP; [START_REF] Carter | The impact of recent sea level and climatic changes of the coast of northwest France[END_REF]) and also at The historical dunes (Fig. 2)

First generation, 350 AD-800 AD Sand dune invaded the St Urnel cemetery (Bay of Audierne) in late Roman time (III d century; [START_REF] Giot | Le cimetière des anciens bretons de Saint Urnel ou Saint Saturnin en Plomeur (Finistère)[END_REF]. Breaching of the coastal ridge and flooding reappear locally at the Bay of Audierne (Lescor's marsh and Troenoen lagoon) after 320 AD, in association with aeolian drift. A brief stabilization is recorded here between 620 and 680 AD, as also in SW and northern Brittany (Table 1, Fig. 1b).

Second generation, 800 AD-1200 AD.

A second dune invasion was well documented between c. 800 AD and c.1000 AD at St. Urnel [START_REF] Giot | Le cimetière des anciens bretons de Saint Urnel ou Saint Saturnin en Plomeur (Finistère)[END_REF], mainly during the second half of the 11 th century. This burial place was reabandoned in the late 12th century [START_REF] Giot | Le cimetière des anciens bretons de Saint Urnel ou Saint Saturnin en Plomeur (Finistère)[END_REF] Carter et al., 2003;Plouguerneau, Morzadec, 1974).

Third generation, from 1350 AD

From c.1350 AD to c.1500 AD, a first period of sand drift was recorded, ending with brief stabilisations marked by humic soils from c.1400 to c.1550 AD (Fig. 1a), which were better developed than during the Medieval Climate Optimum (MCO).

In the Bay of Goulven, Guisseny and Plouguerneau (Fig. 1a), dunes continued to migrate during the XVII-XVIII th centuries. Such landward dune migration also occurred at Audierne and other places, particularly in SE Brittany [START_REF] Guilcher | Coastal dunes in Brittany and their managment[END_REF] in Normandy and Picardy [START_REF] Meurisse-Fort | Enregistrement haute résolution des massifs dunaires ; Manche, mer du Nord et Atlantique[END_REF]. Several churches and villages in these regions, as well as in Brittany and Picardy, were buried by sands in the late XVII th century in association with major gales. After a period of relative quiescence, storms and sand drift again destroyed church and villages in the region, with sand drifts up to 5 km inland. Major storm events occurred in 1795, 1808 and 1824.

DISCUSSION

Stratigraphy:

The onset of sand drift leading to Prehistorical dunes development in Brittany occurred very locally after 5000 cal BP. Sand drift with dune building appeared closer to 2750 cal BP, as a result of enhanced storminess driven by a major cooling event associated with the Homeric solar low (Van Vliet-Lanoë et al., 2014b). Since c. 2750 cal BP, dunes developed in Brittany, as on most of the European coasts [START_REF] Wilson | Mid-to late-Holocene coastal dune event stratigraphy for the North coast of Northern Ireland[END_REF][START_REF] Meurisse-Fort | Enregistrement haute résolution des massifs dunaires ; Manche, mer du Nord et Atlantique[END_REF]. In the Bay of Audierne, a second phase of sand drift seems to develop after the onset of La Tène Iron Age (c. 2425 cal BP), reworking the former deposits and splaying the sand locally inland [START_REF] Giot | Le cimetière des anciens bretons de Saint Urnel ou Saint Saturnin en Plomeur (Finistère)[END_REF]. This occurred in response to a brief climate degradation that corresponded to the Greek solar low (centered around 2300 cal BP).

The onset of dune building occurred in a similar time span after 4000 cal BP in Picardy (Meurisse-Fort, 2009), Aquitaine [START_REF] Clarke | The impact of North Atlantic storminess on western European coasts: A review[END_REF], Northumberland [START_REF] Orford | Holocene coastal dune initiation in Northumberland and Norfolk, eastern UK: climate and sea-level changes as possible forcing agents for dune initiation[END_REF] and Denmark [START_REF] Clemmensen | The evolution of Holocene coastal dunefields, Jutland, Denmark: A record of climate change over the past 5000 years[END_REF], after 3500 cal BP in Belgium [START_REF] Anthony | Shoreface sand supply and mid-to late Holocene aeolian dune formation on the storm-dominated macrotidal coast of the southern North Sea[END_REF] and the Netherlands [START_REF] Jelgersma | An outline of geological history of the coastal dunes in the western Netherlands[END_REF]. We may consider the onset of the dune building to be clearly connected with the slowing down in the SL rise from c.4500 cal BP (e.g. [START_REF] Goslin | France): dynamiques régionales et réponses locales[END_REF] , 2010), which was well-recorded in the entire region (Fig. 1b). The start of these Merovingian dunes seems rather synchronic at the scale of western Europe (Fig. 1b) .related with cold and stormy weather from 200 AD [START_REF] Mccormick | Climate Change during and after the Roman Empire: Reconstructing the Past from Scientific and Historical Evidence[END_REF][START_REF] Patterson | Two millennia of North Atlantic seasonality and implications for Norse colonies[END_REF]. Sand drift was recorded from c.

260 -300 AD, probably when the morphology of the beaches was sufficiently lowered to become dissipative and the sensible vegetation was destroyed by agro-pastoral activities developed by the Merovingian (Fig. 1b). A major point is the occurrence of frequent cattle trampling that coincided with the development of forest clearance and agro-pastoralism in Brittany, Cotentin and Picardy, which promoted instabilities in the sand cover: these destabilised dunes thus drifted further inland, with the largest splay of the whole dunes' generations. Villages were found in nearshore positions during the VII th century. It seems possible that, from that time, the sedimentary budget seriously lowered, partly due to regional anthropogenic practices and mostly inland sand drift. The climate also cooled from 536

-540 AD in response to a volcanic eruption [START_REF] Gao | Volcanic forcing of climate over the past 1500 years: An improved ice corebased index for climate models[END_REF] and to a first solar minimum between 615 and 755 AD [START_REF] Usoskin | Grand minima and maxima of solar activity: new observational constraints[END_REF], fitting the Hegire period (Fig. 1b). The cooling from c. 700 to 800 AD is related to a second solar low, the Viking minimum. Here, dunes continue to grow transversely, attesting to a progressive aggradation and regular Westerly winds only. The record in storminess attests to recurrent storm events, but no giant one. This generation of sand drift is not clear in southern Brittany, where the coastal budget and wind directions are normally more favorable and the coastal ridge seems still vegetated. The Quiberon peninsula was still covered by forest in the XI th century.

The onset of the historical dunes II (Brittany: 800 -1250 AD) occurred synchronously all over Europe [START_REF] Jelgersma | Holocene storm surges in the coastal dunes of the western Netherlands[END_REF][START_REF] Meurisse-Fort | Enregistrement haute résolution des massifs dunaires ; Manche, mer du Nord et Atlantique[END_REF]. The period from 950 to 1350 AD is often considered to be the European Medieval mild period (Hughes and Diaz, 1994). Rainy conditions existed all over Europe (Maruchek, 2010), promoting sand supply by rivers. Villages migrated inland as well in Brittany, Picardy and the Netherlands (construction during the VII th century); this migration was also connected with the Viking invasions. Centennial hurricanes were recorded in Brittany, the southern British Islands and also along the coast of western Cotentin (Fig. 1a; Van Vliet-Lanoë et al., 2014b).

Hurricanes are recorded in northern France (890 AD, [START_REF] Meurisse-Fort | Enregistrement haute résolution des massifs dunaires ; Manche, mer du Nord et Atlantique[END_REF], in Belgium, with the formation of the Zwin in 1134 AD, and in the Netherlands, easing the formation of the Zuiderzee (large storms in 838 AD, 1170 AD and 1240 AD, [START_REF] Buisman | Duizend jaar weer, wind en water in de Lage Landen / 1 tot 1300 AD[END_REF]. These events were connected with the Oort solar minimum (1010 -1050 AD; [START_REF] Usoskin | Grand minima and maxima of solar activity: new observational constraints[END_REF]. A very negative NAO, which was even recorded on Greenland [START_REF] Kobashi | On the origin of multi-decadal to centennial Greenland temperature anomalies over the past 800 yr[END_REF], was responsible for very high sea surface temperatures in the NW Atlantic, which resulted from a warm intertropical ocean and a positive AMO (Van Vliet-Lanoë et al., 2014b). Here, the inland sand drift inland was more limited, due to heavy precipitation, filling mostly lagoons. Storm ridges, which were eroded to their back (Fig. 2), are found along the current coastline. The whole coasts of Brittany were subjected to a major morphological transformation. In Picardy, the shift from transverse dunes to parabolic is explained by a reduction in sand supply from the beach, a more extensive vegetation cover (high water table) and potentially harsher winds [START_REF] Meurisse-Fort | Enregistrement haute résolution des massifs dunaires ; Manche, mer du Nord et Atlantique[END_REF]. A quiet period for sand drift seemed to exist from 1250 to 1340 AD (Fig. 1b) (Van Vliet-Lanoë et al, 2014b) which corresponds mostly to the MCO. The climate during this period was mild and the NAO mostly positive [START_REF] Trouet | Persistent positive North Atlantic Oscillation mode dominated the Medieval Climate anomaly[END_REF] which resulted from a rise of the AMO in response to strong solar activity (1100 -1250 AD; [START_REF] Usoskin | Grand minima and maxima of solar activity: new observational constraints[END_REF].

The onset of the historical dunes III (Brittany: 1350 AD to present) coincides with the onset of the LIA in Europe; it shows the initiation and build-up of the recent dunes (1350 -1750 AD), with a development, maximized during the LIA. Most of the LIA was dominated by giant storms and an unstable negative decennial NAO [START_REF] Trouet | Persistent positive North Atlantic Oscillation mode dominated the Medieval Climate anomaly[END_REF], despite few positive AMO events. High frequencies of SW winds were recorded in Britain (London) from 1340 to 1420 and from 1470 to 1550 AD (Lamb and Fryedalh, 2005), corresponding to mild weather with regular, westerly gales, attesting to the prevailing positive winter NAO and fair weather optimal for building dunes. A first period of dune building occurred from 1350 to 1550 AD (Fig. 1b), a period of relative storm quiescence, especially from 1350-1530 AD on the North and Central Atlantic (prevailing positive decennial NAO with low AMO modes), which corresponded to peculiar weather (Van Vliet-Lanoë et al., 2014b) and AMOC patterns [START_REF] Trouet | North Atlantic storminess and Atlantic Meridional Overturning Circulation during the last Millennium: Reconciling contradictory proxy records of NAO variability[END_REF]. A first stormy period of the LIA occurred from c. 1460 to c. 1630, which was responsible for more important dune activity that corresponded to the Spörer solar minimum (1460 -1550 AD) and a prevailing negative winter NAO. From 1600 AD, sea surface temperatures North of Iceland dropped [START_REF] Bendle | High-resolution alkenone sea surface temperature variability on the North Icelandic Shelf: implications for Nordic Seas palaeoclimatic development during the Holocene[END_REF], attesting to a low AMO mode. The prevailing winter NAO mode was negative and boosted by the Maunder Minimum (1645 -1715 AD; [START_REF] Usoskin | Grand minima and maxima of solar activity: new observational constraints[END_REF][START_REF] Trouet | Persistent positive North Atlantic Oscillation mode dominated the Medieval Climate anomaly[END_REF]. In the Scillies, an important sand drift has been dated AD 1560-1680(Banerjee et al. 2001)). This is the second period for giant storms, this time with a meridian wind pattern (Van Vliet-Lanoë et al., 2014b) driven by unstable jet streams and brief positive NAO anomalies. Sand drift was major, burying churches and villages along the English Channel. The long Great Storm of 4-8 December 1703 crossed the English Channel and Brittany (Lamb and Fryedalh 2005). Similarly, the Christmas 1717 four-days storm affected most of Europe, North of the Gulf of Biscaye, while the 19-20 st January 1735 and the 16 th February 1736 events affected Brittany, Cotentin and the Scillies, (OSL dating:1700-1780, Banerjee et al., 2001). Superimposed storm-surge layers (Lindstrøm, 1979) exposed on the Keremma spit (Bay of Goulven) have been dated with OSL to 1752-1776and 1723-1751AD (Van Heteren, 2002), and major exportation of sand to the offshore in 1703 AD (no dune field), which destroyed the former spit.

A third sand drift event can only be dated with archives and old maps. It took place mostly at the end of the XVIII th /early XIX th centuries, in relation to the Dalton Minimum (1790 -1820). Again churches were buried on Batz Island (N Brittany) and Skagen (Jutland). Major storm events occurred regionally in 1795, 1808 and 1824 AD with dominant westerly winds. Dunes developed longitudinally at St.Annela-Palud and at Kerzine (Fig. 1a). In between these events, high frequencies of SW winds were recorded in Britain (London) from c. 1730, c. 1860and 1900-1930[START_REF] Lamb | Historic Storms of the North Sea, British Isles and Northwest Europe[END_REF], signaling positive NAO periods fitting the relative landscape stabilizations.

Dynamical context: dune disapperance in the near future

When the stormy period ends, the beach is rapidly supplied by sands migrating gently from the subtidal accumulation (Fig. 2). The erosion notch is rapidly buried by dune collapse during the afterstorm restoration of the beach. Additionally, when the climate warms up, water seepage further eases the fixation of drift sand. Firstly, a foredune is formed mostly from spring. Then, from late spring to late summer (water table lowering), drift sand is mobilized, climbing on the foredune and beginning the construction of the true dune. When the autumn's equinoctial storms occur, important drift may occur but also wave run-up may initiate interstratified dune / washover facies, as observed at Audierne, Guisseny and Goulven (Fig. 2). When this succession of events occurs within the same year, vegetation growth cannot impede the process.

Wind direction also has an important impact on dune formation. During positive NAO modes, regional winds are mostly westerlies [START_REF] Pirazzoli | Changes in storminess and surges in western France during the last century[END_REF]. During negative NAO modes, the prevailing winds are meridian [START_REF] Hénaff | Recherche d'indicateurs géomorphologiques de variation d'orientation des houles sur les côtes françaises de l'Atlantique et de la Manche au cours des 25 dernières années, analyse des données et comparaison avec les données de l'atlas numérique de houle EDF-LNHE[END_REF], driven by the important oscillations of the jet stream. This is the main reason for some regional differences in dune formation, as related to the coastal orientation.

When a period of low storm activity occurs for several years with a positive NAO and a high AMO mode, vegetation recolonization occurs rapidly after the storm due to wetter, but not necessarily warmer conditions, leading to a more stable coastline. In this case, ecological perturbation by tourism or by free pasture destabilizes the dune field, even if storminess is not particularly high. This is very clear with the post-1945 mobility of the dunes at the Bay of Audierne, which were also strongly perturbed by sand exploitation and tourism [START_REF] Hallégouët | Les crêtes littorales dunifiées du Massif Armoricain : formation et évolution[END_REF]. For the XVII th century, free pasture, vegetation clearance for agriculture on sand, and seaweed yield strongly perturbed the dunes in Brittany; this occurred in combination with reclamation of the upper tidal marsh areas in back ridge positions. This situation was accentuated since the Second World War by quarrying of the dune, and onshore and offshore sands exploitation, leading to a very negative sediment budget [START_REF] Guilcher | Coastal dunes in Brittany and their managment[END_REF].

Dunes have recycled the same stock of sediment, which was already limited in Brittany for geological reasons, with the slowing down since 3000 years of the transgression, although this has been somehow re-accelerated by the recent warming. The dissipative state of beaches underlying dune ridges, as in the Bays of Audierne, of Goulven and at Guisseny, signals a continuing longshore depletion of ridge sediment by erosion [START_REF] Short | Wave, beach and dune interactions in southeastern Australia[END_REF]. Inland sand drift was important during the historical dune formations, but seem limited to local inland recycling since the LIA (dry storms).

Giant LIA storms have resulted in the second major retreat of the coastline, despite some supply of sediments by forest clearance in Merovingian times River dam construction for water or tide mills activities limited the sand supply in Western Brittany from the XI th century. LIA dunes are less calcareous at the bay of Audierne or are richer in organics, as in Picardy, attesting to the reworking of the stabilized bodies. The existence of "dead" dunes perched on cliffs (Fig. 1a) also attests to a depleted sedimentary stock. A less negative budget along the South Brittany coast explains the latter preservation of coastal dunes (mostly formed after the XI th century), which are now endangered by both onshore (dune quarrying) and offshore sand exploitation.

As very important storms are associated with tall waves, up to 15 m high on the platform, sands are not only exported to the shallow nearshore (<10 m of depth), but are also reworked to a depth exceeding -30 m, leading to progressive sediment exportation by shelf currents to the platform edge [START_REF] Fan | River flooding, storm resuspension, and event stratigraphy on the northern California shelf: observations compared with simulations[END_REF], Guillen et al., 2006;[START_REF] Goff | Sedimentary differences between the 2002 Easter storm and the 15th Century Okoropunga tsunami, southeastern North Island, New Zealand[END_REF], a process particularly efficient with dry storm (Guillen et al., 2006). This suggests that there is, in many places and especially in Brittany, no large sediment volume available on the beach for a future period of dune building, as was already stressed for UK by [START_REF] Orford | Holocene coastal dune initiation in Northumberland and Norfolk, eastern UK: climate and sea-level changes as possible forcing agents for dune initiation[END_REF].

Climate global control

During cold events on Europe, typically associated with negative NAO modes and solar lows, precipitation is usually reduced (Hurrel, 1995), whilst aeolian aggradation may result from moderate but frequent gales, thereby favouring the development of coastal dunes without or on former storm ridges. The extent of sea ice explains a more accentuated cooling of the western Atlantic Ocean, as occurred during the LIA [START_REF] Miller | Abrupt onset of the Little Ice Age triggered by volcanism and sustained by seaice/ocean feedbacks[END_REF] in association with a negative, decennial NAO mode [START_REF] Trouet | Persistent positive North Atlantic Oscillation mode dominated the Medieval Climate anomaly[END_REF]. Moreover, a sea-ice triggered cooling is consistent with a limited regression of a thermosteric nature (≤ 0.5 m; [START_REF] Lamb | Climate, History and the Modern World[END_REF]. More frequent solar minima from the Roman time [START_REF] Usoskin | Grand minima and maxima of solar activity: new observational constraints[END_REF] resulted in a more frequent negative NAO mode, sea-ice extent and storminess.

Additionally, dunes are strongly influenced by anthropic practices that artificially favour dune mobility, especially from the late Roman time. These practices induce sediment-supplying soil erosion with a rhexistasy dynamic of the coastal zone. We may thus suspect that within a context of rising SL, the occurrence of dunes is a man-made temporary and endangered anomaly of the Late Holocene HS.

This conclusion is similar but more obvious than in a high sand supply environment as in Denmark [START_REF] Clemmensen | The evolution of Holocene coastal dunefields, Jutland, Denmark: A record of climate change over the past 5000 years[END_REF]. We think that within a context of rising SL, the occurrence of dunes is a man-made temporary anomaly of the Late Holocene, soon to be erased by both naturally and man-driven sediment starvation. This will result in the progressive disappearance of dunes with, consequently, higher risks for coastal submersion at these locales.

CONCLUSIONS

  Dune development in Brittany only occurred during the latter part of the Holocene stratigraphic record as a result of abnormal sand supply. Even though dunes appeared sporadically c. 4000 cal BP (although not earlier), the first real dune building occurred from 3-2.75 cal kyr BP in close connection with the slowing down of the Holocene transgression from 3 cal kyr BP and agriculture development.. As a result, dune fields were limited along most Brittany coasts, and later in southern Brittany where the sand supply was higher. The favorable building conditions for dunes are recurrent gales associated with dominant negative NAO mode. Most parts of the so-called dune ridges are storm ridges along the southern coast of Brittany that are only topped by dunes, and formed mostly from 900 -1200 AD and during later periods of major storms driven by brief positive NAO event in a decadal NAO negative mode. Along the North coast, dunes have a similar timing as in Picardy and Normandy, although erosion by major storms at the transition of the XVI-XVII th centuries was responsible for the main storm ridge at the present coastline. Prior to the XX th century, dunes were represented regionally by thin sheets of sands, burying coastal relief and reworking mostly the top and the back of the coastal ridge. Many local dune fields have already disappeared.

FiguresFig. 1 :Fig. 2 :

 12 Figures

  Santec on the northern coast ofBrittany (c. 2420 cal BP, Morzadec, 1974). The first well-recorded building of the dunes occurred between 2450-2350 cal BP at the Bay of Audierne(Van Vliet-Lanoë et al., 2014a). Here, a true storm ridge was topped with a dune dated to 2339 -2487 cal BP(Van Vliet- Lanoë et al., 2014a) as also at the Anse du Verger (NE Brittany c. 2170 cal BP[START_REF] Pye | Holocene sea-level variations and geomorphological response: an example from northern Brittany (France)[END_REF]

  with a renewed dunes invasion. This period was marked by giant storms, well-recorded at 900 AD in southern Brittany(Van Vliet-Lanoë et al., 2014b). A limited stabilisation was observed from 1000 to 1200 AD, which was recorded in the form of humic soils or peaty layers in the region, although it was frequently interrupted by giant storms in the form of washover fans during the XI th century(Van Vliet-Lanoë et al., 2014b). Around Brittany, the ridges were often truncated and/or buried by sand drift or splay (Table1; Fogéo: Visset and

Bernard, 2006 Treffiagat, la Torche and Pors Milin: Van Vliet-Lanoë et al., 2014a; Baie des Trépassés:

  . From that time, the HWM reached the present-day LWM, allowing an easier accumulation of sediment in the upper beaches. This indicated the onset of the Holocene high stand. The sediment supply lowered mechanically due to a slower SL rise and more limited coastal erosion, mostly driven by storm activity,

	especially during cold events (Van Vliet-Lanoë et al., 2014b), but temporarily rose by soil erosion
	resulting from Bronze Age forest clearance.
	Historical dunes tell another story: the dunes are preserved at the northern and western coast at the
	Roman time, but did not yet exist as a coastal ridge in the South. A first splay of sands from 350 to 600
	and from 700 to 800 AD is recorded in Brittany. The onset of the historical dunes I is well developed
	at a wider regional scale, in SW Cotentin (Fig. 1; Meurisse-Fort, 2009) or in the Scillies' Islands -(250 -
	330 AD Banerjee et al. 2001). Some storms were recorded around 540 -600 AD and 680 -720 AD in
	Brittany (Van Vliet-Lanoë et al., 2014b), separated by a brief stabilization (640 -760 AD; Patterson et
	al.

Table 1 :

 1 New dating from dunes bodies, Brittany. For location see Fig.1

ACKNOWLEGMENT

This work was funded by the French Research Program (ANR) COCORISCO (2010-CEPL-001-01).

We also thank Barbara Maüz and Christophe Morhange for improving in language the expression of our ideas and their constructive comments.


Julien Tanguy
email: julien.tanguy@see4sys.com

Jean-Luc Béchennec
email: jean-luc.bechennec@irccyn.ec-nantes.fr

Mikaël Briday
email: mikael.briday@irccyn.ec-nantes.fr

Olivier-H Roux
email: olivier-h.roux@irccyn.ec-nantes.fr

Reactive embedded device driver synthesis using logical timed models

Keywords: Real-Time Systems, Formal Modeling, Control, Logical Time, Software Synthesis

The critical nature of hard real-time embedded systems leads to an increased usage of Model Based Design to generate a correct-by-construction code from a formal specification. If Model Based Design is widely used at application level, most of the low level code, like the device drivers, remains written by hand. Timed Automata are an appropriate formalism to model real time embedded systems but are not easy to use in practice for two reasons i) both hardware and software timings are difficult to obtain, ii) a complex infrastructure is needed for their implementation. This paper introduces an extension of untimed automata with logical time. The new semantics introduces two new types of actions: delayed action which are possibly avoidable, and ineluctable action which will happen eventually. The controller synthesis problem is adapted to this new semantics. This paper focuses specifically on the reachability problem and gives an algorithm to generate a controller.

Motivation

Nowadays embedded systems realize many critical functions. From avionics to automotive electronics control systems, the software has grown in size and its complexity has become more important.

The increasing number of functions and complexity of such systems make software development very difficult due to a high level of concurrency and to the hard real-time context. Many safety-critical systems now cooperate in real-time on several ECUs across many communication links.

Due to the critical nature of these systems, software vendors have to prove the functional safety of their systems. Unit and functional tests are common requirements, but they do not guarantee the software is bug free. The automotive community is now pushing for a more formal verification of the systems' behavior.

Model Based Design (MBD) methodologies are now widely used in the industry and are a way to address the complexity of these systems.

Instead of writing the code by hand the engineer models the system to control and builds a model of the application. The models can be tested and simulated. They can also be verified if their spatial and temporal complexity and their size remain practicable. At last the code is generated automatically from the model. In the automotive industry the AUTOSAR standard (Kirschke-Biller, 2011) proposes a framework for MBD. It specifies an architecture and a methodology for the design of such systems, based on current development methods, design best practices and applicable international standards (such as the ISO26262 norm (The International Organization for Standardization, 2011)).

However if MBD is used at the application level, basic software especially device drivers remain coded by hand and are more prone to have bugs. For example in the AUTOSAR standard the basic software is a set of modules. These mod-Core Model Cfg Model

Core

Cfg + bin Dead code This high level of configurability at every level increases greatly the complexity of such systems; they usually require multiple modules and abstraction levels. It can also result in a lot of dead code and if the configuration is not perfectly tuned to the application demands, so that unnecessary behaviors make it into the code and may be executed. This comes at the cost of decreased performance and greater memory footprint, in terms of stack size, ROM and RAM usage. The consistency of the configuration must also be checked in order to be sure that the driver cannot behave in an unspecified way.

The proposed approach. Instead of doing complex verification on existing systems, we propose to use an MBD approach to generate the device driver. However, to reduce the flaws of the current methodology, we combine the use of formal models, the lifting of configuration at the model level and well-known controller synthesis techniques [START_REF] Ramadge | The control of discrete event systems[END_REF] to generate correct-by-construction software.

Given the real-time nature of these systems, the model of timed automata [START_REF] Alur | A theory of timed automata[END_REF] and timed games [START_REF] De Alfaro | The element of surprise in timed games[END_REF] is an appropriate formalism to express and model the required timed properties. In a timed game, we model two players, the controller and the environment, playing moves at a certain time on a shared model called the board. The board represents all possible states of the two players and the possible actions available at all times. In this case, the controller is the device driver, and the environment is the hardware device along with its environment (communication bus, analog signals, etc.). Moves played by the device driver are also known as controllable actions and moves played by the hardware device and its environment are known as uncontrollable actions.

Their level of expressiveness and wellknown controller synthesis techniques and tools [START_REF] Behrmann | Uppaaltiga: Time for playing games! In Computer Aided Verification[END_REF] allow the modeling of complex systems, while providing a formal proof on the behavior of the systems.

However, these timed models require a good understanding of all the components, including the knowledge of the timings of both players. These timings are rarely known: the hardware timings are not always described exhaustively, and the software execution times are rarely known precisely.

In addition, embedded systems hardware resources (computing power, memory, etc.) are limited. The basis of timed controlled, namely explicit clocks, are very expensive to use in a critical embedded environment. Implementation wise, the infrastructure needed to implement these clocks in a timed controller is not acceptable for implementing real-time systems at low level such as device drivers. In order to function properly, a timed driver may need an exact timing. These exacts timings do translate into low-level software to hardware clocks triggering interrupts each time a controller needs to wait during an arbitrary amount of time. Even with this, a controller cannot guarantee all the timing constraints, because interrupts might have been masked for a certain computation.

Our contribution. In this paper, we explore another way of modeling embedded systems, starting from peripheral devices. We would like to derive a controller -a device driver -without explicit timed models. However, the untimed automata framework does not have the necessary level of expressiveness in order to generate useful drivers.

Beside the controllable and uncontrollable actions used in untimed games, device drivers rely on additional behavior of the device in order to work. This behavior can be reduced into two types of uncontrollable actions:

• Delayed actions, which take time to complete or cannot happen immediately, such as writing to an external memory, sending a message on a bus, performing a specific computation on a hardware dedicated unit, etc. These actions come usually with some kind of abortion mechanism, so they are avoidable in a certain point of view. They are modeled in an explicit timed context by guards with lower bounds on clocks as constraints.

• Ineluctable actions, which are known to happen in a nominal context: the end of a transmission or a conversion, or more generally an acknowledgement of the reception of a command. These can be modeled using invariants on states, however in the explicit timed context we need to know an upper bound on the delay, which is not always possible with a quantitative approach.

We propose to extend the semantics of untimed games with two properties of uncontrollable actions: avoidability -an avoidable action cannot disrupt the behavior of the driver -and ineluctability -the driver can rely on these actions to happen.

We will derive the traditional controller synthesis problem for reachability games in this context.

Logical timed game automata

In this section we propose a variant of the traditional untimed game automata with new logical-timed semantics. The modified semantics of actions let us express two important notions of timed automata: delay and urgency. Without these notions, it is impossible to write an untimed controller while keeping the element of surprise. The element of surprise is necessary in this context: a device driver should be able to react to any hardware interrupt when it happens.

Without delays, we cannot express the fact that an hardware action (such as analog conversions, or emitting a message on a com bus) takes times, and as such the device driver can perform actions, even aborting the current operation (see Figure 3). Without urgency, we cannot model any predicted behavior of the device. In these kind of games, the device is expected to play every move at its disposal to make the controller fail, including choosing not to play, even if the controller cannot play any move in the current state. As such, it would not make sense to wait for something to happen (see Figure 4).

As we do not want real-valued clocks, we define a logical time semantics for game automata. It is based on the classical definition G = (Q, q 0 , A C , A U , δ) where

• Q is a set of states • q 0 ∈ Q is the initial state • A C and A U are two disjoint sets of actions
for the controller and the environment, respectively.

• δ : Q × (A C ∪ A U ) × Q a set of edges between states.
We denote q a -→ q for (q, a, q ) ∈ E.

In addition to this definition, we also define A a U ⊆ A U and A U ⊆ A U the subsets of avoidable and ineluctable actions, respectively. Note that these subsets are independent, and may or may not intersect.

These subsets reflect a finer model of the environment: avoidable actions are actions which cannot happen instantaneously, such that we are able to avoid or abort them before they have a chance to happen. Ineluctable actions, on the other hand, can reasonably expected to happen, unless a major failure occurs.

For the rest of this paper, we will consider an arbitrary game G = (Q, q 0 , A C , A U , δ). For the following figures, we will use the following notations:

• States are represented in circles, and the initial state is denoted q 0 .

• Controllable transitions are represented in solid arrows.

• Uncontrollable transitions are represented in dashed arrows.

• Avoidable transitions start with a circle.

• Ineluctable transitions end with a double arrowhead.

Definitions

For X ⊆ Q and Σ ⊆ A C ∪ A U , we define the predecessor and successor functions pre Σ :

2 Q → 2 Q , suc Σ : 2 Q → 2 Q : ∀q ∈ Q, q ∈ pre Σ (X) iff ∃a ∈ Σ and q ∈ X, s.t. q a - → q , and ∀q ∈ Q, q ∈ suc Σ (X) iff ∃a ∈ Σ and q ∈ X, s.t. q a - → q. If Σ = A C ∪ A U , we note pre(X)
and suc(X)

For i = C, U , we define Γ i : Q → 2 Ai ∪ {⊥}, with ⊥ / ∈ A i the enabling conditions. For q ∈ Q, Γ i (q) is the set of available moves for player i. The q 0 q 1 q 2 q 3 q 4 q 5 c u ua ui uai

∈ AC , u ∈ A a U , ua ∈ A a U , ui ∈ A a U and uai ∈ A a U .
q 0 q 1 q 2 q 3 start recv recv recv read read Figure 3: Rx part of a communication device: the uncontrollable actions recv represent the reception of a message. In q1 the data register is empty, in q2 it is full and in q3 it is overwritten. Because the transmission of a message takes time, two immediate and consecutive receptions cannot happen. In this situation, we are able to express the ability for the driver to perform a read action between two recv, and avoid q3.

special action ⊥ represents the act of choosing not to play in this state. We denote by ∆ the set {0, •}. It represents the logical time at which an action is played. It can be instantaneous (0), or unknown (•).

A run of a game structure is the sequence q 0 , a 1 , t 1 , q 1 , a 2 , t 2 , q 2 , . . . with t i ∈ ∆, such q 0 q 1 send end Figure 4: Tx part of a communication device: the uncontrollable action end represent the end of transmission interrupt. Because of the way the bus may be structured, or saturated, we do not know an upper bound on the reaction time, only that it will happen eventually.

that q i ∈ Q and q i ai -→ q i+1 for all i >= 0. Semantically, a, 0 means that the action a is performed immediately, whereas in a, • , the action is performed at an unknown time, possibly zero. We denote by R the set of runs, and by R the set of finite runs.

For r ∈ R, we define First(r) the first state of r, States(r) the set of states which appear in r, and Act(r) the set of actions which appear in r. If r ∈ R, we define Last(r) the last state of r.

We define R s the set of reliable runs, which do not depend on uncontrollable actions:

r ∈ R s ⇔ Act(r) ∩ A U = ∅ For R ⊆ R and X ⊆ Q, we denote by R| X the subset of R such that ∀r ∈ R| X , States(r) ⊆ X.

Controller synthesis

In this section, we will solve the controller synthesis problem using our modified semantics. The goal is to derive a strategy for the controller to restrict the behavior of the game.

A strategy s i for player i is a function s i : R → 2 Ai ∪ {⊥} × ∆. It is said to be memoryless if it only depends on the current state of the run, i.e.

s i : Q → 2 Ai ∪ {⊥} × ∆.
Let G = (Q, q 0 , A C , A U , δ) be a game structure, and s C a strategy for the controller. We define the outcome Outcome(q, s C ) of a strategy the subset of R defined inductively by:

• q ∈ Outcome(q, s C ) • If r ∈ Outcome(q, s C ) is finite, r = r a - → q ∈ Outcome(q, s C ) if r ∈ R and -a ∈ A a U ; -a ∈ A a U and (r a - → q s.t. a , 0 ∈ s C (r)). -a ∈ s C (r).
• An infinite run belongs to Outcome(q, s C ) if all its finite prefixes also belong to Outcome(q, s c )

If q = q 0 , we simply write Outcome(s C ). The control synthesis problem can be declined into objectives, or winning conditions. For a given game G, a winning condition C W is a set of allowed runs. A strategy s for the controller is winning if Outcome(s) ⊆ C W .

The result of applying a strategy on a game is also a game whose set of runs is exactly the outcome of the strategy. We will use both definitions indifferently.

Relation to timed Games It is possible to express some of our semantics using timed games, as in [START_REF] De Alfaro | The element of surprise in timed games[END_REF][START_REF] Behrmann | Uppaaltiga: Time for playing games! In Computer Aided Verification[END_REF]. The avoidable actions for example, translate directly into guards with a lower bound on clocks and vice versa. However, the ineluctability cannot be translated as-is into and from timed automata. We can use invariants on states to force the environment to play, but as the model uses explicit clocks, we have to express an upper bound on the invariants. Our extension here removes this need for explicits values or parameters. It restricts only the behavior of the environment, not of the controller, as it is in timed automata because invariants apply to all players including the controller.

Reachability games

A reachability objective of the controller is to force the game to reach a certain set of states. Formally:

Definition 1 (Reachability objective). Let G = (Q, q 0 , A C , A U , δ) be a game, and Goal ⊆ Q a set of goal states. A run r ∈ R is winning if it has a finite prefix r such that Last(r ) ∈ Goal. The set of winning runs is denoted Reach(Goal).

q 0 q 1 G w s

Computing the strategy

The computation of the strategy is obtained from the set of winning states. A state is winning for the controller if it is possible to reach a goal state. The main algorithm for computing winning strategies for reachability games is a backwards fixed-point algorithm over the controllable predecessor function.

Intuitively, a state s is a controllable predecessor of X if the following conditions are met:

• there is an action which is guaranteed to happen (either controllable or uncontrollable ineluctable);

• all other actions of the environment cannot prevent the game to reach a state in X.

Definition 2 (Controllable predecessors). Let G = (Q, q 0 , A C , A U , δ) be a game, and X ⊆ Q a set of states. The controllable predecessors π(X) of X is the subset of Q defined by:

π(X) = pre C (X) \ pre U a (X) ∪ pre U (X) \ pre U (X) (1)
The two parts of the formula represent two different ways to win:

• if there is a controllable action from s to a state in X, all uncontrollable actions must either be avoidable, or also lead to states in X

• if there is an ineluctable uncontrollable action, all other uncontrollable actions must also lead to a state in X.

The set of winning states is computed using a backwards fixed-point algorithm.

Algorithm 3 Reachability computation algorithm

Require: Goal Ensure: W W ← Goal while π(W) = W do W ← W ∪ π(W) end while if initial ∈ W then return Success else return Failure end if
From the set of winning and goal states, we can derive a non-deterministic, memoryless strategy for the controller. The canonical memoryless strategy s m c : W → (2 A C ∪ ⊥, ∆) is defined by:

s m c (q) = ⊥if a ∈ A C , q a - → q , q ∈ W, { a, d |a ∈ A C , q a - → q , q ∈ W}, where d =      0 if ∃a ∈ A a U , q ∈ Q \ W such that q a - → q , • otherwise.
(2)

Correctness of the computed strategy

The partial definition of s m c on W makes sense because the strategy does not allow leaving W (Lemma 5). Note that in the first case, the controller waits for an uncontrollable ineluctable action to occur, which is bound to happen by defi-nition of ineluctable actions, and because the current state is in W. The second case just cuts off transitions which would lead to loosing states.

The following lemmas and theorems hold if Algorithm 3 returns successfully. To simplify the formulation of the results we will always assume that it returns successfully. For our game G, let us consider a reachability condition in the form of Goal ⊆ Q. We will assume that the algorithm returns successfully and computes the set W of winning states.

Lemma 4 (Winning states). From all states in W, there is a sure run to a state in Goal, i.e. ∀s ∈ W, ∃r ∈ R s such that First(r) = s and Last(r) ∈ Goal.

Proof. We will proceed by induction. We define the following sequence:

W k = Goal if i = 0, W i-1 ∪ πW i-1 otherwise.
It is trivial to see that for all states in W 0 , there is a sure run for a state in Goal. If the property holds for n ∈ N, we can show that it holds for n+1 by finding a run from W n+1 to a state in W n , from which we have a sure winning run. From the definition of π, we can see that, for all states q ∈ W n+1 : ∃a ∈ A C , q ∈ W n such that ∃q a -→ q and a ∈ A a U , q ∈ W n , q a -→ q ,

(3) or ∃a ∈ A U , q ∈ W n such that ∃q a -→ q and a ∈ A U , q ∈ W n , q a -→ q .

(4)

Because the sequence is monotonic and the set of states is finite, it necessarily converges to a limit, W.

Lemma 5. Given s m c defined by Equation 2, we have Outcome(s m c | W ) = Outcome(s m c ). That is, the application of the strategy does not leave W.

Proof. Let us procede by contradiction. Let's suppose that there is a run r ∈ Outcome(s m c ) \ Outcome(s m c )| W . Assuming our hypotheses, that means that there are one or several intermediate states in r which are not an element of W. It cannot be first because q 0 ⊆ W by definition. Let's take q the first of these states, and denote by p the state just before q, and a the action such that p a -→ q is an infix of r. We have q ∈ W and p ∈ W.

By definition, we also have a / ∈ A U . By definition of the outcome, we have one of the following cases:

a ∈ A a U (5) a ∈ A a U and (p a - → q s.t. a , 0 ∈ s m c (p)) (6) a ∈ s m c (r). (7)
The case of 7 is not possible by definition of s m c , and because q / ∈ W. This would lead to a contradiction of the hypothesis.

If a ∈ A a U (5), then by definition we have p ∈ pre U a (W), and p ∈ pre U (W). By definition of π, we have p / ∈ π(W), thus p / ∈ W by definition of W. We would have a contradiction too.

Let's consider the case (6). The fact that there is no possible move a , 0 ∈ s m c (p) implies that s m c (p) = ⊥. Thus, we have p / ∈ pre C (W). Because a ∈ A U , we have p / ∈ π(W), thus p / ∈ W by definition of W.

Since all possible cases lead to a contradiction, the hymothesis is false and thus the lemma holds.

Lemma 4, proves that the game is possibly winning for the controller, with the right strategy.

We cannot prove that our generated controller includes all and only the winning runs, since it allows infinite runs (see Figure 6). We must however assure that the strategy is safe and sound, in that it does not capture loosing runs, and all winning runs are captured. Theorem 6. For all r ∈ Outcome(s m c ), r ∈ R =⇒ ∃ρ ∈ R s s.t. rρ ∈ Reach(Goal)and rρ ∈ Outcome(s m c ) Proof. If any finite run r does not leave W, we have Last(r) ∈ W. Thus, by Lemmas 4 and 5 there is a finite winning run r ∈ R s such that r ∈ Reach(Goal), and rr ∈ Outcome(s m c ). Formally,

∀r ∈ Outcome(s m c ), States(r) ∩ W = ∅. Lemma 7. For all r ∈ (Reach(Goal) ∩ R s ) | W , we have either      r ∈ Outcome(s m c ), or ∃r ∈ Outcome(s m c ), such that r ∈ (Reach(Goal) ∩ R s ) | W . Sketch of proof. From Theorem 6, we know that Outcome(s m c ) ⊆ R s | W .
For a given run r ∈ (Reach(Goal) ∩ R s ) | W , it can either be in Outcome(s m c ) or not. In the latter case, the run has been cut at a certain point because a different action from the environment could have spoiled the outcome of the game (see Figure 7).

q 0 q 1 W q 2 a c b d
Figure 7: Example of a winning run cut by our strategy. The winning run bc is cut because the controller takes a immediately in order to prevent the environment to take d.

Because Algorithm 3 returns successfully, we can construct a sure winning run from every state in W, so there is another winning run.

As a consequence, we can state the following theorem about the existence of solutions and our ability to capture them.

Conclusion

In this paper, we have presented a semantic extension of untimed automata to introduce the model based design methodology in the conception of low level software for embedded systems. This extension introduces two uncontrollable actions' properties that extend the model of the environment:

• the delayed action cannot happen instantaneously so that the device driver can perform another action if needed.

• the ineluctable action is guaranteed to happen eventually, and on which the driver can rely.

This model combines some of the expressiveness of timed games, with the simplicity of untimed automata. It allows an easier implementation of these models, more suitable to embedded real-time systems.

We have adapted the notion of control and reachability games for this extension and defined and proved an algorithm to solve these problems in the general case.

However, the generated strategy can be nondeterministic, and allows infinite runs (one can switch infinitely many times between two states before reaching the goal). In practice, we need to find a deterministic implementation of the strategy that finds the shortest path and eliminating loops.

The goal of this work is to provide the complete toolchain to model, configure and generate the device driver code for any given system. In order to do so, we must extend the controller synthesis to safety games, which deals with avoiding bad states. We will also propose a generic implementation of the resulting controller to complete the methodology.

Figure 1 :

 1 Figure 1: Current development methodology

Figure 2 :

 2 Figure 2: Graphical notation example: Here q0 is the initial state, and c∈ AC , u ∈ A a U , ua ∈ A a U , ui ∈ A a U and uai ∈ A a U .

Figure 5 :

 5 Figure 5: Example reachability game. The objective is to reach the state G.

Figure 6 :

 6 Figure 6: Possibly infinite game: the canonical strategy allows to do a infinitely many times before b.

Theorem 8 .

 8 If Reach(Goal) = ∅, then Outcome(s m c ) = ∅.