Vivian Depoues

Organizational uptake of scientific information about climate change by infrastructure managers: the case of adaptation of the French railway company

Keywords: adaptation, infrastructure, railways, organization, climate change, decision-making

Future development and renewal of transport infrastructures have to take into account how the effects of climate change will affect these complex sociotechnical systems. This article aims at understanding how to raise this issue to ensure an efficient and systemic uptake of climate change by infrastructure managers. It reports the results of an in-depth case study conducted on the French railway company. This study identifies several adaptation dynamics: one is top-down and stems from climate change impacts; others are more bottom-up and focused on vulnerabilities. However, both types of approaches have, so far, yielded limited results. Building on the existing literature, this paper reveals critical bottlenecks to overcome in order to get the organization ready to adapt. It suggests key components of an enabling framework for a more proactive preparation to climate change and mainstreaming climate adaptation into major organizational decisions.

INTRODUCTION

In a context of climate change, the development and renewal of infrastructures is a critical challenge (European Commission 2013;Chappin and van der Lei 2014;[START_REF] Larrivée | Lapérennité Des Bâtiments et Des Infrastructures[END_REF][START_REF] Stecker | The Role of Government in Making Infrastructure Investment Climate Resilient -Draft Survey of Current Practices[END_REF][START_REF] Masood | Towards the Future-Proofing of UK Infrastructure[END_REF]OECD 2015;[START_REF] Forzieroi | Resilience of Large Investments an Critical Infrastructures in Europe to Climate Change[END_REF]ToPDAd 2014). In the coming years, thousand billions of euros will have to be invested in transport, energy, water and telecommunication networks to preserve the connectivity, the efficiency and the resilience of the economies (The new climate economy 2014; [START_REF] Dobbs | Infrastructure Productivity: How to Save $1 Trillion a Year[END_REF]Vallejo and Mullan 2016) 1 . Those infrastructures will have lifetime expectancies of several decades and will therefore be exposed to the impacts of climate change.

Railways play a structuring role in the European economy as they "facilitate the production and distribution of goods and economic services, and form the basis for the provision of basic social services." (European Commission 2013). In Europe, most of the railway managers are big companies founded in the 19 th or 20 th century that today have to face important asset management challenges (e.g. aging infrastructure, underinvestment in the last decades, important evolution of technologies and mobility patterns).

Several research programs have analyzed climate change implications in this context (UIC 2011;EEA 2014;[START_REF] Baker | Climate Change and the Railway Industry: A Review[END_REF][START_REF] Nemry | Impacts of Climate Change on Transport: A Focus on Road and Rail Transport Infrastructures[END_REF][START_REF] Koetse | The Impact of Climate Change and Weather on Transport: An Overview of Empirical Findings[END_REF][START_REF] Armstrong | Adapting Railways to Provide Resilience and Sustainability[END_REF], often focusing on infrastructures' vulnerability. A few case-studies have been conducted at national and sub-national levels, for instance in Sweden [START_REF] Lindgren | Climate Adaptation of Railways: Lessons from Sweden[END_REF], Germany, Austria [START_REF] Dobbs | Infrastructure Productivity: How to Save $1 Trillion a Year[END_REF][START_REF] Rotter | Competing Priorities: How Actors and Institutions Influence Adaptation of the German Railway System[END_REF]) and the UK [START_REF] Rssb | Tomorrow's Railway and Climate Change Adaptation: Phase 1 Summary Report[END_REF]. They generally observed limited action in terms of large-scale investments but a reasonable level of awareness on climate change and a common focus on research and knowledge sharing. Very often, they focus on strengthening resilience to current hazards as a 'no-regret' option to start preparing for an uncertain future. This existing work also pointed at the increasing need to develop forward-looking thinking and to proactively integrate climate change concerns early in planning and decision processes. This literature shows how adaptation is not just a technical matter but also an institutional and organizational issue questioning values and priorities. As such, adaptive capacity relies on elements like governance, procedures or leadership [START_REF] Berkhout | Adaptation to Climate Change by Organizations[END_REF][START_REF] Stecker | The Role of Government in Making Infrastructure Investment Climate Resilient -Draft Survey of Current Practices[END_REF].

This paper follows up with these projects and reports the results of an in depth analytical case study on the management of climate adaptation of the French railway system.

In France, the main player in the railway sector is a state-controlled group created in 1938 and called SNCF (Société Nationale des Chemins de Fer Français). It encompasses both the management of the network (with SNCF Réseau) and part of the operation of this network (with SNCF Mobilités). It is under the supervision of the transport department of the French Ministry of the Environment.

The French railway network is the second largest in Europe with more than 30,000 km of tracks and 3,000 passenger terminals. Fifteen thousand trains use this network daily, in carry 5 million people and 32Gt-km of freight every year. Climate change could produce severe disruptions in this network and adaptation is therefore a crucial collective concern. Nevertheless, where and how this issue should be raised and handled in such a big and complex organization is an issue without a straightforward answer. As a matter of fact, SNCF has about 150 000 employees and more than 650 branches -where decisions are distributed and shaped by various factors.

This paper, intends to understand how a big organization such as a national railway network manager can mainstream and increase the internal uptake of the issue of climate change. It aims at explaining how an infrastructure manager (IM) can integrate scientific knowledge about climate change into its decision-making process in order to implement adaptation strategies.

First, materials and methods of the case study are introduced. Then the article describes two types of observed approaches to adaptation. These are qualified after the IPCC (IPCC 2014) as impact-first and vulnerability-first, depending on where they start and how they frame climate change and related uncertainties.

The limitations of these approaches are discussed. The second part of this paper describes the critical bottlenecks to overcome in order to increase the organization's readiness to adapt. Building on theoretical and empirical results available in the literature, it identifies key elements to build an enabling framework for a more proactive preparation to climate change and to mainstream adaptation into the decision-making process.

Analytical framework, materials and methods

Rooted in the field of science and technology studies (STS), this research adopts a descriptive approach and sees adaptation not only as an engineering issue but also as a sociotechnical concern [START_REF] Latour | Changer de Société[END_REF][START_REF] Edwards | Infrastructure and Modernity: Force, Time, and Social Organization in the History of Sociotechnical Systems[END_REF]. It focuses on the interface between knowledge on climate change, the technical infrastructure and the organization as part of its socio-economic environment. It questions how climate change is understood and how this affects such a complex system. Moreover, this approach takes into account how organisational, corporate and economic values affect how the system understands and deals with the impacts of climate change [START_REF] Hulme | Why We Disagree about Climate Change[END_REF]).

In the objective of analysing the way the organisation is integrating adaptation, the article does not intend to evaluate which approach could be more relevant or efficient. It identifies and describes various initiatives contributing to adaptation, going from incremental reactive adjustments to enhance resilience to current weather down to significant transformations anticipating future changes [START_REF] Saint-Marc | Approches Cartographiques Pour Une Meilleure Connaissance Des Dynamiques Spatio-Temporelles Des Risques Naturels : Application Aux Risques D'inondation Impactant Le Réseau Ferroviaire[END_REF][START_REF] Adger | Social Capital, Collective Action, and Adaptation to Climate Change[END_REF][START_REF] Jouzel | Le Climat de La France Au {XXIe} Siècle Volume 4 Scénarios Régionalisés: Édition 2014 Pour La Métropole et Les Régions D'outre-Mer[END_REF]. This research did not intend to be comprehensive but aimed at covering a diversity of management functions2 . In order to do so, twenty-five in-depth semi-directed interviews supplemented by secondary sources analysis have been conducted. The interviews allowed to engage into discussion with:

-People working in different units of the company:

 Transversal support units in charge of corporate sustainability, standardisations and procedures, socio-economic analysis;

 Technical units in charge of design and engineering ;  Units in charge of operation and maintenance planning and management.

-People intervening in the elaboration of adaptation strategies:

 Representatives of the French Ministry for Environment;  Governmental technical agency (CEREMA);  French national meteorological service (Météo France ).

Case study: where and how is the adaptation question raised?

The analysis shows there are many places within the organisation where adaptation dynamics can start. Indeed, we have observed several initiatives explicitly seeking to contribute to climate adaptation in different departments and along various processes.

