Olimpia Hoinaru
email: olimpia.hoinaru@ifsttar.fr

Christophe Gransart

Georges Mariano

Étienne Lemaire

An ontology for the ERTMS/ETCS

Keywords: Knowledge Engineering, Requirements Engineering, Ontologies, Natural Language Processing (NLP), European Rail Traffic Management System (ERTMS), European Train Control System (ETCS), Railway Systems

In the present paper we aim to describe the research and practical work of creating an ontology of the new European system of control and signalling ERTMS/ETCS. The object of our study is the System Requirements Specification set of documents, that is the corpus of our ontology. This one was processed using an NLP tool i.e. Protégé, in order to obtain a more explicit and easily usable form of these specifications. This processing was performed through a research and practice of system modelling and knowledge formalisation by using the OWL and SWRL languages. To be noted that this work is still in process, and that the part presented here constitutes the first steps in the creation of this ontology.

Résumé

Le présent article a pour but de décrire les travaux de recherche et développement d'une ontologie du système européen de contrôle-commande et signalisation ERTMS/ETCS. L'objet de notre étude est l'ensemble des documents appelés « System Requirements Specifications » spécifiant le cahier des charges du système évoqué. Ces documents ont été traités à l'aide d'un outil de TALN (Traitement Automatique du Langage Naturel) à savoir Protégé, un outil de création d'ontologies. Ce traitement est fait par une recherche et application des domaines de la modélisation de systèmes et de la formalisation des connaissances, en utilisant les langages OWL et SWRL. À noter que ces travaux sont encore en cours de réalisation. La partie présentée dans cette contribution constitue une première étape de ce processus.

Mots-clé: Ingénierie des Connaissances; Ingénierie des Exigences; Ontologies; Traitement Automatique du Langage Naturel (TAL); European Rail Traffic Management System (ERTMS); European Train Control System (ETCS); Système ferroviaire.

Introduction and context

The research and practical work that we performed for this article consisted in the processing of the available documents describing the System Requirements Specifications of the European Rail Traffic Management System (ERTMS). This contribution will tackle the process of creation of this ontology, as well as some information introducing ontologies in the knowledge engineering and requirements engineering. Train control is an important part of any railway operations management system. In the past, a number of different Automatic Train Control (ATC) systems have evolved in different countries at different times. These systems are incompatible and not interoperable. Only a few of these systems are used in more than one country, and even in those cases there have been differences in detailed development which have resulted in incompatible and not interoperable versions. Many railways anticipate a significant increase in density of train traffic and are rethinking their infrastructure strategy in order to accommodate high levels of traffic, in which ATC systems play an important part. Also many railways would like to introduce standardised systems to reduce system costs. The SRS set of documents specifies the European Rail Traffic Management System/European Train Control System (ERTMS/ETCS). Its aim is to establish international standardisation of ATC systems. The modelling and formalisation of such a complex structure is still the aim of our research. The work presented in this paper only describes the first steps of this process. Compared to other types of approaches of processing the specification documents of the ERTMS/ETCS system, who favour formal methods (e.g. Petri nets, B method, etc), we preferred to create an ontology. In Figure 1 the general evolution of the technologies used for this matter is highlighted. By doing this, we follow the paradigm stated in [START_REF] Bjørner | Rôle of Domain Engineering in Software Development-Why Current Requirements Engineering Is Flawed![END_REF]: "Before software can be designed we must understand the requirements. Before requirements can be finalised we must have understood the domain". But where Dines Bjørner uses pure formal logic to tackle generic sample problems, we will experiment the use of ontological technologies (conceptualisation, formalisation, reasoning) to tackle a real and complex system.

General goals

The work presented in this article is situated at the intersection of several domains i.e. knowledge management and Web semantics, knowledge representation and formalisation, as well as system modelling. The knowledge of the ERTMS domain is considered and formalised for understanding and reusing issues. Several methods (models) can be used to capture the different aspects of a railway complex system. Based on the fact that the same concept can have different meanings in different domains, the need for specification of these semantic differences was felt. The ERTMS ontology models and formalises the System Requirements Specification documents of the ERTMS that are written in natural language. The aim of this ontology is the formalisation of these specifications in order to obtain a data structure that can be reusable in the framework of other research in the ERTMS field. A module of this ontology is the OSI (Open Systems Interconnection) [START_REF] Tanenbaum | Efficient data integration in the railway domain through an ontology-based methodology[END_REF] model and another one concerns the application of the OSI model to the ERTMS/ETCS subsystem dealing with data transmission by means of radiocommunication. We aim that, when in its final version, the ERTMS ontology represent a structured and comprehensible form of the ERTMS SRS. It should be able to provide help to human agents in a comprehension and reuse process as well as to programs. System modelling tools could take the owl or xml file obtained as a lexical ressource and use it for information extraction or system modelling purposes.

Elaborating ontologies

In this section, an account of the definition and usage of ontologies will be provided.

Defining ontologies

Ontologies are formal representations of knowledge of a certain domain. Several definitions of the term "ontology" have been provided. Gruber poses that "an ontology is an explicit specification of a conceptualization". According to the same author, "the term is borrowed from philosophy, where an ontology is a systematic account of Existence" (Gruber, 1993a). There are four types of information allowing us to be clear about what we represent in an ontology. These are the types of ontology (domain ontologies, generic ontology, ontology of a method of solving a problem, application ontology and representation ontology), the properties, the "is-a" relation and the other relations [4]. The knowledge of a domain is formalised using several notations with the aim of regrouping and creating a formal structure of the concepts of this domain into a web of knowledge. We chose an ontology creation tool using the Web Ontology Language (OWL), i.e. the Protégé tool. Protégé-2000 was developed by Mark Musen's group at Stanford Medical Informatics. In this environment, concepts are formalised as classes together with several types of properties and the relations among them. The so-called "rules" are created for the purpose of modelling requirements and certain "behaviours" of the system. In the railway domain, documents describing the System Requirements Specifications were issued with the specific aim of explaining and clarifying the usage of a part of the terms/concepts used in this domain, and of the system itself. Furthermore, we will present some of the ontology development methodologies existing and explain more thoroughly the methodology that we used in the framework of our project.

Methontology