i) First adaptation strategy observed: starting from projected impacts

In the last decades, concerns about climate change were raised by the publication of scientific results (five IPCC assessment reports between 1990 and 2015) and political discussions at supranational and national levels. This led to the adoption of "adaptation plans" at various levels of administration: ex. SNCF's contribution to this action-sheet was the starting point for an internal discussion on adaptation. The attention was mostly focused on the first action: the screening of technical standards containing references to climate parameters that needed to be updated according to the expected climate changes (CEREMA, 2015).

This approach is representative of what IPCC's reports refer to as an "impact-first" approach or "top-down, science-first or standard approach" (IPCC 2014 Chapter 2). Tasks are clearly distributed: science is an upstream activity that provides information for the decision about the future as a finished product 7 . Climate projections are generated "for wide application, and thus are not tied to any specific choice". Therefore, very little direct interaction is expected between climate scientists and the IMs who eventually use the information.

Climate change as an external constraint.

In accordance with this linear approach, climate change is knowable, controllable and constitutes a specific issue. Scientific information is provided in a top-down manner to fill a knowledge gap [START_REF] Blanchard | Reflexive Interdisciplinarity -Supporting the Dialogue on the Role of Science for Climate Change[END_REF]) and can result for instance in the modification of an existing temperature threshold in a normalized procedure such as rail installation. Even though individuals may acknowledge the complexity of the climate system and how it interacts with the sociotechnical infrastructure system, the adaptation process itself reduces this complexity by making simplified assumptions [START_REF] Kane | Communicating Risk through a DSS: A Coastal Risk Centred Empirical Analysis[END_REF], for instance causal links between impacts and vulnerability. Consequently, the proposed responses are direct and incremental. Missing pieces of information are identified and demanded to scientists with no dialogue on the feasibility, relevance or costs of the necessary research (CEREMA 2015) 8 . Climate uncertainties are treated independently from others components of the situation.

Limitations encountered: a limited appropriation across the IM activities.

At the end of the period covered by the 1 st French PNACC (2011)(2012)(2013)(2014)(2015), sensitive standards were identified but not yet updated (CGEDD 2015). This approach failed to produce an engagement strong enough to go beyond a formal assessment of the procedures.

According to interviewees who were involved in this process, it was not specific enough and not self-sufficient.

Making it operational in the context of the railway system would have required a large amount of work with dedicated resources the PNACC did not provide. Moreover, no tailor-made climate change indicators were delivered beyond generic climate projections. Indeed, there is no link between indicators in the Jouzel Reports and much more specific parameters currently used in the industrial processes (for instance temperature thresholds in technical guidelines). This appears to be a critical sticking point, never called into question. Neither the availability of further customized information nor the possibility to decide without it [START_REF] Dessai | Climate Prediction: A Limit to Adaptation. Adapting to Climate Change: Thresholds, Values, Governance[END_REF] were explored. Engaging in a direct in-depth discussion with climate scientists was not considered an option as interviewees consider that high-resolution climate projections should be publically produced and made available.

It is not the revision of norms and standards by itself that interviewees judge irrelevant but the process set up to do so at the national level which was not transversal enough. According to several interviewees, climate change will not just affect a few procedures or standards that could be easily listed, but will also have impacts across the whole railway system. Mere listing instances of climate parameters in technical documents is therefore perceived as a sign of poor understanding of the system's complexity. It assumes that it is possible to draw a linear causal link between climate impacts and standardization documents when there are thousands of interactions between the climate system and the infrastructure life cycle that are not always formalized. Moreover, the process described above, was conducted separately from related policy dynamics, such as European discussions on industrial standards and regulation. SNCF is associated with a European cross-sectoral group working on 7 General insights have to be provided publically for free (while more tailored information might be sold as a "climate service"), the public sector playing a role of knowledge-broker through its public policies (giving an official mission to scientists and broadcasting the results through official channels, being an intermediary between information needs and information supply 8 Cf. requests to scientists in the PNACC, deliverable 1, p91 adaptation of industrial standards to climate change. Representatives of the company took part in drafting of specific technical guidelines that propose a step-by-step approach to address climate change in any standards (CEN-CENELEC 2016). SNCF executives perceive this logic of mainstreaming climate change questions into the general process standardization potentially more relevant and efficient. Applying this type of approach might have a significant effect on practice (e.g. Rotter et al. 2015;Rudberg et al. 2012;[START_REF] Ryghaug | The Appropriation of the Climate Change Problem among Road Managers: Fighting in the Trenches of the Real World[END_REF], but this is not the direction followed through the PNACC implementation.

In a nutshell, this ad-hoc, impact-first approach struggles to address the diversity of business operations and its relationships with the climate system. It remains an incomplete process, depoliticized and far from the strategic concerns of the company. In practice, it did not succeed in considering climate change as a potential key element in the decision-making environment. Prescriptive approach to adaptation has left very little room for discussion and was very poorly appropriated throughout the firm. At the end of the day, impacts of climate change are still perceived internally as too ambiguous and not tangible enough compared to other priorities such as urgent renewal needs and security.

ii) Vulnerability-first: context-centered alternatives

Enhancing adaptive capacity by focusing on weather sensitivity. Public policy is not the only source of adaptation concerns within the company. A few people in various positions in the organisation tried to raise this question locally. They did it when providing feedback on their everyday activity, or when writing the specifications of new materials or infrastructure components. They did not refer to the institutionalised adaptation process described in the previous section.

Those "adaptation intrapreneurs 9 " know very well how the system is exposed to the weather and what its main vulnerabilities are. Most of them share a common diagnosis about the French railway network being globally robust to potential climate changes. Some extreme events might produce disruptions difficult to deal with 10 , but there are also large security margins: stabilized renewed railways tracks can for instance withstand temperatures up to 60°C. Recent drainage systems and major engineering works are designed to cope with at least a 1:100year flood event.

In addition, adaptation measures are implemented continuously in a reactive mode. After the 2003 heat wave, which caused major disruptions due to track deformations and severe deterioration of travel conditions, SNCF took important measures: release of a reinforced heat wave contingency plan, establishment of an annual heatday for a check-up of critical equipment, adjustment of temperature class specifications for the new regional rolling-stock, modernization of decision support tools to optimize monitoring and maintenance, etc.

Willing to go beyond reaction, punctual initiatives intend to improve the understanding of the existing interactions between the infrastructure components and climatic conditions. This is perceived as a first necessary step to improve readiness and to anticipate what the consequences of climate change might be. Indeed, there 9 entrepreneur from the inside of a large organization 10 Rail buckling during heatwaves, fires because of droughts, flash-floods in the south of France, landslide because of heavy rain [START_REF] Stamos | Impact Assessment of Extreme Weather Events on Transport Networks: A Data-Driven Approach[END_REF]. Old infrastructure and equipment are particularly vulnerable to this type of events.

is, for now, very little aggregated quantified information about the impact of weather on the French Railway system 11 .

Example 1: An improved understanding of the relationships between the railway infrastructure and weather.

Taking the opportunity of the renewal of weather service contracts, representatives from different SNCF departments launched initiatives to improve the understanding of the relationship between the railway infrastructure and weather. Through cross-analysis of weather data (observations and forecasts) and infrastructure data, those initiatives pursue several objectives such as detecting current vulnerabilities, providing a better picture of the capacity of the system to absorb shocks, designing indicators directly relevant for various management operations, improving decision making tools and updating technical standards and guidelines.

One of them aims at matching the internal incident databases with weather observations. Its primary goal is to improve the understanding of individual disruptions and of the conditions associated with them. A second one is the adoption of a decision support software to trigger and conduct heat-inspections of tracks. A robust statistical relationship was thus established and validated to replace the former empirical approach. This operation aims at reducing the number of non-useful inspections conducted and useful inspections not conducted.

Example 2: A historical approach to crisis management. A research project conducted in the Engineering and projects department of SNCF-Réseau 12 is exploring the benefits of a geomatics (GIS) approach to improve knowledge about flood risks for the railway network (Saint-Marc 2013). It provides descriptions and representations of past flood episodes with detailed chronologies of the events and how they were managed.

The purpose is to strengthen the institutional memory in order to mainstream the culture of risk within the company. At the moment, it is indeed very hard to understand and compare individual weather events because the relevant circumstances are not systematically recorded, especially when the damages are not exceptional [START_REF] Pams-Capoccioni | Impacts Des Inondations Historiques Sur Un Réseau de Transport: Exemple Des Installations et Des Circulations Ferroviaires En France[END_REF]. This project may lead to further developments providing a better description of the evolution of the network vulnerability through decades and questioning how the system reacts to changes.

Continuity between weather resilience and climate change adaptation. These approaches are representative

of what IPCC's reports refer to as a "vulnerability-first" approach (or "bottom-up", or "context-first" approach) (IPCC 2014 Chapter 2) starting with the decision-making context before considering climate change projections.

These discourses are more infrastructure-centred than climate-centred. In these examples, climate change is the exacerbation of existing stresses occurring between infrastructure and the environment. While not necessarily perfectly defined or understood, climate change provides incentives to improve the knowledge about the infrastructure itself. Detailed scientific information or climate change projections are almost never quoted or used. The general objective is to ensure a continuity of service with current and future climate conditions. It is consistent with many sectorial reports exploring how utilities are adapting to climate change (Rotter et al. 2016; 11 Similarly to the UK (NetworkRails 2017), understanding the impact of weather events on the railway comes a long way. There was attempts to perform economic estimations of those impacts, for instance on the cost of maintenance [START_REF] Gaudry | Man, Environment, Space and Time -Economic Interactions in Four Dimensions[END_REF], but this aspect has not been fully addressed yet.

12 This is a national department offering engineering services to business units of the group but also conducting autonomous researches.

EEA 2014; Lindgren, Johnsson, and Carlsson-Kanyama 2009; Ryghaug and Solli 2012). There is no rupture between current ability to deal with weather events and future adaptation; actions to be taken are the result of trade-off between risks and opportunities.

Context-centred initiatives responding to day-to-day concerns at the expense of anticipation and

transversality. These initiatives have a priori a stronger capacity to foster the uptake of climate challenges in infrastructure management. Still, they meet some important obstacles. First, interviewees reported the prevalence of reaction over anticipation. There is a strong ability in the organisation to deal with crisis, but no culture of prevention of events that have not been experienced yet (let alone unpredictable events). Promoters of those context-centred initiatives describe their action as a first step to enable future towards more prevention. Indeed, an enhanced knowledge of the current infrastructure vulnerability may be used as a starting point to stress-test assets and the reliability of procedures13 under different climate change scenarios. However, this development is not considered at this point.

A second major limitation of those approaches is their low transversality. Most of them remain context specific and poorly interconnected. There are very few interactions between various business units, phases of the infrastructure lifecycle or decision-levels where the issue is raised.

In a nutshell, these vulnerability-first approaches remain local processes of knowledge acquisition with no institutional uptake. Proposals for more strategic approaches did not raise enough interest from the top management. For instance, a prospective analysis of the climate-induced evolution of transport demand was proposed but not marked as a priority. There is no scepticism about whether there might be changes in climate, however, IMs have not considered these evolutions as potentially disruptive or as structuring drivers for the activity.

TABLE 1: SYNTHESIS OF IDENTIFIED LIMITATIONS OF CURRENT ADAPTATION APPROACHES

General interaction between management and science

Sharing a vision of climate change across the organisation

Processes and procedures for decision-making under uncertainty

Impact-first approach

Projections of future climate remaining too far from daily concern A top down approach with no direct contact with everyday activities.

No specific resources dedicated or provided for a transversal analysis.

Classical predict-then-act instruments (such as statistics-based standards) relying on a linear, centralized and deterministic framework with no consideration of potential disruptive changes or uncertainties.

Contextcentred approaches

Robustness of current weather sensitivity to potential future changes not questioned.

Scientific information about climate change not mobilized.

Context-based initiatives do not succeed to demonstrate potential consequences across the whole infrastructure organization.

Reaction systematically preferred to prevention, potential breakdown not considered. Knowledge on the infrastructure not complete yet.

Source: author

Discussion of observations and comparison with existing literature on adaptation to climate change: overcoming bottlenecks to build collective ownership and enable proactive adaptation

In the recent years, SNCF took some steps towards an institutional uptake of adaptation to climate change. Both company executives and public authorities recognize climate change as a concern and adaptation as a challenge.

However, as of now, adaptation processes have remained incomplete and do not enable the definition of a framework to generalize the uptake of this question. While the literature states that adaptation is able to disrupt classical ways of doing business [START_REF] Richard | L'adaptation Aux Changements Climatiques Les Réponses de L'action Publique Territoriale[END_REF], it has been very difficult until now to challenge the current infrastructure management framework and go beyond weather resilience.

As described in the first part of this article, many context-based questions related to climate adaptation are raised across the company (table 2). However, there is no consensual vision on how to describe this phenomenon and how it affects the infrastructure and the organisation. As a result, no collective ownership of the issue is built either.

TABLE 2: EXAMPLES OF CONCERNS EXPRESSED BY VARIOUS INTERVIEWEES DURING OUR RESEARCH

Source: author

This table is an attempt to characterize the diversity of adaptation questions raised by the interviewees. It does not depict the number of times either of these questions came up during the interviews. For example, more interviewees mentioned as a new public concern than as a new structuring driver of the future of railway infrastructure. Even though all the interviewees generally perceived climate change an important concern, priorities clearly differ from one department to the other.

A lesson learned from STS (Rittel and Webber 1973;[START_REF] Hulme | Why We Disagree about Climate Change[END_REF]) is that the description of a complex phenomenon like climate change as a critical issue for an organization does not pre-exist. It has to be collectively built out of the relationship between this phenomenon and the sociotechnical system. Our analysis reveals serious bottlenecks that prevent management from achieving this objective. Those are quite similar to obstacles faced in other countries that have started to address them. For instance in the UK, a dedicated program called TRACCA 14 funded through the Rail Safety and Standards Board, recently led to creating an adaptation strategy (NetworkRails 2017) to address the "lack of ownership and governance" of adaptation. These examples as well as recent literature suggest different levers of action to enable a more proactive preparation to climate change and to mainstream adaptation into major relevant decisions.

i.

Lack of a consistent institutional framework: satisfying the necessary conditions for adaptation. Some of the core elements of what would constitute a consistent facilitative framework for action appeared 14 The Tomorrow's Railway and Climate Change Adaption (TRACCA) program led to the formulation of 5 objectives "for a railway that is safe and more resilient to the effects of weather, now and in the future". These objectives are: 1. Infrastructure which is able to withstand the impact of future weather conditions; 2. Rapid recovery from the impacts of adverse and extreme events; 3. Improve performance and safety during adverse and extreme weather conditions; 4. Leverage financial savings through reduced compensation payments and repair costs; and 5. Enhance reputation and trust in the railway's ability to manage weather events."(NetworkRails 2017) to be lacking. The process for a national adaptation policy launched by the government was not able to facilitate them.

Alternatives paths may be explored. Many situations may provide windows of opportunity to start building a common understanding of the climate related issues across the company. It might for instance be a response to a triggering event, an institutional initiative, a planned revision of the standards, or a catalysing R&D program [START_REF] Ryghaug | The Appropriation of the Climate Change Problem among Road Managers: Fighting in the Trenches of the Real World[END_REF][START_REF] Networkrails | Network Rail Weather Resilience and Climate Change Adaptation Strategy 2017-2019 1[END_REF]EEA 2014). In any case, it is important to structure the approach in order to ensure a strong leadership from top management, set up a clear and transparent governance, enhance engagement with external stakeholders and especially the public authorities and identify possible resources to design and implement adaptation actions [START_REF] Ford | A Framework for Examining Adaptation Readiness[END_REF]. This cannot be handled separately from other ongoing processes setting both the scientific agenda (e.g. development of climate services, new research forefronts, etc.) and the structural evolution of a sector such as transportation (e.g. asset management, energy of institutional evolutions).

ii.