"Methontology" is the term used to describe one of these methodologies for creating an ontology. It is among the more comprehensive ontology engineering methodologies as its aim is to build ontologies either from scratch, reusing other ontologies as they are, or by a process of re-engineering them. But methontology is not the only methodology for creating ontologies. Other methodologies, such as the corpus-based methodology exist. [4] explains this methodology in a very pedagogical way. In this paragraph, we will briefly present this methodology and in a later section, we will explain how we applied it in the case of our ontology.

The corpus-based methodology

The corpus-based methodology helps to acquire ontologies starting from corpora. This method was developed by B. Bachimont [START_REF] Charlet | Ontologies pour le Web sémantique[END_REF]. The four steps of this method are:

• Corpus analysis. This first step implies finding texts written in natural language that explain the knowledge of the stated domain, for purposes of practice, specification or knowledge transfer. The collation of these texts is called corpus collection and preparation. The preparation of the corpus consists in thorough analysis of the textual resources that will be the source of allowing us to characterise the useful concepts for modelling an ontology and the corresponding semantic content. This corpus approach implies terminology extraction tools, natural language processing tools but also language processing carried out manually for a better disambiguation. • Semantic normalisation. This second step uses the candidate terms defined at the first stage, terms that have a meaning for the reader. But nothing makes sure that this sense is unique. On the contrary, we are in the case of a linguistic behaviour where meanings are ambiguous, definitions not always clear or well-formed, and they depend particularly on the context of the user's interpretation. However, in the ontological modelling, we seek to build primitives whose meaning does not depend on other primitives and especially non-contextual ones. That is why, in order to obtain formal results, we need to normalise the meanings of the terms i.e. only retain one meaning for each term, one interpretation for human understanding. The corollary of the methodology, the meaning of a concept, is generally defined according to what it is (heritage relation to the father concept) and to what it is not (differences with the father or the sibling concepts). At the end of this step, we can assert that we have a "regional ontology". • Ontologic engagement. This third step uses the regional ontology obtained at the step before with the aim of developing a formal ontology. This is the ontologic engagement. Formal semantics does not consider semantic notions anymore, but extensions i.e. the set of objects that satisfy properties defined in intension, at the preceding step. This formal ontology must take the form of a concept lattice. • Ontology operationalisation. During this last stage, the approach is to represent the ontology in a knowledge representation language that allows inferential services. There exist several knowledge representation languages, such as the conceptual graphs and description logics. Both of them allow a certain number of operations on the ontologies: inferences proper to graph structures, classification into tree structures for description logics. The latter mentioned are the type of language used by the Web Semantics for representing ontologies and making inferences. When using the Protege tool, as in our case, the OWL is the W3C standard used to develop the ontology. [START_REF] Noy | Ontology Development 101: A Guide to Creating Your First Ontology[END_REF]) is a publication dealing precisely with this subject matter. The authors describe here the reasons that can lead one to develop an ontology i.e. the usage of this kind of structure, its definition, several types of methodologies, as well as the composition and structure of an ontology. We found this article particularly interesting for its explicitness and pedagogical style. The example taken is a test ontology created by the Protege developers, a wine ontology.

State of the art of ontology usage in Systems Engineering, Requirements Engineering and Railway systems

This section provides a panel of works related to the usage of ontologies in the domains of Systems Engineering, Requirements Engineering and Railway Systems. The aim of this section is to provide an overview of the main aspects of our work, as well as to state the fact that they have already been studied. Thus, there exists a solid background to tackle now with complex railway systems (like ERTMS/ETCS is) while involving several concerns like formalisation, requirements engineering, traceability, …

Ontologies and software engineering

• In [START_REF] Barbosa | Ontology-based Development of Testing Related Tools[END_REF] an ontology called OntoTest is presented. This ontology is developed in order to promote organisation, reuse and sharing of software testing knowledge. The main concepts and artefacts of testing are described (processes, phases, resources, procedures). The ontology itself is figured with UML class diagrams. W3C formalisms are not used in the paper, but the ontology is now available in OWL format. • The work presented in [START_REF] Bonifacio | Improvement of Processes and Methods in Testing Activities for Safety-Critical Embedded Systems[END_REF] is very close to the goals of our work. Starting from an industrial-use case (the Onboard Unit of ERTMS) a methodology to improve the testing process is provided. This methodology involves the analysis of the SRS specifications, the rewriting of the requirements into a "formal" language. The definition of this language is based on a previously established ontology classically defining the concepts, relations and axioms of the domain.

Ontologies and requirements engineering

Castaneda et. al. (2011) describes the expected benefits, but also the challenges of using ontologies, in requirements engineering (RE) activities. This is exactly the basis of our approach. The main statement is that such an approach needs the definition of three ontologies: (1) an application domain ontology, (2) a requirements ontology and (3) a requirements specification document ontology. The application domain ontology is a double-utility ontology i.e. a domain ontology that defines the necessary concepts for all training in the domain, and an application ontology, which is one defining the concepts specific to a given application or method. The requirements ontology is used for representing requirements and their various relationships, as well as the relationships between requirements and systems, whereas the requirements specification document ontology is a documentary ontology. The present paper deals with the creation of an ontology of the first type presented above.

Ontologies and railway systems/applications

In [START_REF] Tanenbaum | Efficient data integration in the railway domain through an ontology-based methodology[END_REF], the authors present an ontology creation work conducted during the FP6 InteGRail project (InteGRail). They used the same tools as us (OWL, Protégé) to model an ontology that permits them to check network statement for infrastructure operators. By using the ontology, they combine the network statements of different countries in different formats and analyse them in a transparent way. They modelled the network using concepts such as network node, network line, track section, track node. All these concepts allow the authors to represent the railway network as an object graph. In our work we could reuse such concepts.

Global view of the proposed ERTMS ontology

This section presents the normative documentation and the methodology that we followed for acquiring this first version of our ERTMS ontology.

The ERTMS/ETCS System Requirements Specification -the normative documentation

The railway domain is an environment where numerous heterogeneous information sources exist. The ERTMS system basically relies on information exchange. Ontologies provide a number of useful features for intelligent systems, as well as for knowledge representation generally. The ERTMS ontology that we propose also aims at offering a solution for information exchange, and this for a better railway transportation world.