Poor engagement with climate science: creating opportunities for a strengthened dialogue. With stable climatic conditions, the interactions between infrastructure management and the climate system remain most of the time invisible. Indeed, the infrastructure was designed to perform properly within a range of conditions large enough to absorb weather deviations. Weather is only an issue in some exceptional circumstances (extreme temperatures during heat waves, extreme precipitation leading to floods), rare enough to be managed ad-hoc as exceptional crises. Climate change disturbs this wellestablished relationship. With more extreme episodes and less historical data on their statistical distribution it becomes harder to keep the infrastructure fitted to different contexts [START_REF] Edwards | Infrastructure and Modernity: Force, Time, and Social Organization in the History of Sociotechnical Systems[END_REF].

This creates new uncertainties that could be better managed with a proper use of climate change This last point shows that the needs and levers described in this article -common vision of adaptation challenges; enabling institutional framework; strategic support; relevant partnerships; adapted tools -are tightly interrelated.

CONCLUSION

This paper, through the case study of SNCF, explores where and how large and complex organization managing a network infrastructure may raise adaptation issues. In the first part, it described two types of approaches: first, impact-centered processes focusing on the mobilization of climate science upstream, which struggle to percolate through the organization; second, localized vulnerability-centered initiatives, which strengthen current management procedures but do not bridge the gap with future climate changes. Most of them focus on resilience to current weather and do not go so far as to question future climate.

The analysis highlighted key bottlenecks at the interface between the production and the use of knowledge on climate change. Building a shared and politically backed vision of this phenomenon and formulating contextrelevant questions appear to be essential steps to set the ground for an enabling framework for adaptation.

Finally, the article presented existing tools and methodologies suggesting an alternative approach to tackling adaptation challenges. These tools have not been tested in the French context yet. How such tools can be integrated in existing decision processes, in which situations it is relevant to mobilize them, what are the conditions of their acceptance and appropriation (for example in terms of credibility, salience and legitimacy [START_REF] Cash | Adaptation of Interconnected Infrastructures to Climate Change: A Socio-Technical Systems Perspective[END_REF]) remain open research questions. Tackling them would lead to a broader question about the nature of climate knowledge for a sector like transportation potentially revealing tensions within the sociotechnical system of the infrastructure interacting with its environment.

  scenarios and a sustained dialogue between climate scientists and engineers that has not yet been set up. Thus, precise knowledge about climate change -with certainties and uncertainties, the complexity of the dynamics and an enhanced variability -are never considered. Yet, these characteristics are precisely what might challenge current practices.To build a shared understanding of what climate change is, what it means for the railway system, and how it can be addressed, an iterative dialogue with scientists might be a beneficial first step. Beyond addressing specific demands for additional information, such a relationship would allow to overcome oversimplified representations of the phenomenon and to explore possible futures[START_REF] Kirchhoff | Actionable Knowledge for Environmental Decision Making: Broadening the Usability of Climate Science[END_REF][START_REF] Cash | Adaptation of Interconnected Infrastructures to Climate Change: A Socio-Technical Systems Perspective[END_REF][START_REF] Vaughan | Climate Services for Society: Origins, Institutional Arrangements, and Design Elements for an Evaluation Framework[END_REF]. Different arrangements can be set up like research partnerships, common research projects, business partnerships, etc. Scientific knowledge can be integrated into management in many forms: participatory vulnerability assessments (following protocols such as the one developed by Engineers Canada (2011), prospective work based on few contrasted possible climate futures, systematic tests to assess the vulnerability of options to worstcase scenarios, etc.iii.Processes and procedures not adapted to an uncertain dynamic phenomenon: experimenting alternative decision-making tools to mainstream adaptation. The existing processes and procedures are those of a big technical organization. Tasks are divided according to a classical, homogeneous and codified industrial model. Past experiences and standard situations play an important role in shaping up these procedures. For instance, every technical document with reference to climate parameters is based on empirical evidence of past climate records (e.g. drain systems designed according on past flood patterns, the installation of continuous welded rails is calibrated for average temperatures). These characteristics reflect rarely challenged engineering culture. They are very different from what is usually described as a relevant approach to deal with climate change, favoring diversity, flexibility, anticipation, non-deterministic planning and continuous learning (IPCC 2014 Chapter 15).Alternative decision-making tools and methodological frameworks might be powerful and performative instruments to foster the evolution of In situations such as large project conception, maintenance budget planning or standard revisions, they can contribute to operationally mainstreaming adaptation into decision-making processes. The generalization of alternative decision-making tools is a matter of corporate strategy and moves forward alongside the revision of procedures and standards.However, a first interesting step might be to experiment this type of tools at different stages of projects analysis, from design phases (to display extended costs and benefits) down to monitoring and evaluation (to provide feedback). Many methodologies, including economic analysis, decision making under deep uncertainty techniques, multicriteria decision making, social network analysis, etc. have been explicitlydeveloped to address climate change challenges (Watkiss and Hunt 2013; Dittrich, Wreford, and Moran 2016) but have not been mobilized yet in the French transport sector. A common property of this family of approaches is to disclose any underlying hypothesis and to make every methodological option explicit and open to discussion. These methods encourage more inclusive and participative decision making processes. They also challenge business as usual thinking. For instance, they question optimal economic efficiency as a unique decision criterion by emphasizing the value of flexibility (adjustability over time)or robustness (effectiveness in a broad spectrum of possible futures) as complementary valuable characteristics and by considering possible surprises. Mobilizing these tools to design an adaptive management strategy, to stress test a new management plan or to choose between options is therefore not always straightforward. They are more than additional decision-support tools-they embody and perform a "new paradigm" in decision-making, which can be hard to switch to. Indeed, any procedure of decision-making or indicator implicitly reflects underlying values and societal choices that can change with time(Callon and Muniesa 2009; Crozet 2004; Doganova 2014; Godard 2004). The experimentation with this type of instruments can therefore only be carried out as an explicit strategy in cooperation with all the relevant stakeholders including public authorities, SNCF engineers and climate scientists.

  Do we know how much weather events cost; can we attribute the evolution of costs to climate change? Are management choices (for instance maintenance or renewal of selected options) robust or flexible enough to handle uncertain future climate change? How to prioritize options by considering this new constraint? What type of information is needed? Climate change as an uncertainty for infrastructure planning and designIs climate change uncertainty comparable to socio-economic uncertainties? How to deal with this deep uncertainty during planning and design phases? Are currently used decision-making tools able to take it into account?Climate change as a structuring driver for the future, among others How to articulate various undergoing transition dynamics (e.g. energy transition, digital transformation, country planning, and evolutions of competitive and institutional landscapes, climate changes)? How to deal with potentially conflicting objectives and time steps?

	Various readings of climate change	Implications for infrastructure management, types of adaptation questions raised
	Climate change as a new public	How to respond to regulatory and policy requirements (e.g. European and national adaptation
	concern	strategies)? How to accompany and anticipate changes in regulatory frameworks?
	Climate change as a source of perturbations for technical systems and daily organization	Which adjustments or modifications can be proposed to existing procedures, practices and standards to keep them fitted for climate conditions?
	Climate change as a source of costs
	& potentially enhanced stresses

Mc Kinsey Global Institute estimates global infrastructures needs between $2.5 (current expenses) and 3.3 trillion per year -40% in developed countries.

Starting with people who previously demonstrated an interest in addressing climate change issues within the organization and were involved in previous work related to this topic. Interviews with weather data users inside business or technical unit most sensitive to weather and climate conditions complemented those discussions.

DGITM (transport and infrastructures department), DGEC (energy and climate department)

This described process is in many ways similar to what has been observed in other European countries(AEE 2014)

The letter of appointment sent by the Ministry of the Environment to Jean Jouzel in July 2010, requested an « in depth synthesis on climate scenarios to consider in order to implement the National climate adaptation plan.

On the basis on modelling work of two climate-science teams from CNRM-Meteo France (Aladin-climat model) and from IPSL (WRF model).

i.e. to evaluate their ability to deal with unusual and suboptimal situation.

ACKNOWLEDGEMENTS

This research was funded by the French National Energy and Environment Agency (ADEME), the Institute for Climate Economics (I4CE) and SNCF. The author is especially grateful to Christian Dubost, Bernard Torrin, Antoine Rothey and Sophie Jalabert (SNCF) for their valuable support to access the relevant people and material for the case study within the company. We thank Jean-Paul Vanderlinden, Tommaso Venturini, Benoit Leguet, Alexia Leseur, Igor Shichlov, Mariana Deheza, Bruno Lafitte and the anonymous reviewers for constructive feedback.


Lotfi Braham

Ayoub Mediouni

Marius Nouri

Saddek Bozga

Bensalem

Improved Learning for Stochastic Timed Models by State-Merging Algorithms

The construction of faithful system models for quantitative analysis, e.g., performance evaluation, is challenging due to the inherent systems' complexity and unknown operating conditions. To overcome such difficulties, we are interested in the automated construction of system models by learning from actual execution traces. We focus on the timing aspects of systems that are assumed to be of stochastic nature. In this context, we study a state-merging procedure for learning stochastic timed models and we propose several enhancements at the level of the learned model structure and the underlying algorithms. The results obtained on different examples show a significant improvement of timing accuracy of the learned models.

Introduction

A necessary condition for a successful system design is to rely on faithful models that reflect the actual system behavior. In spite of the long experience designers have on building system models, their construction remains a challenging task, especially with the increasing complexity of recent systems. For performance models, this is even harder because of the inherent complexity and the induced stochastic behavior that is usually combined with time constraints.

Machine Learning (ML) is an active field of research where new algorithms are constantly developed and improved in order to address new challenges and new classes of problems (see [START_REF] Verwer | Pautomac: a probabilistic automata and hidden markov models learning competition[END_REF] for a recent survey). Such an approach allows to automatically build a model out of system observations, i.e., given a learning sample S, a ML algorithm infers an automaton that, in the limit 1 , represents the language L of the actual system [START_REF] Angluin | Learning regular sets from queries and counterexamples[END_REF]. We believe that ML can be used to automatically build system models capturing performance aspects, especially the timing behavior and the stochastic evolution. Those system models may be very useful for documenting legacy code, and for performing formal analyses in order to enhance the system performance, or to integrate new functionalities [?].

despite the wide development of ML techniques, only few works were interested in learning stochastic timed models [START_REF] Sen | Learning continuous time markov chains from sample executions[END_REF][START_REF] Verwer | Efficient identification of timed automata: theory and practice[END_REF][START_REF] De Matos Pedro | Learning Stochastic Timed Automata from Sample Executions[END_REF][START_REF] Mao | Learning deterministic probabilistic automata from a model checking perspective[END_REF]. In this paper, we study the RTI+ algorithm [START_REF] Verwer | Efficient identification of timed automata: theory and practice[END_REF] and we propose improvements that enhance its accuracy. This algorithm learns a sub-class of Timed Automata [START_REF] Alur | A theory of timed automata[END_REF] augmented with probabilities, called Deterministic Real-Time Automata (DRTA). Given a timed learning sample S (traces of timestamped actions of the system), the algorithm starts by building a tree representation of S, called Augmented Prefix Tree Acceptor (APTA). Then, based on statistical tests, it performs state-merging and splitting operations until no more operations are possible. In this algorithm, clock constraints are captured as time intervals over transitions and are built in a coarse fashion. These time intervals are actually considered to be the largest possible, which makes the learning procedure converge faster. However, this introduces a lot of generalization in the built APTA, by allowing timing behaviors that are not part of the actual system language L. Furthermore, we identified that such behaviors cannot be refined during the learning process. The learned model is thus not accurate from a timing point of view.

In this work, we propose a more accurate learning procedure by investigating better compromises between the time generalization introduced in the APTA and its size (and consequently its learning time). We introduce three new APTA models representing different levels of time generalization; the first model is the exact representation of the learning sample, i.e., with no generalization, while the two others introduce some generalization which is less than the original RTI+. We implemented the new variants of the RTI+ algorithm and validated them on different examples. The obtained results show that the learned models are more accurate than the original implementation, albeit the learning time is generally higher.

Outline In Section 1, we discuss some related works on learning stochastic timed models. Section 2 introduces notations and key definitions used in the rest of the paper. We recall the RTI+ learning algorithm and study underlying time representation issues in Section 3. In Section 4, we present the three improvements we propose for RTI+ and discuss them. Section 5 presents experiments and results of the improved algorithms. Conclusions are drawn in Section 6.

Related Works

In the literature, several algorithms have been proposed for automata learning [START_REF] Angluin | Learning regular sets from queries and counterexamples[END_REF][START_REF] Carrasco | Learning stochastic regular grammars by means of a state merging method[END_REF][START_REF] Verwer | Efficient identification of timed automata: theory and practice[END_REF][START_REF] Maier | Anomaly detection in production plants using timed automata[END_REF], mostly in the deterministic case. In the last decades, an increasing interest has been shown for learning probabilistic models, partly due to the success of verification techniques such as probabilistic and statistical model checking [START_REF] Kwiatkowska | Symbolic model checking for probabilistic timed automata[END_REF][START_REF] Legay | Statistical Model Checking: An Overview[END_REF]. Despite this development, only few works considered the problem of learning stochastic timed models [START_REF] Sen | Learning continuous time markov chains from sample executions[END_REF][START_REF] Verwer | Efficient identification of timed automata: theory and practice[END_REF][START_REF] De Matos Pedro | Learning Stochastic Timed Automata from Sample Executions[END_REF][START_REF] Mao | Learning deterministic probabilistic automata from a model checking perspective[END_REF].

Most of the algorithms proposed in this setting are based on the state-merging procedure made popular by the Alergia algorithm [START_REF] Carrasco | Learning stochastic regular grammars by means of a state merging method[END_REF]. Moreover, many of them consider Continuous Time Markov Chains (CTMCs) as the underlying model. For instance, in [START_REF] Sen | Learning continuous time markov chains from sample executions[END_REF], an algorithm is proposed for model-checking black-box systems. More recently, the AAlergia algorithm [START_REF] Mao | Learning probabilistic automata for model checking[END_REF], initially proposed for learning Discrete Time Markov Chains and Markov Decision Processes, was extended to learn CTMCs [START_REF] Mao | Learning deterministic probabilistic automata from a model checking perspective[END_REF]. This work is an extension of Alergia to learn models having timed in/out actions.

Other algorithms such as RTI+ [START_REF] Verwer | Efficient identification of timed automata: theory and practice[END_REF] and BUTLA [START_REF] Maier | Anomaly detection in production plants using timed automata[END_REF] focus on learning Timed Automata augmented with probability distributions on discrete transitions and uniform probabilities over timing constraints. Both follow a state-merging procedure but consider different statistical tests for checking states compatibility.

In [START_REF] De Matos Pedro | Learning Stochastic Timed Automata from Sample Executions[END_REF], authors focus on learning more general stochastic timed models, namely Generalized Semi-Markov Processes following the same state-merging procedure. This algorithm relies on new statistical clocks estimators, in addition to the state compatibility criterion used in Alergia.

Background

Let Σ be a finite alphabet, Σ * the set of words over Σ and the empty word. Let T be a time domain and T * the set of time sequences over T. In our work, we consider integer time values, i.e., T ⊆ N. For a set of clocks C, let CC(C) denote the set of clock constraints over C. Let I be the intervals domain, where I ∈ I is an interval of the form [a; b], a, b ∈ T such that a ≤ b, and represents the set of integer values between a and b. Let ω be an untimed word over Σ and τ a time sequence over T. We write ω ≤ ω (resp. τ ≤ τ ) whenever ω (resp. τ ) is a prefix of ω (resp. τ ). We also write ωu (resp. τ v) for the concatenation of ω (resp. τ ) and u ∈ Σ * (resp. v ∈ T * ). |ω| (resp. |τ |) is the size of ω (resp. τ ).

Deterministic Real-Time Automata (DRTA)

A Real-Time Automaton (RTA) is a timed automaton with a single clock which is systematically reset on every transition. Definition 1 (Real-Time Automaton (RTA)). An RTA is a tuple A = Σ, L, l 0 , C, T, inv where: (1) Σ is the alphabet, (2) L is a finite set of locations, (3) l 0 ∈ L is the initial location, (4) C = {c} contains a single clock, (5) T ⊆ L × Σ × CC(C) × C × L is a set of edges with a systematic reset of the clock c, (6) inv : L -→ CC(C) associates invariants to locations.

For more convenience, transitions are denoted as l σ,I --→ l , where σ ∈ Σ and I ∈ I is a time interval including both transition guards and location invariants. For simplicity, we also ommit the systematic reset.

An RTA is deterministic (DRTA) if, for each location l and a symbol σ, the timing constraints of any two transitions starting from l and labeled with σ are disjoint, i.e., ∀l ∈ L, ∀σ ∈ Σ, ∀t 1 , t 2 ∈ T, t 1 = l, σ, I 1 , l 1 and t 2 = l, σ, I 2 , l 2 , (I 1 ∩I 2 = ∅) ⇔ (t 1 = t 2 ). A DRTA generates timed words over Σ ×T.

Each timed word is a sequence of timed symbols (ω, τ )=(σ 1 , τ 1 )(σ 2 , τ 2 )...(σ m , τ m ), representing an untimed word ω together with a time sequence τ . A set of n timed words constitute a learning sample

S = {(ω, τ ) i , i ∈ [1; n], ω ∈ Σ * , τ ∈ T * }.
We denote by T S the set of time values appearing in S.

A Prefix Tree Acceptor (PTA) is a tree representation of the learning sample S where locations represent prefixes of untimed words in S. Timing information is captured in a PTA in form of intervals I ∈ I over transitions. This structure is called Augmented PTA (APTA). In the latter, each transition l σ,I --→ l is annotated with a frequency that represents the number of words in S having l as a prefix. An APTA can be seen as an acyclic DRTA annotated with frequencies. Let N : T -→ N be this annotation function. Given a DRTA A, a pair (A, N ) is an annotated DRTA, denoted DRT A + .

Stochastic Interpretation of a DRTA

A DRTA starts at the initial location l 0 with probability 1. It moves from a location to another using transitions in T . At each location l, a transition is chosen among the set of available transitions T l . Selecting a transition consists of choosing a timed symbol (σ i , τ i ). A probabilistic strategy ϕ that associates a probability function to each location l over the set of transitions T l is used to make this choice: ϕ : L × T -→ [0, 1], such that Σ t∈T l ϕ(l, t) = 1, ∀l ∈ L. For the chosen transition l σ,I --→ l , the choice of the time value is done uniformly over the time interval I. Figure 1 shows an example where two transitions labeled A and B are possible from location 1. The strategy ϕ associates probability 0.6 to A and 0.4 to B. Then, uniform choices on the associated time intervals are performed.

Transition Distribution Uniform Choice 1 2 3 A [0;1] B [0;1] 1 2 3 A [0;1] (0.6) B [0;1] (0.4) 1 3 B [0;0] (0.2) A [1;1] (0.3) 2 A [0;0] (0.3) B [1;1] (0.2)
Fig. 1: Probabilistic strategy with uniform choice 3 The RTI+ Learning Procedure RTI+ [START_REF] Verwer | Efficient identification of timed automata: theory and practice[END_REF] is a state-merging algorithm for learning DRTA models from a sample of timed words. The algorithm first builds a PTA then reduces it by merging locations having similar behaviors, according to a given compatibility criterion. Compared to other state-merging algorithms, RTI+ relies on a time-split operation to identify the different timed behaviors and to split them into disjoint ones. The algorithm is able to learn a stochastic DRTA, i.e, a DRT A + where the strategy is obtained from the associated annotation function N .

Building the APTA

The timed learning sample is represented as an APTA where all the time intervals span over T. Initially, the built APTA only contains a root node consisting of the empty word . RTI+ proceeds by adding a location in the tree for each prefix of untimed words in S. Then, a transition labeled with σ is created from location l to location l if the prefix of l is obtained by concatenating the prefix of l and symbol σ. Finally, transitions are augmented with the largest time constraint [0; max(T S )], where max(T S ) = M ax{a ∈ T S }. The annotation function N is built at the same time and represents transitions frequencies. In this work, we denote this construction as generalized-bound APTA.

Definition 2 (Generalized-bound APTA). A generalized-bound AP T A is a DRT A + ( Σ, L, l 0 , C, T, inv , N ) where: -L = {ω ∈ Σ * | ∃(ω , τ ) ∈ S, ω ≤ ω }, l 0 = , -T contains transitions of the form t = ω, σ, [0; max(T S )], ω s.t. ωσ = ω ,
and

N (t) = |{(ω u, τ ) ∈ S, u ∈ Σ * }|.

The Learning Process

The learning process aims to identify the DRT A + that represents the target language while reducing the size of the initial APTA. At each iteration, the algorithm first tries to identify the timing behavior of the system, by using timesplit operations. The second step consists of merging compatible locations that show similar stochastic and timed behaviors. Locations that are not involved in merge or split operations are marked as belonging to the final model (promote operation). The algorithm proceeds by initially marking the root of the APTA as part of the final model and its successors as candidate locations. The latter will be considered for time-split, merge or promote operations. Merge Operation. Given a marked location l (belongs to the final model) and a candidate location l , this operation is performed by first redirecting the transitions targetting l , to l and then by folding the subtree of l on l. 2

Compatibility Evaluation

The compatibility criterion used in RTI+ is the Likelihood Ratio (LR) test. Intuitively, this criterion measures a distance between two hypotheses with respect to specific observations. In our case, the considered hypotheses are two DRT A + models: H with m transitions and H with m transitions (m < m ), where H is the model after a merge operation (resp. before a split) and H is the model before a merge (resp. after a split). The observations are the traces of S.

We define the likelihood function that estimates how S is likely to be generated by each model (H or H ). It represents the product of the probability to generate each timed word in S 3 . Note that the i th timed word (ω, τ ) i in S corresponds to a unique path p i in the DRT A + . The probability to generate (ω, τ ) i is the product of the probabilities of each transition in

p i = s 1 s 2 ...s |ω| : f ((ω, τ ) i , H) = |ω|-1 j=1 π((ω j , τ j ) i , s j )
Where π((ω j , τ j ) i , s j ) corresponds to the probability to transit from the location s j to s j+1 in H with the j th timed symbol (ω j , τ j ) i . Given a learning sample S of size n, the likelihood function of

H is Likelihood(S, H) = n i=1 f ((ω, τ ) i , H).
The likelihook ratio is then computed as follows

LR = Likelihood(S, H) Likelihood(S, H )
Let Y be a random variable following a χ 2 distribution with m -m degrees of freedom, i.e., Y χ 2 (m -m). Then, y = -2ln(LR) is asymptotically χ 2 distributed. In order to evaluate the probability to obtain y or more extreme values, we compute the p-value pv = P (Y ≥ y). If pv < 0.05, then we conclude that H and H are significantly different, with 95% confidence.

The compatibility criterion concludes that a time-split operation is accepted whenever it identifies a new timing behavior, that is, the model after split is significantly different from the model before split (pv < 0.05). In constrast, a merge is rejected whenever the model after merge is significantly different from the model before merge since the merged locations are supposed to have similar stochastic and timed behaviors.

Shortcomings

The RTI+ algorithm relies on the generalized-bound APTA as initial representation of the learning sample S. As pointed out before, this kind of APTA augments an untimed PTA with the largest possible time intervals, without considering the values that concretely appear in S. This introduces an initial generalization that leads the APTA to accept words that do not actually belong to S and might not belong to the target language L. In Example 1, we show that this initial generalization cannot be refined later in the learning process. More concretely, we observe that the time intervals that do not appear in S are not isolated and removed from the DRT A + .

) = The generalized-bound APTA introduces empty time intervals that cannot be removed during the learning process. To overcome this issue, we propose, in the next section, new representations of the learning sample S.