The ERTMS System Requirements Specification is a set of documents written in natural language, English in this case. It specifies the European Rail Traffic Management System/ European Train Control System, which is a control and signalisation innovative system of the railway vehicles and tracks. Also, system safety plays an important role in railway transport as it constitutes a challenging issue that has engaged strong and continuous research interest.

The chosen method

The method that we chose for the creation of this ERTMS ontology is the corpus-based methodology that is detailed and explained in section 3 [START_REF] Charlet | Ontologies pour le Web sémantique[END_REF]. This subsection presents our approach of constructing our ERTMS ontology, based on studying normative documentation.

For the first stage of this methodology i.e. corpus analysis we chose our corpus among the documents that exist in the domain of railway transport. One of these documents is the System Requirements Specification document that was imposed in the framework of this project, as it is essential for the system. It is actually a set of documents (SRS 3.2.0) provided by the European Railway Agency (ERA). Other related documents are the "ERTMS Glossary" (ERTMS Glossary, 2012) and the "ETCS Implementation Handbook" (ETCS, 2008) published by the International Union of Railways (UIC). This is an ontology created as a semantic model and module extracted from the below-mentioned documents. The extraction is based on the study and comprehension of these documents, and on the transposition of the information conceptualised in the same documents. All this was carried out manually by the authors of this article and not performed automatically, as some software can do. As the study of these SRS within the framework of this research is at its beginnings, we chose to start it manually for a better usage of the comprehension of human understanding. So, in the case of this first part of our ERTMS ontology, for the preparation of the corpus, only language processing carried out manually was used, for the reasons mentioned below. For the second step i. e. the semantic normalisation, the candidate terms identified at the first step were entered in an OWL format document using the Protégé tool. We began thus to build our ontology from normative documentation.

During the third step of the methodology i.e. the ontologic engagement, the concepts of the domain were formalised as classes (terms). An ontology is not only the identification and classification of concepts, but also of their inherent characteristics that are here called "properties". Moreover, the relations gather the concepts together. Primarily, we used the "is-a" relation which is a subsumption relation allowing the formal heritage of properties. The "has-a" relation, also known as composition, is also used in this ontology, this time not for the class layer but for the instance layer. Since, at the beginning, we had conceived our primary concept structure using the two relations for the classes, a differentiation became crucial as work proceeded. Then, other relations were established according to the system's syntax. These relations were created based on property declaration and domain specification (tab allowing us to select the class(es)) on which they take effect. For the fourth step i.e. the ontology operationalisation of the creation of this part of our ontology, we used description logics that are available in the Protégé tool. Our ontology is structured into several modules.

• the Entity module, i.e. the superclass containing several entities like Driver, ERTMS, Procedure, describes entities that are used to define the required system behaviour on a context level. • the OSI_Model is a sibling class of Entity, a module aiming at describing the Open Systems Interconnection (OSI) model. This is a conceptual model that characterises and standardises the internal functions of a communication system by partitioning it into abstraction layers. This module will be more thoroughly explained in section 6. • another sibling class of the above-mentioned one is Source. It formalises information about the SRS and other ERTMS/ETCS documents used as corpus of these ontology. • TrainCategories is also a child of the Entity superclass, containing information about the different types of rolling stock. After the representation of the concepts of a domain, the next step is to make inferences. For the moment, our ERTMS ontology does not contain this type of processing, but it is intended for future actions.

Focus on the radio-communication part

As mentioned in the sections before, this ontology is constructed by modules. One of these modules formalises the OSI (Open Systems Interconnection) model and another sub-module deals with the application of the generic OSI model to the ERTMS. This section presents the generic telecommunication model, followed by its instantiation with the OSI model and finally with the ERTMS telecommunication subsystem.

The radio telecommunication model

First, we defined a generic radio telecommunication model (Figure 2). This model/module is composed of several concepts: • the NetworkStack is the telecommunication stack which is composed of several Layers • the Layer is a part of the NetworkStack which is able to marshall and unmarshall some Messages.

Each Layer is linked to two other Layers: a higher Layer and a lower Layer. The combination of this set of layers is a NetworkStack. • a Layer manipulates some Messages • the Message defines the data that will be sent and received on the network by the Layers.

• the Telecommunication concept references the concepts defined above.

Feeding the ontology with the OSI model

Next, we populated the ontology with the concepts that describe the OSI model composed of 7 layers. This part of the work was useful to see if the concepts defined into the radio telecommunication model were enough and to be sure that nothing was forgotten.

Figure 3a presents the hierarchy as defined previously and all the instances which represent the different layers of a classical OSI network stack. There is one important relation between the layers. That relation describes the link between two consecutive layers. The relation between layers N and N+1 is hasHigherLayer, and its opposite hasLowLayer between N and N-1. The highest layer does not have a hasHigherLayer, nor does the lowest layer have a hasLowLayer. These relations are not shown on the Figure 3a in order to keep a clear schema.

Feeding the ontology with the ERTMS radio sub-system

We applied the same reasoning to represent the concepts of the ERTMS/ETCS radio sub-system. This radio subsystem is composed of three layers (from lower layer to higher layer):

• GSM_RLayer is based on the GSM specification with some modifications to fit the railway industry needs.

The goal of this layer is to transport data packets through a celullar network between the train and the Radio Block Center (RBC).

• the EuroradioLayer deals with the end to end communication between an embedded application into the train and an application on ground. This layer is also responsible for non functional properties like authentication and cryptography of the messages. • the ETCSLayer manages the messages at the application level of ETCS. This layer permits the communication between the on-board EVC and the ground system RBC that gives the movement authority grant(s) to the train. • AirGap, EurobaliseLayer and EuroloopLayer represent equipments put on the track. These equipments communicate with the train when it goes over them. • Figure 3b shows the ERTMS Network layer stack with three instances that correspond to the layers described just before.

Results and discussion

This ERTMS ontology is structured into several layers. The Thing superclass contains several classes like Entity, Source, OSI_Model, etc which, in their turn, have several sub-classes. For example, the Entity class reunites the subclasses Driver, ERTMS and Procedure. The ERTMS sub-subclass contains ApplicationLevel, ERTMSNetworkLayer and ETCS. These are just a few examples of terms that we entered in the surface levels of the class structure of this ontology.