Learning More Accurate Models

A faithful representation of the learning sample consists of building an APTA that accepts only words in S by taking into account the time values. This can be done at different granularities, which results on different tradeoffs between the introduced initial generalization and the APTA size. We propose three different APTA models denoted unfolded, constructive-bound and tightened-bound APTAs.

Unfolded APTA

This APTA model fits perfectly the traces in S, that is, accepts exactly the timed words in S. Hence, it does not introduce any initial generalization. To build such a model, we need to consider both symbols and time values. The APTA initially contains the empty word. Locations are added for every timed prefix and corresponding transitions are created such that each transition only accepts a single time value, i.e., time intervals are equalities of the form [a; a] ∈ I.

Definition 3 (Unfolded APTA). An unfolded AP T A is a DRT A + where:

-L = {(ω, τ ) ∈ Σ * × T * | ∃(ω , τ ) ∈ S, ω ≤ ω , τ ≤ τ },
-T contains transitions of the form t = (ω, τ ), σ, [a; a], (ω , τ ) such that: [START_REF] Alur | A theory of timed automata[END_REF] ωσ = ω , (2) τ a = τ , and

N (t) = |{(ω u, τ v) ∈ S, u ∈ Σ * , v ∈ T * }|.

Constructive-bound APTA

A more compact representation of S compared to the unfolded APTA can be obtained by reducing the size of the initial APTA. At each location, a reduction of the number of transitions is performed by grouping all the contiguous time values for the same symbol into a single transition where the time interval I is the union of the different time intervals.

Definition 4 (Constructive-bound APTA).

A constructive-bound AP T A is a DRT A + where:

-L = {(ω, {I i } |ω| i=1 ), ω ∈ Σ * , I i ∈ I | ∀i ∈ [1; |ω|], ∀c ∈ I i , ∃(ω , τ ) ∈ S, ∀j < i, τ j ∈ I j , c = τ i , ω ≤ ω } ∪ {l 0 = ( , ∅)},
N (t) = |{(ω u, τ v) ∈ S, ∀i ∈ [1; |ω |], τ i ∈ I i , u ∈ Σ * , v ∈ T * }|.
In Definition 4, each location corresponds to a subset of timed words that have a common untimed prefix where each symbol (of the prefix) apprears with contiguous time values. A location is labeled by the given untimed prefix ω and the sequence of intervals {I i } |ω| i=1 corresponding to each symbol of ω. I i is the interval grouping the contiguous time values for the symbol σ i of ω. All time values of these intervals are present in at least one timed word in S. A transition is added between locations l and l such that: (1) the concatenation of the untimed prefix relative to l and symbol σ produces the untimed prefix relative to l , and (2) adding I to the interval sequence of l gives the interval sequence of l .

Tightened-bound APTA

The minimal size of APTA is obtained by allowing the minimal number of transitions from each location. This minimal number is obtained by assigning at most one transition for each symbol of Σ. The initial generalization is reduced (compared to the generalized-bound APTA) by identifying the minimum (resp. the maximum ) time value t min (resp. t max ) among all the time values for each location l and symbol σ. Then, a single transition is created from l with symbol σ and a time interval [t min ; t max ]. We call this APTA model a tightened-bound APTA. It has the same structure as the generalized-bound APTA but with tighter bounds. The time interval [t min ; t max ] of each transition is computed locally depending on the corresponding timed words in S.

Definition 5 (Tightened-bound APTA). A tightened-bound AP T A is a

DRT A + where:

-L = {ω ∈ Σ * | ∃(ω , τ ) ∈ S, ω ≤ ω }, l 0 = , -T contains transitions of the form t = ω, σ, [t min ; t max ], ω such that: (1) ωσ = ω , (2) t min = M in{τ |ω | | (ω u, τ ) ∈ S}, (3) t max = M ax{τ |ω | | (ω u, τ ) ∈ S}, and
N (t) = |{(ω u, τ ) ∈ S}|, where u ∈ Σ * .

Evaluation

In this section, we discuss the proposed APTA models with respect to their ability to faithfully represent S and to their size. We consider the following sample S = {(A,5)(B,5); (A,4)(A,3); (A,3)(B,5); (B,3)(A,5); (B,3)(B,5); (B,1)(A,1)}. Figure 3 depicts the three types of APTAs representing S. Initial Generalization. The unfolded APTA does not introduce any initial generalization (Figure 3a). The constructive-bound APTA is a more compact representation of S compared to the unfolded APTA with less generalization than the generalized-bound APTA. Some generalization is introduced due to the possible combination of grouped time values. In other words, the time values of the time intervals appear in S, but the language generated by the APTA overapproximates S since it accepts more time sequences. For instance, in Figure 3b, the timed word (A,3)(A,3) is accepted although not in S. This is due to the combination of time values coming from the timed words (A,4)(A,3) and (A,3)(B,5). The tightened-bound APTA introduces two kinds of generalization. The first is due to the combination of grouped time values, as for the constructive-bound APTA. The second one is caused by the presence of empty intervals. An example is given in Figure 3c where transitting from the root is possible using the timed symbol (B,2) which is not S. This latter generalization is similar to the one we pointed out for the generalized-bound APTA albeit with more restrictive time intervals, since the empty intervals [0; t min -1] and [t max + 1; max(T S )] are initially removed. The relationship between these models and the generalization they introduce is summarized in Figure 4.

APTA Size. In terms of the size of initial representation, the unfolded APTA is the largest. The APTA size depends on the size of Σ and T S . The worst case is encountered when all the traces in S are of the same length N and when S contains all the combinations of symbols and time values. The resulting complete tree, in this case, represents the upper bound on the exponential number of locations and can be expressed as

M axSize (unf olded) = 1 -(|Σ| × |T S |) N +1 1 -(|Σ| × |T S |)
This maximum number of locations is reduced in the constructive-bound APTA by grouping contiguous time values. However, this improvement is meaningless in the case where all the time values are disjoint. For a given interval [0; max(T S )], the maximum number of disjoint intervals is encountered when all the time values are disjoint and is equal to (max(T S ) + 1) div 2. The worst case number of locations of a complete tree of depth N + 1 is

M axSize (constructive) = 1 -(|Σ| × ((max(T S ) + 1) div 2)) N +1 1 -(|Σ| × ((max(T S ) + 1) div 2))
The number of locations, in this case, is highly dependent on the size of Σ and less on the size of T S . This latter can be removed by allowing only one interval for each symbol at each location. This is the case of the generalized-bound APTA and the tightened-bound APTA which return the minimum number of locations.

Experiments

In this section, we evaluate the learned model according to its ability to accept the words belonging to L and to reject the others. This gives insight into how accurate the learned model is. A C++ implementation of the proposed algorithms and the considered examples can be found in http://www-verimag.imag.fr/ ~nouri/drta-learning. The same page also contains additional materials such as algorithms and formal definitions of the elementary operations, in addition to a discussion about the proposed models accuracy.

Evaluation Procedure

The accuracy of the learned model can be quantified using two metrics: the precision and the recall. The precision is calculated as the proportion of words that are correctly recognized (true positives) in the learned model H over all the words recognized by H , while the recall represents the proportion of words that are correctly recognized in H over all the words recognized by the initial model H. The precision and the recall can be combined in a single metric called F1 score. A high F1 score corresponds to a high precision and recall, and conversely.

P recision(H , H)

= |{(ω, τ ) ∈ Σ * × T * | (ω, τ ) ∈ L(H) ∧ (ω, τ ) ∈ L(H )}| |L(H )| Recall(H , H) = |{(ω, τ ) ∈ Σ * × T * | (ω, τ ) ∈ L(H) ∧ (ω, τ ) ∈ L(H )}| |L(H)| F 1 score(H , H) = 2 × prec(H , H) × recall(H , H) prec(H , H) + recall(H , H)
Based on these metrics, we distinguish four degrees of generalization for the learned models (see Figure 5):