Results

Currently, the ERTMS ontology that we have been creating contains 112 classes, 193 instances, and 104 properties including object, datatype and annotation properties. The maximum depth level is 9.

SRS coverage

Since we focused on a first feasibility of the approach, the current coverage of the available texts by our ontology is obviously reduced. This work shall be improved in order to make our "ontological product" actually usable. It would be a painstaking work that could possibly take advantages on techniques (and related tools) such as automatic language processing. For example, the following step of our experiment may be the use of the GATE framework [START_REF] Cunningham | Text Processing with GATE (Version 6)[END_REF], since it provides ontological and also machine learning facilities.

Modelling ERTMS/ETCS procedures

We have modelled the ERTMS procedures defined in the SRS. For instance, the "Shunting" mode is, by definition, a type of ERTMS/ETCS on-board equipment allowing a train to move without having the updated train data. Considering the flowcharts as state-transition machines, we transcribed a flowchart into a set of SWRL rules, each rule corresponding to a transition. By doing this, we intended to catch the dynamic behaviour of the ERTMS/ETCS.

Ontology quality

The quality of the ontology, viewed as a product, can be twofold: first, the quality of the embedded knowledge (as a semantic object); and second, the quality of the ontology itself (as a syntactic object).

The second point can be treated by the use of experience feedback from the elaboration of other ontologies and, particularly by taking into account the best practices of the domain sometimes identified and integrated into dedicated static analysis tools (like OOPS!) [START_REF] Poveda-Villalón | Validating Ontologies with OOPS![END_REF]. Table 1 gives the results of the evaluation of the ERTMS ontology by the tool OOPS!, in its current state. These results are barely correct because this "syntactic" aspect of the assessment has not been taken into account yet. For example, the pitfall with the worst score should be easily corrected simply by using the correct "annotation property" attribute for the definitions.

It is also possible to improve the overall quality (structure) of the current ontology by studying aspects like modularity [START_REF] Bezerra | ModOnto: A tool for modularizing ontologies[END_REF], thus improving the decomposition and the potential reuse of the knowledge. A better modularity should also make easier the reuse of other related ontologies like testing ontologies, RE ontologies.

Usage of reasoners

Knowledge quality is essentially a matter of specific expertise to the considered field, but it can also be enhanced by the power of inference mechanisms used especially to detect semantic inconsistencies, incompleteness of relations. All these criteria are not assessable by previous techniques (syntactic/structure level). As we study complex specification documents, it is even more important to implement these mechanisms earlier in the development process, so as to achieve a real "debugging" of the ontology before effective implementation of the system.

Linking ontology and external (formal) models

As a next step, when the ERTMS ontology will be rich enough to be usable, we will start to tackle the problem of deriving more concrete models (mainly formal ones). As described in Figure 4, the current work (number one circled) deals with the analysis of available documentation and expert knowledge to derive one ontology (and probably several others in the future) which can be taken as a first step for an abstract formalisation. Formal methods are highly recommended for the development of safety-critical (railway) systems (cf. CENELEC 50128 (EN50128, 2011). The ERTMS/ETCS is a system of this kind and, thus, a formalizable domain. Indeed, in the openETCS project (openETCS, 2012), a European large project involving the main actors of railway research, ERTMS/ETCS (semi-)formal models will be delivered (as well as the corresponding tool-chains). More than ten formalisms/approaches are studied. They range from ADA (the robust programming language), UML and/or sysML, to formal methods like SCADE, B or eventB, Petri nets. The next step (number two circled) will be the derivation of more concrete models using available and wellknown (semi-)formalisms like those used in the openETCS initiative. We intend to show that an initial formalisation derived from an ontological conceptualisation will be helpful to define the architecture and the main properties for derived formal models.

Since the ontological support languages (OWL, SWRL, etc) used while elaborating our ontology are not too far from classical first order logic and set theory, one path to explore may be a model transformation from our ontology into formal specifications expressed within a "classical" formalism such as the B formal method [START_REF] Abrial | The B-Book: Assigning Programs to Meanings[END_REF].

Connecting our approach to the artefacts (formal models) of the openETCS could be a perspective of this work.

Conclusions and perspectives

In the present paper, we presented an experimental approach aiming at establishing an ontology of a complex domain like the ERTMS/ETCS railway control system. This development is mainly based on the study of a set of referential texts. As an example of the benefits we expect to obtain, we presented the enrichment of the ontology with the consideration of OSI standard levels to define precisely the concepts regarding the radio communication aspects of ERTMS.

Fig. 1 .

 1 Fig. 1. Ontologies for software-based systems

Fig. 2 .

 2 Fig. 2. Generic radio telecommunication concepts

Fig. 3a .

 3a Fig. 3a. Hierarchy and instances for the OSI model. 3b. Hierarchy and instances for the ERTMS radio subsystems

Fig. 4 .

 4 Fig. 4. Ontologies in the formalised development of safety critical systems

Acknowledgements

The present research work is supported by the ICSIT (International Campus on Safety and Intermodality in Transportation) program and funded by the Nord Pas de Calais French Region and the ERDF (European Research and Development Funds). The authors gratefully acknowledge the support provided by these institutions.


Eric Duch

Gabriel Renault

VERTEX NIM PLAYED ON GRAPHS

Keywords: Combinatorial games, Nim, graph theory

Given a graph G with positive integer weights on the vertices, and a token placed on some current vertex u, two players alternately remove a positive integer weight from u and then move the token to a new current vertex adjacent to u. When the weight of a vertex is set to 0, it is removed and its neighborhood becomes a clique. The player making the last move wins. This adaptation of Nim on graphs is called Vertexnim, and slightly differs from the game Vertex NimG introduced by Stockman in 2004. Vertexnim can be played on both directed or undirected graphs. In this paper, we study the complexity of deciding whether a given game position of Vertexnim is winning for the first or second player. In particular, we show that for undirected graphs, this problem can be solved in quadratic time. Our algorithm is also available for the game Vertex NimG, thus improving Stockman's exptime algorithm. In the directed case, we are able to compute the winning strategy in polynomial time for several instances, including circuits or digraphs with self loops.

Background and definitions

We assume that the reader has some knowledge in combinatorial game theory. Basic definitions can be found in [START_REF] Berlekamp | Winning ways for your mathematical plays[END_REF]. We only remind that a P position denotes a position from which the second player has a winning strategy, while an N position means that the first player to move can win. Graph theoretical notions used in this paper will be standard and according to [START_REF] Bondy | Graph Theory with Applications[END_REF]. In particular, given a graph G = (V, E) and a vertex v of V , we set N (v) = {w ∈ V : (v, w) ∈ E}.

The original idea of this work is the study of a variant of Nim, called Adjacent Nim, in which both players are forced to play on the heaps in a specific cyclic order: given N heaps of tokens of respective sizes (n 1 , . . . , n N ), play the game of Nim under the constrainst that if your opponent has moved on heap i, you must move on heap i + 1 (or on the smallest next non-empty heap, in a circular way). Actually, our investigations led us to consider Adjacent Nim as a particular instance of the game NimG (for "Nim on Graphs") introduced by Stockman in [START_REF] Stockman | Presentation: The game of nim on graphs: NimG[END_REF].

As a brief story of the game, we remind the reader that the game of Nim was introduced and solved by Bouton in 1904 [START_REF] Bouton | Nim, a game with a complete mathematical theory[END_REF]. Since then, lots of variations were considered in the literature, the most famous one being Wythoff's game [START_REF] Wythoff | A modification of the game of Nim[END_REF][START_REF] Fraenkel | How to beat your Wythoff games' opponent on three fronts[END_REF]. One can also mention [START_REF] Duchêne | Geometrical extensions of Wythoff's game[END_REF][START_REF] Fraenkel | A generalization of Wythoff's game[END_REF][START_REF] Fraenkel | The Rat and the Mouse game[END_REF][START_REF] Fraenkel | The Raleigh game, Combinatorial number theory[END_REF][START_REF] Fraenkel | A new heap game[END_REF] as a non-exhaustive list. One of the most recent variant of Nim provides a topology to the heaps, which are organized as the edges of an undirected graph. This game was proposed by Fukuyama in 2003 [START_REF] Fukuyama | A Nim game played on graphs[END_REF][START_REF] Fukuyama | A Nim game played on graphs II[END_REF]. More precisely, an instance of its game is an undirected graph G = (V, E) with an integer weight function on E. A token is set on an arbitrary vertex. Then two players alternately move the token along a positive adjacent edge e and decrease the label of e to any strictly smaller non-negative integer. The first player unable to move loses the game (this happens when the token has all its adjacent edges with a label equal to zero). In his papers, Fukuyama gives necessary and sufficient conditions for a position on a bipartite graph to be P. He also computes the Grundy values of this game for some specific families of bipartite graphs, including trees, paths or cycles. In [START_REF] Erickson | Nim on the complete graph[END_REF], a larger set of graphs is investigated (including complete graphs), but only for the weight fonction f : E → {1}.

In 2004, Stockman considered another generalization of Nim on graphs that she called Vertex NimG. The main difference with Fukuyama's work is that the Nim heaps are embedded into the vertices of a graph. This definition raises a natural question when playing the game: does the player first remove some weight from a vertex and then move to another one, or does he first move to a vertex and then remove weight from it?

• The variant Move then remove of Vertex NimG was recently investigated by Burke & George in [START_REF] Burke | A PSPACE-complete Graph Nim[END_REF]. They showed that in the case where each vertex of the input graph G has a self loop, then this game is PSPACE-hard. To the best of our knowledge, nothing was proved in the general case yet. • The variant Remove then move of Vertex NimG is the one that was considerd by Stockman in [START_REF] Stockman | Presentation: The game of nim on graphs: NimG[END_REF]. In the case where the weight function is bounded by a constant, she gave a polynomial time algorithm to decide whether a given position is P or N . The same algorithm can be applied in the general case, but becomes exponential according to the order of G.

In Fukuyama's or Stockman's definitions, the game ends when the player is blocked because of a null weight. This means that unlike the original game of Nim, their variants may end with remaining weight on the graph. To be closer to the original Nim, we have defined the rules of our variant of Vertex NimG in such a way that the game ends only when all the weight is removed from the graph. This variant was introduced on both directed and undirected graphs with possible loops, and under the remove then move convention. Multiple edges are not considered, since the weight is set on the vertices. We start by giving the definition of our game on undirected graphs, which is called Undirected vertexnim.

Definition 1. Undirected vertexnim. Let G = (V, E) be an undirected connected graph, let w : V → N >0 be a function which assigns to each vertex a positive integer. Let u ∈ V be a starting current vertex. In this game, two players alternately decrease the value of the current vertex u and choose an adjacent vertex of u as the new current vertex. When the value w(v) of a vertex v is set to 0, then v and its incident edges are removed from G, the subgraph N (v) of G becomes a clique, and a loop is added on each vertex of N (v). The game ends when G is empty. The player who makes the last move wins the game.

In this definition, we make N (v) become a clique after v reaches zero to prevent the graph to be disconnected. In other words, we can say that in order to choose the next current vertex, it suffices to follow any path of zero vertices ending on a non zero vertex. We also add loops to prevent a player to be blocked on a vertex. The example below shows an execution of the game, the current vertex being the one with the triangle. This game can naturally be extended to directed graphs, with some constraints ensuring that all the weight is removed in the end. In particular, arcs are added when the weight of a vertex goes to zero (by the same way that a clique is build in the undirected case). We also need to play on a strong connected digraph, to avoid to be blocked on a vertex having a null outdegree. Recall that in a strong connected digraph, for every couple of vertices (u, v) there exists a path from u to v. This directed variant will be called Directed vertexnim. Definition 2. Directed vertexnim. Let G = (V, E) be a strong connected digraph, and let w : V → N >0 be a function which assigns to each vertex a positive integer. Let u ∈ V be the starting current vertex. In this game, two players alternately decrease the value of the current vertex u and choose an adjacent vertex of u as the new current vertex. When the value of a vertex v is set to 0, then v is removed from G and all the pairs of arcs (p, v) and (v, s) (with p and s not necessarily distinct) are replaced by an arc (p, s). The game ends when G is empty. The player who made the last move wins the game.

Note that in Definition 2, the strong connectivity of G is preserved when deleting a vertex. Hence it is always possible to play whenever G is not empty. Figure 1 illustrates a sequence of moves of Directed vertexnim, where both players remove all the weight of the current vertex at their turn. The current paper deals with the complexity of both versions of vertexnim, in the sense of Fraenkel [START_REF] Fraenkel | Complexity, Appeal and Challenges of combinatorial games[END_REF]. In particular, we will prove the tractability of the game, which implies to show that the outcome (P or N ) of a game position can be computed in polynomial time. In Section 2, we will solve the game Adjacent Nim, which is actually an instance of directed vertexnim on circuits. Section 3 will be devoted to the resolution of directed vertexnim for any strong connected digraph having a loop on each vertex. Section 4 concerns undirected vertexnim, whose tractability is proved in the general case. As a corollary, we will show that our algorithm also solves Stockman's Vertex NimG in quadratic time, improving the results presented in [START_REF] Stockman | Presentation: The game of nim on graphs: NimG[END_REF]. In Section 5, we finally mention how our results can be adapted to misère versions of vertexnim.

Adjacent Nim

As explained in the introduction, this game was the original motivation of our work. With the above formalism, it can be expressed as an instance of directed vertexim on an elementary circuit

C N = (v 1 , v 2 , . . . , v N ) with the orientation (v i , v i+1 ) : 1 ≤ i < N and (v N , v 1 )
of the arcs. In Theorem 3, we fully solve adjacent Nim in the case where all the weights are strictly greater than 1. Without loss of generality, we will assume that the starting position is always v 1 .

Theorem 3. Let (C N , w, v 1 ) : N ≥ 3 be an instance of adjacent Nim with w : V → N >1 . • If N is odd, then (C N , w, v 1 ) is an N position. • If N is even, then (C N , w, v 1 ) is an N position iff min{argmin 1≤i≤N w(v i )} is even.
Proof. • If N is odd, then the first player can apply the following strategy to win: first play w(v 1 ) → 1. Then for all 1 ≤ i < (N -1)/2: if the second player empties v 2i , then the first player also empties the following vertex v 2i+1 . Otherwise play w(v 2i+1 ) → 1. The strategy is different for the last two vertices of C N : if the second player empties v N -1 , then play w(v N ) → 1, otherwise play w(v N ) → 0. As w(v 1 ) = 1, the second player is now forced to empty v 1 . Since an even number of vertices was deleted since then, we still have an odd circuit to play on. It now suffices for the first player to empty all the vertices on the second run. Indeed, the second player is also forced to set each weight to 0 since he has to play on vertices satisfying w = 1. Since the circuit is odd, the first player is guaranteed to make the last move on v N or v N -1 .

• If N is even, we claim that who must play the first vertex of minimum weight will lose the game. The winning strategy of the other player consists in decreasing by 1 the weight of each vertex at his turn. Without loss of generality, assume that min{argmin 1≤i≤N w(v i )} is odd. If the strategy of the second player always consists in moving w(v i ) → w(v i ) -1, then the first player will be the first to set a weight to 0 or 1. If he sets a vertex to 0, then the second player now faces an instance

(C ′ N -1 , w ′ ) with w ′ : V ′ → N >1
, which is winning according to the previous item. If he sets a vertex to 1, then the second player will empty the following vertex, leaving to the first player a position (

C ′ N -1 = (v ′ 1 , v ′ 2 , . . . , v ′ N -1 ), w ′ ) with w ′ : V ′ → N >1 except on w ′ (v ′ N -1 ) = 1.
This position corresponds to the one of the previous item after the first move, and is thus losing. Problem 4. The question of deciding whether a given position is P or N remains open in the cases where some vertices have a weight equal to 1. Indeed the previous strategy cannot be applied anymore, and we did not manage to get satisfying results when the 1 ′ s are owned by different players.

Remark 5. What if we adapt Stockman's Vertex NimG to directed graphs ? Recall that it means that vertices of null weight are never removed, and a player who must play from a 0 loses. In the case of circuits, it is easy to see that Theorem 3 remains true, even if there are vertices of weight 1. On a general graph, we conjecture that this game should be at least as hard as the game Geography [14] (nevertheless the reduction needs to be done).

Directed graphs with all loops

Dealing with directed vertexnim on any strong connected digraph is much harder. We managed to decide whether a position is P or N only in the case where there is a loop on each vertex. This is somehow a way to consider NimG with the extended neighborhood, as proposed in [START_REF] Burke | A PSPACE-complete Graph Nim[END_REF]. Theorem 6. Let (G, w, u) be an instance of directed vertexnim where G is strongly connected with a loop on each vertex. Deciding whether (G,w,u) is P or

N can be done in time O(|V (G)||E(G)|).
The proof of this theorem requires several definitions that we present here.

Definition 7. Let G = (V, E) be a directed graph. We define a labeling lo G : V (G) → {P, N } as follows : Let S ⊆ V (G) be a non-empty set of vertices such that the graph induced by S is strongly connected and ∀u ∈ S, ∀v ∈

(V (G)\S), (u, v) / ∈ E(G). Let T = {v ∈ V (G)\S | ∃u ∈ S, (v, u) ∈ E(G)}.
Let G e be the graph induced by V (G)\S and G o the graph induced by

V (G)\(S ∪ T ). If |S| is even, ∀u ∈ S, lo G (u) = N , and ∀v ∈ G\S, lo G (v) = lo Ge (v). If |S| is odd, ∀u ∈ S, lo G (u) = P, ∀v ∈ T , lo G (v) = N and ∀w ∈ G\(S ∪ T ), lo G (w) = lo Go (w).
When decomposing the graph into strongly connected components, S is one of those with no out-arc. The choice of S is not unique, unlike the lo G function: if S 1 and S 2 are both strongly connected components without out-arcs, the one which is not chosen as first will remain a strongly connected component after the removal of the other, and as it has no out-arc, none of its vertices will be in the T set. then (G,w,u) is an N position if and only if |V (G)| is odd since the problem reduces to "She loves move, she loves me not". We will now suppose that G = G ′ , and consider two cases about w(u):

Proof. Let G ′ be the induced subgraph of G such that V (G ′ ) = {v ∈ V (G) | w(v) = 1}. If G = G ′ ,
• Assume w(u) 2. If there is a winning move which reduces u to 0, then we can play it and win. Otherwise, reducing u to 1 and staying on u is a winning move. Hence (G, w, u) is an N position.

• Assume w(u) = 1, i.e., u ∈ G ′ . According to Definition 7, computing lo G ′ yields a sequence of couples of sets (S i , T i ) (which is not unique). Note that some T i may be empty (this happens when the corresponding S i has an even size). Thus the following assertions hold: if u ∈ S i for some i, then any direct successor v of u is in a set S j or T k with j i and k < i, and if u ∈ T i = ∅ for some i, then there exists a direct successor v of u in the set S i , with lo G ′ (v) = P. Our goal is to show that (G, w, u) is an N position if and only if lo

G ′ (u) = N by induction on |V (G ′ )|. If |V (G ′ )| = 1, then V (G ′ ) = {u} and lo G ′ (u) = P.
Hence we are forced to reduce u to 0 and go to a vertex v such that w(v)

2, which we previously proved to be a losing move. Assume |V (G ′ )| 2. First, note that when one reduce the weight of a vertex v to 0, the replacement of the arcs makes the strongly connected components remain the same (except the component containing v of course, which loses one vertex). Consequently, if u ∈ S i for some i, then for any vertex v ∈ ∪ i-1 l=1 (T l ∪ S l ), lo G ′ \{u} (v) = lo G ′ (v) and for any vertex w ∈ S i \{u}, lo G ′ \{u} (w) = lo G ′ (w). If u ∈ T i for some i, then for any vertex

v ∈ (∪ i-1 l=1 (T l ∪ S l )) ∪ S i , lo G ′ \{u} (v) = lo G ′ (v)
. We now consider two cases about u: first assume that lo G ′ (u) = P, with u ∈ S i for some i. We reduce u to 0 and we are forced to move to a direct successor v. If w(v)

2, we previously proved this is a losing move.

If v ∈ ∪ i-1 l=1 (T l ∪ S l ), then lo G ′ \{u} (v) = lo G ′ (v) = N
and it is a losing move by induction hypothesis. If v ∈ S i , then lo G ′ \{u} (v) = lo G ′ (v) = P and it is a losing move by induction hypothesis. Now assume that lo G ′ (u) = N . If u ∈ T i for some i, we can reduce u to 0 and move to a vertex v ∈ S i , which is a winning move by induction hypothesis. If u ∈ S i for some i, it means that |S i | is even, we can reduce u to 0 and move to a vertex v ∈ S i , with lo G ′ \{u} (v) = lo G ′ (v) = N . This is a winning move by induction hypothesis. Hence, (G, w, u) is an N position if and only if lo G ′ (u) = N . Figure 3 illustrates the computation of the lo function. Note that one of the reasons for which we have slightly changed Stockman's rules is that we assumed that our current game had a lower complexity than Vertex NimG or Geography [14] on directed graphs. The previous theorem shows that our assumption was somehow true, since we remind the reader that Vertex NimG was proved to be PSPACE-hard with all loops (for the move then remove convention [START_REF] Burke | A PSPACE-complete Graph Nim[END_REF], the other convention being trivial with all loops).

Undirected graphs

In the undirected case, it is easy to show that if each vertex has a self loop, deciding whether a position is P or not only depends on the size of the subset {v ∈ V | w(v) = 1}. Remark that this game can be solved by Theorem 6, by saying that it suffices to replace each edge (u, v) by two arcs (u, v) and (v, u). Yet, the following proposition improves the complexity of the method, which becomes linear.

Proposition 9. Let (G = (V, E), w, u) be an instance of undirected vertexnim such that there is a loop on each vertex of G. Deciding whether (G, w, u) is P or N can be done in time O(|V |). then (G,w,u) is an N position if and only if |V (G)| is odd since the problem reduces to "She loves move, she loves me not". In the rest of the proof, assume G = G ′ .

Proof. Let G ′ be the induced subgraph of G such that V (G ′ ) = {v ∈ V (G) | w(v) = 1}. If G = G ′ ,
• We first consider the case where w(u)

2. If there is a winning move which reduces u to 0, then we play it and win. Otherwise, reducing u to 1 and staying on u is a winning move. Hence (G, w, u) is an N position.

• Assume w(u) = 1. Let n u be the number of vertices of the connected component of G ′ which contains u. We show that (G, w, u) is an N position if and only if n u is even by induction on n u . If n u = 1, then we are forced to reduce u to 0 and move to another vertex v having w(v)

2, which we previously proved to be a losing move. Now assume n u 2. If n u is even, we reduce u to 0 and move to an adjacent vertex v with w(v) = 1, which is a winning move by induction hypothesis. If n u is odd, then we reduce u to 0 and we are forced to move to an adjacent vertex v. If w(v) 2, then we previously proved it is a losing move. If w(v) = 1, this is also a losing move by induction hypothesis. Therefore in that case, (G, w, u) is an N position if and only if n u is even.

In the general case where the loops are optional, the tractability of the game is still guaranteed, even though the previous linear time algorithm is no more available. The proof of this theorem requires several definitions that we present here.

Definition 11. Let G = (V, E) be an undirected graph with a weight function w : V → N >0 defined on its vertices.

Let S = {u ∈ V (G) | ∀v ∈ N (u), w(u) w(v)}. Let T = {v ∈ V (G)\S | ∃u ∈ S, (v, u) ∈ E(G)}.
Let G ′ be the graph induced by G\(S ∪ T ). We define a labeling lu G,w of its vertices as follows :

∀u ∈ S, lu G,w (u) = P, ∀v ∈ T , lu G,w (v) = N and ∀t ∈ G\(S ∪ T ), lu G,w (t) = lu G ′ ,w (t). Proof. Let G u be the induced subgraph of G such that V (G u ) = {v ∈ V (G) | w(v) = 1 or v = u}, and G ′ be the induced subgraph of G such that V (G ′ ) = {v ∈ V (G) | w(v) 2 and (v, v) / ∈ E(G) and ∀t ∈ V (G), (v, t) ∈ E(G) ⇒ w(t) 2}. If G = G u and w(u) = 1, then (G, w, u) is an N position if and only if |V (G)
| is odd since it reduces to "She loves move, she loves me not". If G = G u and w(u) 2, we reduce u to 0 and move to any vertex if |V (G)| is odd, and we reduce u to 1 and move to any vertex if |V (G)| is even; both are winning moves, hence (G, w, u) is an N position. In the rest of the proof we will assume that G = G u . In the next three cases, we consider the case u / ∈ G ′ . • Case (1) Assume w(u) 2 and there is a loop on u. If there is a winning move which reduces u to 0, then we can play it and win. Otherwise, reducing u to 1 and staying on u is a winning move. Therefore (G, w, u) is an N position.

• Case (2) Assume w(u) = 1. Let n be the number of vertices of the connected component of G u which contains u. We will show that (G, w, u) is an N position if and only if n is even by induction on n. If n = 1, then we are forced to reduce u to 0 and move to another vertex v, with w(v) 2, which was proved to be a losing move since it creates a loop on v. Now assume n 2. If n is even, we reduce u to 0 and move to a vertex v satisfying w(v) = 1, which is a winning move by induction hypothesis (the connected component of G u containing u being unchanged, except the removal of u). If n is odd, we reduce u to 0 and move to some vertex v, creating a loop on it. If w(v) 2, we already proved this is a losing move. If w(v) = 1, it is a losing move by induction hypothesis. We can therefore conclude that (G, w, u) is an N position if and only if n is even. Figure 4 illustrates this case.

• Case (3) Assume w(u) 2 and there is a vertex v such that (u, v) ∈ E(G) and w(v) = 1. Let n be the number of vertices of the connected component of G u which contains u. If n is odd, we reduce u to 1 and we move to v, which we proved to be a winning move. If n is even, we reduce u to 0 and we move to v, which we also proved to be winning. Hence (G, w, u) is an N position in that case. Figure 4 illustrates this case.

• Case (4) Assume u ∈ G ′ . We will show that (G, w, u) is N if and only if Proof. The proof works similarly to the previous one, except that the subgraph G u is no more useful. Hence we have four cases:

• If w(u) = 1 and u has no self loop, then the position is P.

• If w(u) ≥ 1 and there is a loop on u, then it is N .

• If w(u) ≥ 2 and there is a vertex v such that (u, v) ∈ E and w

(v) = 1, then it is an N position. • If u ∈ G ′ , then compute lu G ′ ,w (u) as in Theorem 4.
Note that the proof is still working if there exist vertices of null weight at the beginning. It suffices to consider the two following properties: if w(u) = 0 then this is P, and if u is adjacent to some v with w(v) = 0, then it is N .

Misère versions

The misère version of a game is a game with the same rules except that the winning condition is reversed, i.e., the last player to move loses the game. The following results shows that in almost all cases, misère and normal versions of Vertexnim have the same outcomes. Proof. If all vertices have weight 1, then (G, w, u) is an N position if and only if |V (G)| is even since it reduces to the misère version of "She loves move, she loves me not". Otherwise, we can use the same proof as the one of Theorem 6 to see that (G, w, u) is N in the misère version if and only if it is N in the normal version.

Remark 15. Though the algorithms we give for both Undirected Vertexnim and Directed Vertexnim can easily be adapted for the misère version, it does not seem to be the case with the algorithm we give for Vertex NimG.

Problem 16. This section showed that Vertex NimG and Undirected Vertexnim can both be solved in polynomial time. Does this remain true when considering the Move then remove convention ?

Conclusion

When dealing with an undirected graph, we proved that both versions of Vertex NimG (Stockman's version where the game ends whenever a player is blocked on a 0, and our version which allows to play until all the weight is removed from the graph) are tractable. We even proved that deciding whether a given position is P or N can be done in quadratic time, which is a real improvement compared to the exptime algorithm presented in [START_REF] Stockman | Presentation: The game of nim on graphs: NimG[END_REF]. Unfortunately, the directed case turns out to be more tricky, even for simple graphs such as circuits. Yet, it seems that our variant of Nim on graphs is more accessible than Vertex NimG or Geography, as the results obtained in Theorem 6 allow us to be optimistic for graphs where loops become optional.

Figure 1 .

 1 Figure 1. Playing undirected vertexnim

Figure 2 .

 2 Figure 2. Playing directed vertexnim

Figure 3 .

 3 Figure 3. Exemple of lo labeling function Problem 8. Can one provide a characterization of the P and N positions in the general case where self loops are optional?Note that one of the reasons for which we have slightly changed Stockman's rules is that we assumed that our current game had a lower complexity than Vertex NimG or Geography[14] on directed graphs. The previous theorem shows that our assumption was somehow true, since we remind the reader that Vertex NimG was proved to be PSPACE-hard with all loops (for the move then remove convention[START_REF] Burke | A PSPACE-complete Graph Nim[END_REF], the other convention being trivial with all loops).

Theorem 10 .

 10 Let (G, w, u) be an instance of undirected vertexnim. Deciding whether (G, w, u) is P or N can be done in O(|V (G)||E(G)|) time.

Figure 4 .

 4 Figure 4. Case 2: the connected component containing u has an odd size: this is a P position.

Figure 5 .

 5 Figure 5. Case 3: an N position since u of weight w(u) > 1 has a neighbor of weight 1.

Figure 6 .

 6 Figure 6. Case 4: lu-labeling of the subgraph G ′

Corollary 12 .

 12 Let (G, w, u) be an instance of Vertex NimG with w : V → N >0 . Deciding whether (G, w, u) is P or N can be done in O(|V (G)||E(G)|) time.

Theorem 13 .

 13 Let (G, w, u) be an instance of undirected vertexnim under the misère convention. Deciding whether (G, w, u) is P or N can be done in O(|V (G)||E(G)|) time. Proof. If all vertices have weight 1, then (G, w, u) is an N position if and only if |V (G)| is even since it reduces to the misère version of "She loves move, she loves me not". Otherwise, we can use the same proof as the one of Theorem 4 to see that (G, w, u) is N in the misère version if and only if it is N in the normal version. Theorem 14. Let (G, w, u) be an instance of directed vertexnim in the misère version, where G is strongly connected, with a loop on each vertex. Deciding whether (G,w,u) is P or N can be done in time O(|V (G)||E(G)|).