1. The maximum F1 score is obtained when the exact target language L(H) is learned. 2. A precision of 1 and a recall strictly lower than 1 characterize an underapproximation, i.e., the learned model H recognizes only a subset of words of L(H). 3. A recall of 1 and a precision strictly lower than 1 characterize an overapproximation, i.e., the learned model H accepts all the words of L(H) in addition to extra words not in L(H). 4. A precision and a recall strictly lower than 1 characterize a cross-approximation, i.e., L(H ) contains only a subset of words in L(H) plus additional words not in L(H). Periodic A is a synthetic periodic task A that executes for 1 to 3 time units in a period of 5 time units. The goal of this benchmark is to check if the algorithm is able to learn the periodicity and the duration of a single task. Two less constrained variants of this model are also considered. In both of them, we remove the periodicity of the task by setting a predefined waiting time of 5 time units after the task A finishes. In the first variant, called aperiodic contiguous-time (ap cont A), the execution time of the task A can take contiguous time values in [1; 3]. In the second one, called aperiodic disjoint (ap dis A), the execution time takes the disjoint time values 0, 2 and 4. Our goal is to check if the algorithm is able to detect the unused time values 1 and 3.

Periodic A -B consists of two sequential tasks A and B, taking execution time values, respectively, in intervals [1;3] and [1;2] with a periodicity of 5 time units.

In this example, the learning algorithm is faced with dependencies between clock constraints for the task A, the task B and their periodicities, which is a more complex setting. CSMA/CD communication medium model for a 2-station network CSM A/CD communication medium model is a media access control protocol for single-channel networks that solves data collision problems. We focus on the CSMA/CD communication medium model for a 2-station network presented in [START_REF] Kwiatkowska | Symbolic model checking for probabilistic timed automata[END_REF]. Figure 7 represents the underlying CSMA/CD communication medium model where λ represents the propagation time. We assume that t max is the maximum time elapsing between two consecutive events.

F ree start Busy1 Busy2 CD Send1 [0; tmax] Send2 [0; tmax] Collide [0; λ -1] End1 [λ; tmax] Collide [0; λ -1] End2 [λ; tmax] N otif y [0; 0]

Results

Experiments have been done on the described examples using a learning sample of size 200 and a test sample of size 1000.

The Synthetic Examples. Table 1 summerizes the results for periodic A (and variants) and periodic A-B. Since all the learned models have a 100% recall, only the precision is discussed in the sequel. The obtained results show that the original RTI+ learns an overfitting model with a poor precision for all the considered examples. In contrast, as shown by the F1 score, the exact model is learned using the unfolded APTA for periodic A and its variants. Both the constructive and the tightened-bound APTAs do not learn the exact periodic A model (although more accurate than RTI+). They actually fail to identify the periodicity of task A. For ap cont A, the constructive and the tightened-bound APTAs learn the exact model. However, for ap dis A, the constructive-bound approach learns the exact model, while the tightened-bound one returns a model with a low precision since it does not detect the unused time values 1 and 3.

For the periodic A-B example, none of the variants was able to learn an accurate model: the obtained precision is at most 2.27% (using the constructive-bound APTA). They all fail to capture dependencies over clock constraints. Nevertheless, precision is still better than the original RTI+ (0.18%). Figure 8 shows the impact of bigger time periods in the periodic A example on the quality of the learned model (Figure 8a) and the learning time (Figure 8b). We observe that increasing the period makes it more difficult to learn accurate models; Increasing the period decreases the precision as shown in Figure 8a and increases the learning time as shown in Figure 8b. For instance, the original RTI+ with generalized-bound APTA is quite fast but its precision tends to zero. Using constructive and tightened-bound APTAs improves the precision with a similar learning time. Finally, relying on the unfolded APTA produces very precise models but induces an important learning time when the period exceeds 15 time units.

The CSMA/CD Example. Table 2 summerizes the experiments done on CSMA/CD. On the one hand, one can notice that RTI+, like in the previous cases, learns an overfitting model with a poor precision (6.20%) but in a short time (∼ 6 s). Moreover, the generalized-bound APTA, initially having 2373 locations, is reduced to a final model with only 4 locations which represents a high reduction. On the other hand, the proposed APTAs produce significantly different models that cross-approximate the original CSMA/CD. For instance, the tightened-bound APTA learns a very precise model (93.70%). However, the model is obtained in more than 8 hours and has 370 locations. Using the constructive-bound APTA gives a model with less precision (85.80%) in a lower execution time (∼ 3 h). Finally, the unfolded APTA gives a model with a 49.40% precision and a 96.70% recall, which corresponds to the best F1 score (0.6539). Furthermore, compared to constructive and tightened-bound APTAs, Fig. 8: Impact of varying the task A period on the precision/the learning time the learning time for the unfolded APTA is lower (∼ 9 min). Hence, we conclude that, for this example, the unfolded APTA provides a good tradeoff between accuracy and learning time.

Conclusion

In this work, we proposed different variants of the RTI+ algorithm for learning models with both stochastic and timed behaviors. We formally defined three APTA models with different levels of generalization and representation sizes. We validated our proposal by performing different experiments which showed that using the new APTA variants provides more accurate models regarding the time behaviors. However, we observed that a higher learning time is generally required, depending on the desired accuracy. In the future, we are planning to improve our algorithms to better handle models with dependencies over clock constraints such as in the periodic A-B example. We are investigating a new compatibility criterion that takes into account such dependencies and which is able to isolate empty time intervals.

Example 1 .

 1 Let us consider the following learning sample S = {(A,5)(B,5); (A,4)(A,3); (A,3)(B,5); (B,1)(A,5); (B,3)(B,5); (B,5)(A,1)}. The left-hand model in Figure 2 presents the initial DRT A + (H) of S on which we evaluate a timesplit operation. The latter is expected to identify the empty interval [0; 2] on transition t = 1, A, [0; 5], 2 , since no timed word in S takes this transition with time values in [0; 2]. The right-hand figure represents the model assuming a split of transition t at time value 2 (H ). The LR test returns pv = 1 which leads to reject the time-split operation, and hence, the empty interval [0; 2] is not identified during the learning process.

Fig. 2 :

 2 Fig. 2: Identifying empty intervals with time-split operation

-

  T contains transitions of the form t = (ω, {I i } |ω| i=1 ), σ, I, (ω , {I i } |ω | i=1 ) such that: (1) ωσ = ω , (2) ∀i ∈ [1; |ω|], I i = I i and I |ω | = I |ω|+1 = I, and

Fig. 3 :

 3 Fig. 3: The three APTA models for the sample S

Fig. 4 :

 4 Fig. 4: Generalization introduced by the different AP T As

Fig. 5 :Fig. 6 :

 56 Fig.5: Degrees of generalization of the learned language L(H ) with respect to the target language L(H)

Fig. 7 :

 7 Fig. 7: CSMA/CD communication medium model for a 2-station network

Table 1 :

 1 Accuracy results for the synthetic benchmarks with the four APTAs

	Benchmark	Periodic A Ap dis A Ap cont A Periodic AB
	Generalized Precision	11%	0.8%	0.6%	0.18%
	-bound	Recall	100%	100%	100%	100%
		F1 score	0.1982	0.0159	0.0119	0.0036
	Unfolded Precision	100%	100%	100%	1.97%
		Recall	100%	100%	100%	100%
		F1 score	1.0000	1.0000	1.0000	0.0386
	Constructive Precision	16.4%	100%	100%	2.27%
	-bound	Recall	100%	100%	100%	100%
		F1 score	0.2818	1.0000	1.0000	0.0444
	Tightened Precision	16.9%	3.01%	100%	2.18%
	-bound	Recall	100%	100%	100%	100%
		F1 score	0.2891	0.0584	1.0000	0.0427

Table 2 :

 2 Experimental results for CSMA/CD using the four APTA models

	APTA type Precision Recall F1 score Time	APTA size DRTA size Reduction
	Generalized 6.20%	100.00% 0.1168 ∼ 6 sec 2373	4	99.83%
	Unfolded	49.40% 96.70% 0.6539 ∼ 9 min 3586	19	99.47%
	Constructive 85.80% 52.00% 0.6475 ∼ 3 hrs 2652	207	92.19%
	Tightened	93.70% 49.90% 0.6512 ∼ 8 hrs 2373	370	84.41%

By considering a sufficient number of observations[START_REF] De La Higuera | Grammatical inference: learning automata and grammars[END_REF].

For further details, see: http://www-verimag.imag.fr/ ~nouri/drta-learning/ Appendice.pdf