Johann-Mattis List¹

Simon J Greenhill¹

Cormac Anderson¹

Thomas Mayer

Tiago Tresoldi¹

Robert Forkel¹

Simon J Greenhill¹²

Thomas Mayer³

CLICS 2 An Improved Database of Cross-Linguistic Colexifications

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

When linguists succeed in identifying similar patterns across various languages, a number of different types of explanations for these similarities are possible. Common patterns might result from coincidence; from natural reasons with a basis in human cognition, psychology or physiology, or indeed the nature of our environment; or they might derive rather from historical processes, among which it is customary to differentiate inheritance and contact. Traditionally, coincidence is not considered linguistically interesting, while natural reasons are the primary focus of work in linguistic typology, as well as providing the theoretical grounding for various universal frameworks of grammatical architecture, while inheritance and contact fall into the purview of historical linguistics. However, to draw a clear dividing line between these two subfields is not necessarily useful or even tenable, as the research results of each feed back into the other, and unpicking which of the various explanations for a given phenomenon is most convincing is not always an easy task. Nowhere is this as clear as in the domain of lexical typology.

Languages differ in how they label the universe and sometimes these labels clash in interesting and informative ways, such that one word form has multiple meanings. This may result from coincidence, termed homophony, whereby multiple meanings for one word form arise accidentally as two word forms come to sound alike, as in French paix 'peace' vs. pet 'fart', which are both pronounced as [pɛ]. In contrast to this are cases of polysemy, in which one word form comes to have multiple related senses, as in Russian дерево dérevo, which can denote both 'tree' and 'wood'.

Cases of polysemy may be cross-linguistically frequent, in which case an explanation can likely be found in natural factors, be they linked to some aspect of human psychology or cognition, or the inherent structure of the natural environment (e.g. 'rain' and 'water', the above example of 'tree' and 'wood', or the common colexification of 'moon' and 'month'). On the other hand, where a polysemic pattern is relatively rare cross-linguistically, this is likely to point to a historical explanation in common inheritance or contact. For example, many Austronesian and Papuan languages in eastern New Guina and northern Australia use the same term for both 'fire', 'firewood', and 'tree. As this pattern is rare world-wide, this hints that there might be some deep connection between these groups across the Torres Strait [START_REF] Schapper | Tree, firewood and fire in the languages of Sahul[END_REF]). Another case is given by [START_REF] Urban | Sun'='Eye of the Day': A linguistic pattern of Southeast Asia and Oceania[END_REF], who notes that the word for 'sun' can typically be translated as 'eye of the day' in many Austroasiatic, Tai-Kadai, and Austronesian languages. In spite of the fact that a diachronic development based on a similar equation is attested in Indo-European (e.g. Old Irish súil 'eye', from the PIE root *seh₂l-, thus cognate with Latin sōl 'sun', see Vaan 2008, 570; Classical Armenian արեգակն aregakn, a compound of arew 'sun' and akn 'eye', see [START_REF] Olsen | Thoughts on Indo-European compounds -inspired by a look at Armenian[END_REF], the relative cross-linguistic rarity of this pattern and its prevalence in Southeast Asia suggests an explanation in terms of historical factors.

Deciding on a natural or historical explanation (i.e. distinguishing between homophony and polysemy) may be relatively straightforward for small groupings of languages for which detailed etymological and historical knowledge is available, but it becomes increasingly difficult on a larger scale, and impossible where detailed historical information is unknown. To circumvent this problem, scholars have increasingly begun to use the agnostic cover term colexification, where two senses in a given language colexify if the language uses the same lexical form for both [START_REF] François | Semantic maps and the typology of colexification: intertwining polysemous networks across languages[END_REF]. Taking a colexification approach enables scholars to approach questions of lexical semantics from the perspective of the data: if a pattern of colexification of certain meanings in one language is replicated across different languages or linguistic areas, that is indicative (if not diagnostic) of polysemy, rather than homophony [START_REF] List | Using network approaches to enhance the analysis of crosslinguistic polysemies[END_REF]. However, if frequency is to be used in this way as a proxy to infer polysemy, reliable large-scale cross-linguistic colexification resources are required. The revised CLICS database outlined in this paper is one such resource.¹

A key underpinning of all colexification studies, whether explicitly or implicitly, are networks, which play a crucial role in the investigation of cross-linguistic colexification patterns. First, they offer a convenient way to visualize the complexity of recurring semantic associations along with a number of high-quality tools for the interactive exploration of network data [START_REF] Smoot | Cytoscape 2.8[END_REF][START_REF] Bastian | Gephi: An Open Source Software for Exploring and Manipulating Networks[END_REF]. Second, thanks to recent advances in the empirical study of networks [START_REF] Newman | Networks. An Introduction[END_REF], many aspects of network structures are well understood, and a multitude of methods and statistics are available [START_REF] Csárdi | The igraph software package for complex network research[END_REF][START_REF] Hagberg | NetworkX. High productivity software for complex networks[END_REF], making it easy for scholars to apply them in their research.

The application of colexifications in the form of a network is straightforward. Following [START_REF] Cysouw | Semantic maps as metrics on meaning[END_REF], lexical comparative concepts [START_REF] Haspelmath | Comparative concepts and descriptive categories[END_REF] are represented as nodes in a network, while edges connect colexified concepts. The problem with this approach is that it does not allow one to represent whether a given word form colexifies more than two concepts. In order to represent this kind of information, more complicated network structures are needed, like hypergraphs, in which one edge can connect more than two nodes,² or bipartite networks (Newman, 2010, 122), in which nodes are divided into two types and edges can only be drawn between different types (see [START_REF] Hill | Challenges of annotation and analysis in computer-assisted language comparison: A case study on Burmish languages[END_REF] for an example of bipartite colexification networks). A further enhancement comes from using different edge weights where the weights reflect the ¹Historically, the idea of colexifications goes back to the concept of semantic maps [START_REF] Haspelmath | The geometry of grammatical meaning: semantic maps and cross-linguistic comparison[END_REF], which was most prominently used by typologists to study grammaticalization patterns (van der [START_REF] Van Der Auwera | A semantic map for depictive adjectivals[END_REF][START_REF] Cysouw | Building semantic maps: The case of person marking[END_REF][START_REF] Forker | Towards a semantic map for intensifying particles: Evidence from Avar[END_REF], before it inspired scholars to study phenomena of lexical typology in a similar manner (see the very detailed overview in Georgakopoulos and Polis 2018). Since semantic maps, however, imply rather specific techniques for analysis, which are not necessarily directly required when studying phenomena of lexical typology (as, for example, reflected in the articles introduced by Koptjevskaja-Tamm 2012), we prefer to look at colexifications derived from cross-linguistic data in form of a network. ²This network representation is most frequently used for the drawing of isogloss maps in areal linguistics and dialectology. See [START_REF] Georgakopoulos | The meaning of ancient words for 'earth': An exercise in visualizing colexification on a semantic map[END_REF] for examples involving colexifications. Unfortunately, hypergraphs are very difficult to visualize. Since all nodes in the graph sharing the same feature need to be shown as collected by drawing a boundary around them (excluding all nodes not sharing that very feature), a specific re-arranging of nodes and boundaries is required, which is a challenge both for computational and manual approaches to visualization. frequency of a given colexification in a given dataset, while node weights represent the overall occurrence of a given concept [START_REF] List | Using network approaches to enhance the analysis of crosslinguistic polysemies[END_REF]. Figure 1 gives examples for different possibilities for representing cross-linguistic colexification data in the form of networks.

The promise of a network-based approach to colexification (see [START_REF] List | Using network approaches to enhance the analysis of crosslinguistic polysemies[END_REF][START_REF] Mayer | An interactive visualization of cross-linguistic colexification patterns. In Visualization as added value in the development, use and evaluation of linguistic resources[END_REF] for colexification analyses and Rosvall and Bergstrom 2008 for general purpose studies) led to the publication of the Database of Cross-Linguistic Colexifications (CLICS, [START_REF] List | Sequence comparison in historical linguistics[END_REF], which provided cross-linguistic colexification patterns for 1280 concepts across 220 language varieties. While this version of the CLICS database was a valuable resource it also had a number of serious shortcomings. In particular, it had little data, including only 220 languages spoken primarily in South America and Eurasia, and what data were available were hard to check, curate and extend.

In this paper we describe an updated release of CLICS (henceforth called CLICS²) based around a new framework that attempts to solve these problems, while at the same time scaling up the available data, thus facilitating future research into colexifications. The most important points of improvements we see are:

(A) separating data from display, (B) making exhaustive and principled use of existing reference catalogs like Concepticon [START_REF] List | Concepticon. A resource for the linking of concept lists[END_REF] for concepts) and Glottolog [START_REF] Hammarström | Glottolog[END_REF], for languages) along with recently proposed standardization efforts for cross-linguistic data [START_REF] Forkel | Cross-Linguistic Data Formats (CLDF)[END_REF], (C) curating data and code with help of a transparent Application Programming Interface (API), and

(D) regularly releasing data in release cycles of at least one per year [START_REF] Haspelmath | CLLD -Cross-Linguistic Linked Data[END_REF].

In following these design guidelines, we have developed a new database of cross-linguistic colexifications which supersedes the old CLICS database not only in size, both in terms of the number of language varieties and the number of comparative concepts represented, but also with respect to the ease of data curation and the flexibility of the API.

How to compare semantics across languages?

Semantic comparison across languages is notoriously difficult. A naive approach to identifying colexification across languages would be to simply map identical translation glosses in wordlists and dictionaries to each other. However, this can easily lead to errors. For example, [START_REF] Chén | Lùn yǔyán jiēchù yǔ yǔyán liánméng 论语言接触与语言联盟 [Language contact and language unions[END_REF] originally intended to directly translate [START_REF] Swadesh | Lexico-statistic dating of prehistoric ethnic contacts[END_REF] list of 200 items for Chinese dialects. However, the item dull (knife) was mistranslated as dāi, bèn 呆, 笨 'dull, stupid' in the Chinese questionnaire. Chén's version of the Swadesh 200 item list became quite influential in China and was re-used in a number of studies (Ben [START_REF] Hamed | Stuck in the forest: Trees, networks and Chinese dialects[END_REF][START_REF] Wang | Basic words and language evolution[END_REF].

Another approach would be to harvest data for clearly attested polysemies across the languages of the world. Scholars could collect instances of colexifications which they deem interesting, and by using careful hand-collected data, these scholars could control for word meaning and homophony from the start. Such an approach would have the advantage of being extremely flexible in terms of the concepts and the languages investigated. However, the amount of work required for a project of such a nature makes it unfeasible to assemble and curate a global database of polysemies. One project that has attempted this is DatSemShifts [START_REF] Bulakh | Database of semantic shifts in the languages of the world[END_REF], which attempts to provide an exhaustive resource on attested instances of semantic shifts across the languages of the world. In its 2015 form,³ the DatSemShifts database listed as many as 2424 distinct glosses for comparative concepts. The glosses were, however, only minimally specified, which makes it difficult for users to both find a certain concept and to understand what concept they are dealing with, cross-linguistically.

Harvesting cross-linguistic data with Concepticon

In order to make semantic association patterns comparable across the world's languages, it is clear that we must base our analysis on a rigorous collection of comparative concepts. The Concepticon reference catalog project [START_REF] List | Concepticon. A resource for the linking of concept lists[END_REF][START_REF] List | Concepticon. A Resource for the linking of concept list[END_REF] is an attempt to provide consistent links across the multitude of lexical questionnaires that linguists have used to elicit words. Concepticon works by defining specific concept sets based on published datasets (whether these are from field work, or from historical or typological studies), and then linking the labels used by researchers to these defined conceptsets. For example, the "dull, blunt" vs. "dull, stupid" error is solved by linking the "dull" label in the list of [START_REF] Chén | Lùn yǔyán jiēchù yǔ yǔyán liánméng 论语言接触与语言联盟 [Language contact and language unions[END_REF] to the concept set ¹⁵¹⁸ while linking that of [START_REF] Swadesh | Lexico-statistic dating of prehistoric ethnic contacts[END_REF] to the concept set ³⁷⁹.⁴ If possible, these links are further checked against the original data, that is, the words in the target languages that were elicited in the end, in order to make sure that what is glossed as blunt is indeed reflecting the comparative concept stupid.

The immediate advantage of linking data to the Concepticon is that it enables us to merge data from different sources quickly and safely. We now know which word lists contain lexemes for ¹⁵¹⁸ and which contain lexemes for ³⁷⁹. And we can now directly ask which languages contain lexemes that colexify ¹⁵¹⁸ and ³⁷⁹, and colexify these lexemes with any of the other 3144 concept sets defined in Concepticon. In order to avoid errors, we have striven for rigor and strictness when linking concepts to Concepticon. Concepticon does not tolerate "fuzzy" matchings and deliberately avoids linking one elicitation gloss in a single dataset to more than one concept set in the Concepticon resource. If no ideal concept ³The database was originally freely accessible at http://datsemshifts.ru but is currently under construction. The version we refer to is the one we accessed on December 29, 2015. ⁴Superscript numbers indicate the identifier used by Concepticon. set could be found to link a given elicitation gloss in a questionnaire, it was left unlinked rather than linking to a semantically "close" concept.

Concepticon concept sets can further be linked among each other with help of a simplifying ontology that identifies concept sets which are broader or narrower with respect to their denotation range. The concept set ²¹²¹, for example, is useful for languages such as Russian or Irish, where the words рука ruká and lámh respectively refer not only to the part of the arm which other languages denote as hand, but also to the entire upper limb. The concept set ²¹²¹ is thus considered broader than either ¹²⁷⁷ or ¹⁶³⁷. While scholars might object to this procedure, preferring to represent a comparative concept reflecting the semantics of Russian рука ruká or Irish lámh by linking them to both and , it is important to emphasize that this practice, which may seem counterintuitive from the perspective of a given language, is critical if one wishes to guarantee a rigorous mapping of word elicitation glosses in questionnaires to lexical comparative concepts. If a given questionnaire contains the gloss arm/hand (as we can find across many questionnaires which have been used to assemble a large number of data points) and we linked it to both ¹²⁷⁷ and ¹⁶³⁷, we would lose the essential information that the original questionnaire was asking for the word expressing the concept that covers both concept sets in a single term. Since the ontology allows us to derive the information that is semantically broader than and , we can choose, over the course of our analysis, to link the elicitation gloss arm/hand to both narrower concept sets.

Each Concepticon gloss is also linked to additional metadata e.g. a semantic field, ontological categories (reflecting the more language-specific notion of part of speech), as well as additional metadata derived from norm datasets in psycholinguistics and natural language processing, including age-of-acquisition information for individual languages [START_REF] Kuperman | Age-of-acquisition ratings for 30,000 English words[END_REF], ontologies like WordNet (Princeton University, 2010), or word frequency counts, again for individual languages [START_REF] Brysbaert | Moving beyond Kucera and Francis: A critical evaluation of current word frequency norms and the introduction of a new and improved word frequency measure for American English[END_REF].

To illustrate how lexical comparative concepts are organized in the Concepticon, Figure 2 provides a small excerpt of the data which is linked to the concept set ( )³²³. As we can see from the figure, this concept set itself is narrower than the concept set ²⁵⁵¹, which shows that many languages do not explicitly distinguish oil from fat. On the other hand, the concept set is broader than ( )²⁰⁹⁵. The definition at the top of the figure indicates that the comparative concept should only be linked to those elicitation glosses which target the organic substance as opposed to potential non-organic variants. The five exemplary elicitation glosses in the table at the bottom of the figure are only a small excerpt of what can be found in the whole data linked by the Concepticon. According to the current version (Concepticon-1.1.0, [START_REF] List | Concepticon. A Resource for the linking of concept list[END_REF], the concept set ( ) recurs in 107 different questionnaires and surfaces in the form of 34 distinct elicitation glosses. As we can see from the five examples in the figure, elicitation glosses can vary drastically, not only because they may be given in different languages, but also because authors do not always pay much attention to consistency. Thus, Swadesh used two different glosses, fat (organic substance) in his list of 1952, and fat (grease) in his later list from 1955, but when inspecting other articles written by Swadesh, we can see that these were absolutely not the only two variants he used, and we find fat in [START_REF] Swadesh | Salish internal relationships[END_REF] and grease in Swadesh (1971).

Using, expanding, and improving Concepticon

We have created a simple automated mapping algorithm to quickly link new wordlists into Concepticon. After applying this algorithm, all links are manually checked to avoid embarrassing errors. In order to further facilitate the task of concept mapping, we wrote a small web-based standalone application which serves as a straightforward lookup tool, including a fuzzy search, across all 3042 concept sets which are currently defined and which can currently be used in seven languages (English, German, Chinese, French, Spanish, Russian, and Portuguese). This web-application, which can be used offline from common web browsers, is provided along with the supplementary material (SI:A) accompanying this paper (see below for further information on the supplementary material). It can also be accessed at http://calc.digling.org/

Concept Set FAT (ORGANIC SUBSTANCE)

Related concept sets

Esters of three fatty acid chains and the alcohol glycerol which form a semi-solid substance in room temperature and occur in animals and plants. Given the complexity of the lexical semantics of natural languages, it is obvious that resources like Concepticon or datasets that link to it will contain uncertainties, less-than-perfect links, and even straightforward errors.⁵ Concepticon is designed to be easily correctable and welcomes contributions and additions submit-⁵We recently found, for example, a link of German schaukeln 'rock (somebody or something)' to ²¹²⁵, reflecting a typical case of sloppy automatic linking that can usually only be avoided by manual refinement. ted in form of GitHub issues⁶ or email inquiries.⁷ Reference catalogs such as Concepticon are community efforts that can only be enhanced if the research community actively takes part in improving them and it is advantageous for our field if scholars help correct existing problems.

A new database of cross-linguistic colexifications

The first version of the CLICS database was based on four different sources which were publicly available at the time of publication and offered sufficient coverage in terms of comparative concepts. With more and more large questionnaires being linked to the Concepticon resource, it has become possible to easily harvest further data and add it to create an improved colexification dataset. With CLDF as a basic representation format that can be easily manipulated with help of the CLDF API written in the Python language (see Section 4.3), all that needs to be done is to assemble different datasets, convert them to CLDF by linking language varieties to Glottolog and elicitation glosses to Concepticon, and analyze them with the standard algorithms which were already present at the release of the CLICS database. Note that the fact that we list 498 distinct glosses for the Bai dataset but 499 Concepticon concept sets, is due to an ambiguity in the English gloss "old", which occurs two times in this dataset, one time referring to ( )²¹²², and another time to ( )²¹¹³. This information is available in the Chinese glosses, but not in the English ones.

Table 1 lists all datasets that were selected for the first version of our improved colexification database (http://clics.clld.org). All datasets are multilingual wordlists in the sense of List (2014, 23f). They are based on a collection of (elicitation) glosses that are translated into different language varieties. In our CLDF representation of the data, we have linked the elicitation glosses to Concepticon Concept sets, and the language varieties to Glottocodes. Since not all elicitation glosses could be successfully linked to Concepticon, the number of links to Concepticon and the number of original elicitation glosses in the respective datasets shown in the table often vary, showing fewer Concepticon links than elicitation glosses in the original data. The number of varieties and Glottolog entries also varies, but for different reasons, since it can happen that two or more varieties are linked to the same Glottocode, either because the varieties can be seen as identical but stemming from different datasets, or because the Glottocodes for the subvarieties of a given language or dialect are not yet available in the Glottolog project.

As can be easily seen, the data crucially improves upon the old database in terms of languages. The overlap in terms of concepts, however, is less promising, since many of the lists we assembled are in the range of 300 to 500 concepts. Since these sum up to 2488 different concept sets in total, while none of the original lists provides that many concepts, it is also clear that our new sample is considerably skewed, with only a few concepts recurring across all datasets. However, the framework we have implemented will enable us to rapidly increase the size of this database and improve the coverage via a series of "rolling releases". Furthermore, interested users can easily use our framework to analyze more balanced sub-samples of the data (for technical details, see Section 4.5) or even feed their own data into our framework.

General statistics

Our new database automatically derives colexifications for 1220 language varieties (of which 1029 are distinguished by Glottolog) and a total of 2488 distinct Concepticon concept sets. Based on a strict threshold that only accepts a given colexification if it occurs in at least three different language families (as defined by Glottolog),⁸ this results in a total of 2638 different colexification patterns, corresponding to 66140 individual instances of colexifications in the languages in our sample. Partitioning the colexification network with the help of the Infomap algorithm [START_REF] Rosvall | Maps of random walks on complex networks reveal community structure[END_REF] resulted in 248 different communities consisting of more than one concept.⁹ Given that some of the concepts in our data are never colexified (probably due to the sparseness of the data) our colexification network consists of 1534 different concepts. Table 2: The ten most frequently recurring colexifications encountered in our database.

In Table 2, we list the most frequently recurring colexifications in our database, sorted by the attestation per language family along with detailed counts on distinct languages and distinct words that attest the colexification. As can be seen from the table, the results are not particularly surprising. It is well-known that many languages use the same word for and or for and . That kinship terms are particularly heavily colexified clearly results from underspecification and does not reflect any potential instances of semantic shift. After manually inspecting the data to look for potential errors, we are quite confident that the unbalanced distribution of our data did not lead to any major errors, providing the same look and feel as the original CLICS database, while offering a drastically increased quantity of data.

The increase in data is also reflected when one inspects the geographic distribution of languages covered in our colexification database. As can be seen from the map in Figure 4, our colexification data has drastically reduced the number of empty areas, which were so characteristic of the original CLICS database. However, this does not mean that the data could not be further improved. We can still find many areas on the map, especially in Africa and North America, but also in the Pacific and South Asia, in which coverage is poor to non-existent. We hope to improve the geographical coverage in further releases.

⁸The threshold does not have any deeper scientific value. We selected it, since it resulted in communities of a reasonable size that guarantee a smooth look and feel when inspecting the network visualizations, not because we believe in any magic number that would provide us with true polysemies. Since we provide the software to create the networks and clusters along with the data, interested users can test different thresholds and parameter settings for the same data. ⁹In contrast to the earlier version of CLICS, we no longer follow [START_REF] Dellert | Lifting a large multilingual dictionary to the level of concepts[END_REF] in normalizing the edge weights with respect to the frequency by which concepts are reflected across all languages, since we found that the granularity of the communities produced when taking the number of language families as weight is sufficient for our purposes of displaying the data in interesting chunks.

Exploring colexifications through web-based applications

Our application (hosted at http://clics.clld.org) allows users to explore the data from various additional perspectives, including geographic maps, the inspection of the data of individual languages, or the distribution of concepts for which we find translations in our data. In addition, each data point can be traced back to its original source, allowing the users to rigorously check whether the automatic findings we present can be confirmed through qualitative research. In order to illustrate the new application, a number of examples follow.

Bird's eye view of the colexification data

Before going into details, a bird's eye view of the data is given in Figure 5. While we can see that most of the nodes in our graph form a large connected component, we can also see that the community detection algorithm singles out communities, adding structure which would otherwise be difficult to spot.

Colexifications of , , and

Of the 248 communities containing at least two concepts in the data, the largest community consists of more than 20 nodes, centering around the concept ¹⁶²³, which has the largest number of links in this subgraph (see Figure 5 regarding the position of the network in our big graph). The detailed network is shown in Figure 6. This subgraph also contains the link between ¹³⁰⁷ and ¹⁵⁹⁹, ranking at position nine in the collection of most frequently recurring links shown in Table 2 Concepts which could equally well be assigned to different communities are quite common in crosslinguistic colexification data. While this may result from using an inappropriate algorithm for community detection that partitions the network into too small sets of nodes, it also reflects the general indeterminacy of concepts which can often be assigned to different domains. According to our automatic analysis, for example, ¹⁴⁵⁸ plays a role in four different semantic domains, which could be labeled as neutral speech (the community shown in Figure 6), concrete action (community around ), (community ), and articulated speech (community around ). Unfortunately, our data is not tagged for semantic fields or semantic domains. If it were, we could automatically derive those concepts which are in transitional areas and not easy to assign to only one domain. Much more work will have to be done in the future, both on existing resources such as the Concepticon, and on datasets in CLDF format, as well as our colexification database, in order to exhaust its full potential.

Colexifications of and

As a further example, let us consider a case of regional colexification that was already mentioned by [START_REF] Mayer | An interactive visualization of cross-linguistic colexification patterns. In Visualization as added value in the development, use and evaluation of linguistic resources[END_REF] and can also be found in our new colexication database: the colexification of ¹³⁰¹ and ⁷¹⁰ in some South-American languages. In contrast to the example of , , and in the preceding section, this colexification does not reflect a global pattern which could be identified when looking into the partitions based on the Infomap community detection analysis, which places and into distinct communities. An additional view of the colexification data, introduced by [START_REF] Mayer | An interactive visualization of cross-linguistic colexification patterns. In Visualization as added value in the development, use and evaluation of linguistic resources[END_REF], however, allows one to find areal patterns, provided they are frequent enough and recur across different language families. This view (called subgraph by [START_REF] Mayer | An interactive visualization of cross-linguistic colexification patterns. In Visualization as added value in the development, use and evaluation of linguistic resources[END_REF] presents the subgraph derived from the closest neighbors of a given query concept. Neighbors of the starting concept are identified by setting a frequency threshold. In consecutive steps, more nodes (the neighbors of the neighbors) can be added to the subgraph, depending on the size of the network, which should not exceed a certain number of nodes to allow for convenient inspection.

Thus, while the colexification between and does not show up in our community analysis, we find it in the subgraph view, as shown in Figure 7. As we can see from the different concrete word forms reflecting the colexification, we are not dealing with a direct borrowing that spread among the languages. Instead, the colexification either reflects an instance of loan transfer (in the terminology of [START_REF] Weinreich | Languages in contact[END_REF] or an indirect metaphorical extension. What may substantiate the latter hypothesis is the fact that the colexification is not restricted to Southern America, but seems to be also reflected in some African languages located on the Eastern coast of Africa [START_REF] Gilman | African areal characteristics: Sprachbund, not substrate?[END_REF][START_REF] Heine | An areal view of Africa[END_REF], but our current version of CLICS² does not contain data on these particular languages. The explanation for this particular colexification can thus be sought in historical factors, as a metaphorical extension linked to the introduction of the wheel as a widespread technology in a colonial context. This again has immediate implications for ongoing debates on linguistic paleography. First, the metaphor shows that concrete historical events may be reflected in languages. Second, however, it also shows that we need to be very careful when evaluating this evidence. As we can see from the subgraph in Figure 7, there are plenty of colexifications for ¹⁴⁶⁷ and in our data as well (our data counts 26 concrete colexifications across 11 different language families). Assuming that societies usually have a way to express the concept 'circle', while 'wheel' may be missing, our data suggests that the most straightforward strategy to express a new concept 'wheel' starts from the word for 'circle'. Since this can easily happen independently, as we can again see from our data, these findings might be of importance for on-going debates on the origin of terms for 'wheel', especially in Indo-European [START_REF] Hock | Indo-European linguistics meets Micronesian and Sunda-Sulawesi[END_REF][START_REF] Anthony | The Indo-European homeland from linguistic and Archaeological perspectives[END_REF]. Further studies on lexical typology, including studies on independently recurring patterns of semantic shift as well as the frequency of loan transfer, are required before this linguistic data can be reliably used to reconstruct ancestral cultures. Our extended colexification data may serve as a starting point for these investigations.

Technical background

This section provides interested readers with technical details regarding our improved database of crosslinguistic colexifications. More information can also be found in the supplementary material submitted with this study.

Shortcomings of the previous version of CLICS

The original CLICS database by [START_REF] List | Sequence comparison in historical linguistics[END_REF] was compiled in a mostly automatic manner. The data were assembled from four different sources (Key and Comrie, 2007;Group, 2008;Haspelmath and Tadmor, 2009;[START_REF] Borin | The Intercontinental Dictionary Series -a rich and principled database for language comparison[END_REF] and were mostly already linked to the same set of comparative concepts, originally based on [START_REF] Buck | A dictionary of selected synonyms in the principal Indo-European languages. A contribution to the history of ideas[END_REF]. The lexical entries were automatically cleaned, using regular expressions and similar standard techniques for text manipulation, and then compared for colexifications. The resulting network was analyzed with help of the Infomap algorithm for community detection [START_REF] Rosvall | Maps of random walks on complex networks reveal community structure[END_REF] in order to decrease the complexity, single out colexifications that point to instances of homophony, and split the semantic network into a meaningful set of subgraphs, representing areas of high semantic affinity, close to the notion of semantic fields [START_REF] Anttila | Field theory of meaning and semantic change[END_REF].

Since then CLICS has enjoyed considerable popularity among scholars working in the field of lexical typology. On the one hand, this is reflected in studies that mention the database in a favorable manner [START_REF] Östling | Studying colexification through massively parallel corpora[END_REF][START_REF] Georgakopoulos | The semantic map model: State of the art and future avenues for linguistic research[END_REF][START_REF] Šipka | Lexical conflict. Theory and practice[END_REF], as an inspiration source for similar or enhanced analyses [START_REF] Söderqvist | Colexification and semantic change in colour terms in Sino-Tibetan and Indo-European languages[END_REF][START_REF] Brochhagen | Improving coordination on novel meaning through context and semantic structure[END_REF][START_REF] Dellert | Using causal inference to detect directional tendencies in semantic evolution[END_REF][START_REF] Pericliev | On colexification among basic vocabulary[END_REF][START_REF] Gast | The areal factor in lexical typology: Some evidence from lexical databases[END_REF], or as a potential dataset for additional studies [START_REF] Youn | On the universal structure of human lexical semantics[END_REF]. On the other hand, it is reflected in a couple of studies that make direct use of the data provided in CLICS [START_REF] Schapper | Tree, firewood and fire in the languages of Sahul[END_REF][START_REF] Koptjevskaja-Tamm | Semantic patterns from an areal perspective[END_REF][START_REF] Staffanson | Mitt hjärta är bittert. En lexikal typologisk studie om smaktermer[END_REF][START_REF] Regier | Languages support efficient communication about the environment: Words for snow revisited[END_REF]. It seems that the general strategy of using an interactive interface that allows scholars to explore the actual data, offering both a bird's eye view on colexification patterns while keeping in touch directly with the original data fulfils a certain need for studies on lexical typology, serving as an example for computer-assisted as opposed to purely computer-based frameworks [START_REF] List | Computer-Assisted Language Comparison: Reconciling computational and classical approaches in historical linguistics[END_REF].

As mentioned, the earlier CLICS database suffered from a number of shortcomings. Not only was the coverage in terms of languages rather small, with a sample of only 220 languages heavily biased towards Southern America and North Eurasia (Östling, 2016), but the data was also not easy to expand, as new word lists would have demanded a considerable amount of overlap with the 1280 comparative concepts in CLICS. A factor further complicating the expansion of the existing CLICS database was the difficulty in its curation. Given that the data came from independent sources, and that the small number of developers did not have the linguistic expertise to check all wordlists systematically, it was impossible to correct errors in the data itself. Although such curation would have also gone against the original policy of the database, insofar as it was originally built on the idea of providing a different view of already curated datasets, it constituted a serious problem for further development. An additional problem was the transparency of the algorithms underlying CLICS: while the source code was online and freely available, it was difficult to use in its previous state, as it was largely undocumented and provided an unfortunate mix of code written for data deployment and code written for data analysis.

Software implementation

While the original CLICS framework was deployed via PHP, we have integrated the original code for data visualization [START_REF] Mayer | An interactive visualization of cross-linguistic colexification patterns. In Visualization as added value in the development, use and evaluation of linguistic resources[END_REF] into a Python-based CLLD application [START_REF] Forkel | CLLD: A toolkit for cross-linguistic databases[END_REF]. CLLD offers not only more granular access to the data, but also provides the look-and-feel of well-known typological databases like the Atlas of Pidgin and Creole Language Structures [START_REF] Michaelis | The Atlas of Pidign and Creole language structures online[END_REF] or the World Atlas of Language Structures (Dryer and Haspelmath, 2013). The new framework allows users to inspect the inferred colexifications online via the CLLD framework, and also allows them to curate their own colexification datasets, to analyze, inspect, and even deploy them, thanks to a standalone application which they can use to convert their own colexification data to an interactive visualization very similar to the look and feel of the original CLICS database.

The new database of cross-linguistic colexifications comes along with a simple interface to compute the colexifications and network statistics. To identify and plot colexifications, we follow the strategy employed by [START_REF] Mayer | An interactive visualization of cross-linguistic colexification patterns. In Visualization as added value in the development, use and evaluation of linguistic resources[END_REF], but have significantly refactored the code, leading to a drastic increase of speed when searching for colexifications. In contrast to the regular expressions by which the data was automatically cleaned in the original CLICS framework, we have decided to use an even more rigorous approach by stripping off all metalinguistic information that can often be found in linguistic datasets (morpheme boundary markers, brackets for scholars' comments or to indicate pronunciation alternatives) and representing all lexical entries internally with help of ASCII letters. While this carries the danger of introducing errors, our tests indicate that most of these problems can be singled out by only considering colexifications with a frequency above a certain average. Furthermore, since we show the original values as they appear in the data to the users, scholars wishing to work with the data in concrete form can easily check with the original entry or even go back to the original sources of each colexification that we identify with our automated procedure.

We provide platform-independent versions of the Python code which can be used on a Mac, Windows, or Linux computers running either Python 2 or 3. The package provides useful command line tools which we describe in detail at the projects GitHub page at https://github.com/clics/clics2. The software package providing the colexification API is further hosted with Zenodo (see https://doi. org/10.5281/zenodo.1299093 for the most recent version), as well as the 15 datasets (see https: //zenodo.org/communities/clics/).

In addition to the CLLD application that provides the data online, we also provide code that exports colexification data to a standalone application, purely based on JavaScript, which can be used locally (and offline) in a web browser, or shared online using a static web server.¹¹ We assume that this service may turn out to be useful especially for users who want to run their own datasets through our framework, but don't have the technical means or expertise to set up a complex CLLD application. The new CLICS² software package also offers information how the standalone application can be computed.

Cross-Linguistic Data Formats

In order to increase the comparability of cross-linguistic data and to ease the curation and reuse of existing datasets, we follow the standards and recommendations of the Cross Linguistic Data Framework (CLDF). CLDF is a standard to capture different data types often encountered in cross-linguistic research, such as wordlists, typological features, parallel texts, and dictionaries [START_REF] Forkel | Cross-Linguistic Data Formats (CLDF)[END_REF]. The major features of the CLDF specification are: (A) a simple text format for data-storage, based on CSV (comma-separated values), extended by recent recommendations by the World Wide Web Consortium, allowing metadata to ¹¹In offline form, only Mozilla Firefox is supported at the moment, but when the data is put on a web server, it can be used from any browser.

be incorporated and data to be linked across multiple CSV files [START_REF] Pollock | Metadata vocabulary for tabular data[END_REF][START_REF] Tennison | Model for tabular data and metadata on the web[END_REF], (B) a flexible software API which allows validation of whether a given dataset conforms to the specifications, (C) an ontology which allows frequently recurring objects and properties in comparative linguistics to be recognized, and (D) the rigorous integration of reference catalogs in order to increase the comparability of data across datasets.

Cross-Linguistic reference catalogs

CLDF strongly encourages the usage of reference catalogs, such as Glottolog or Concepticon, when preparing linguistic data. The advantage of organizing language varieties not only by their common name, but also by adding the identifiers offered by Glottolog are obvious. Since Glottolog harvests various types of information regarding language varieties all over the world, ranging from geographical coordinates via references in the literature up to genealogical classifications, scholars linking the languages in their data to Glottolog identifiers can automatically dispose of this information when carrying out additional studies. Disadvantages may result from incorrect links to Glottolog or from problems that experts may encounter when checking the information provided by Glottolog. If, for example, scholars do not agree with the genealogical classification provided by Glottolog, they may prefer to add their own classification to their dataset. However, even if specific information turns out to be erroneous or not satisfying enough for scholars to help in their application, it is still useful to try to provide a link to Glottolog, as it will make it much easier for other scholars to find their data. Furthermore, Glottolog is curated in public and changes can be proposed and made in a transparent manner in the form of GitHub issues¹² or by contacting the editors via email.

As outlined in Section 2, these advantages also hold for the usage of Concepticon as a reference catalog for comparative concepts. While scholars may still use and embrace their individual questionnaires with their preferred elicitation glosses and concept definitions, linking them to Concepticon guarantees that their data is cross-linguistically comparable and easily accessible to other researchers as well.

Choosing a representative sample using Average Mutual Coverage

A crucial issue when assembling different datasets in the way this is done in our updated version of the CLICS database is whether the overlap in terms of comparative concepts across datasets is sufficient and representative enough. While the data aggregated from the 15 different datasets should be interesting enough for manual inspection and analysis, some analysis strategies (for example those based on hypothesis testing, as mentioned by Roberts 2018) will require balanced and representative samples.

A seemingly straightforward way to identify a representative sample would be to determine the subset that provides the optimal overlap in terms of languages and concepts. In order to get a better idea of how skewed the data in our updated version of CLICS actually is, we carried out a detailed investigation of the different subsets of the data, employing the concept of average mutual coverage (AMC) in multilingual wordlists, as provided in the most recent version of the LingPy software package (List et al., 2017, Version 2.6).

Here, the AMC of a given wordlist is defined as the average of the number of concepts shared between all pairs of languages in a given wordlist divided by the number of concepts in total. Assuming we have a concept list of 100 concepts and three different languages A, B, and C, which have translations for 90, 70, and 60 concepts each, we can determine the average mutual coverage by first checking the individual overlap among the languages (which is not necessarily equal to the number of the concepts translated in the "smaller" of two varieties), and then divide these numbers by the total amount of concepts. If we assume a mutual coverage of 65 between A and B, of 55 between A and C, and 45 between B and C, we can sum up ¹²See https://github.com/clld/glottolog/ for details. and average the mutual coverage between all pairs. In this example, this would result in an AMC score of 0.55 ( 0.65+0.55+0.45 3 ).¹³ Therefore, if users want a representative sample, they can make use of our AMC statistics, which are provided along with the source code to compute them in the supplementary material, to extract their sample of choice of the datasets we provide in full (SI:B). We can use this metric to evaluate how well-balanced a given selection of languages and concepts is. This can be done by dividing the data into different subsets in which concepts and languages are consecutively deleted from the data, using their average size (number of concepts, or number of languages which provide a translation for a concept) as a criterion. We can then compute the average mutual coverage for each of these subsets and plot the data in order to see how the AMC scores change when reducing the number of languages and concepts in the data.

We carried out this analysis both for our new collection of datasets in CLDF format and the data underlying the original CLICS database. The results can be seen in Figure 8. As can be seen from these plots, our new data collection is heavily unbalanced, with extremely low mutual coverage scores for samples of a large number of concepts and languages. Comparing our data with the AMC statistics for different subsets of the original CLICS database, however, we can also see that our data supersedes the original CLICS coverage for a subset of about 1200 concepts and about 300 languages.

Concluding Remarks

Our new colexification database provides a powerful new tool for investigating colexification patterns on both global and regional scales. Thanks to a substantial increase in the data used to identify the patterns, the inference of colexifications is far more robust than before. The new framework based on the CLDF specification and intensive use of reference catalogs has dramatically increased the transparency and replicability of analyses -and our stated policy towards open data and a regular floating release scheme will extend and grow the database further in the future. Our framework can easily be extended following our collaboration guidelines, or co-opted for analysis of alternative datasets as necessary. We see our framework as a central tool for future work in lexical typology.

¹³Since we use 100 concepts as an example, the mutual coverage for each language pair is simply divided by 100.

Figure 1 :

 1 Figure 1: Examples for hypothetical cross-linguistic polysemy networks. A shows an unweighted graph. B shows a hypergraph, C represents a network with weighted edges (edge-width representing relative weight), and D shows a network with weighted edges and weighted nodes (node size representing relative node weight).

Figure 2 :

 2 Figure 2: Example for the representation of data in the Concepticon project. Note that the three different separators in the elicitation glosses for fat/grease are given as such in the data, thus reflecting the high degree of inconsistency we find in linguistic practice.

Figure 3 :

 3 Figure 3: Example for the web-based lookup tool for Concepticon mapping.

Figure 4 :

 4 Figure 4: The current coverage of our colexification database in terms of language varieties. Colours indicate the major genetic subgroupings of the languages, following the Glottolog classification.

Figure 5 :

 5 FIGHT

Figure 6 :

 6 Figure 6: The largest community in our sample, with the concept ¹⁴⁵⁸ showing most connections to the other concepts.

  around

Figure 7 :

 7 Figure 7: Detecting regional colexification patterns with help of the subgraph explorer. The colors for the languages in the top-left table indicate their genetic relationship. As can be seen, all languages belong to different language families (with three of them being isolates), although they are geographically close.

Figure 8 :

 8 Figure 8: Average mutual coverage in A CLICS, and B our new colexification database. The legend shows the number of concepts for which the AMC has been calculated.

Table 1 :

 1 Overview of datasets converted to CLDF for the new database of cross-linguistic colexifications.

	#	Dataset	Source	Range	Glosses Concepticon Varieties Glottocodes Families
	1	allenbai	Allen (2007)	Bai (ST)	498	499	9	3	1
	2	bantubvd	Greenhill and Gray (2015)	Bantu	430	415	10	10	1
	3	beidasinitic	Běijīng Dàxué (1964)	Sinitic (ST)	905	700	18	18	1
	4	bowernpny	Bowern and Atkinson (2011)	Pama-Nyungan 348	338	170	168	1
	5	hubercolumbian	Huber and Reed (1992)	Colombian	374	343	69	65	16
	6	ids	Key and Comrie (2016)	World-wide	1310	1305	321	276	60
	7	kraftchadic	Kraft (1981)	Chadic	434	428	67	60	3
	8	northeuralex	Dellert and Jäger (2017)	North-Eurasian 1016	940	107	107	21
	9	robinsonap	Robinson and Holton (2012)	Alor-Pantar	398	393	13	13	1
	10 satterthwaitetb	Satterthwaite-Phillips (2011)	Sino-Tibetan	423	418	18	18	1
	11 suntb	Sūn (1991)	Sino-Tibetan	1004	905	48	48	1
	12 tls	Nurse and Phillipson (1975)	Tanzanian	1589	808	120	97	1
	13 tryonsolomon	Tryon and Hackmann (1983)	Solomon Islands 324	311	111	96	5
	14 wold	Haspelmath and Tadmor (2009) World-wide	1460	1457	41	41	24
	15 zgraggenmadang	Z'graggen (1980abcd)	Madang	380	306	98	98	1
		TOTAL / Overlap				2487	1220	1028	90

⁶See https://github.com/clld/concepticon-data/issues for details. ⁷By sending an email to concepticon@shh.mpg.de.

Acknowledgments

We thank three anonymous reviewers for challenging and constructive advice. We are grateful to Martin Haspelmath, who brought up the idea to submit this paper to Linguistic Typology and always supported our data-driven approach to lexical typology. We thank Russell Gray for encouraging us to pursue our datadriven perspective on historical linguistics and language typology. We also thank Stéphane Polis, Thanasis Georgakopoulos, and Anne-Maria Fehn for helpful comments on earlier versions of this paper. Last but not least, we would like to express our gratitude to all scholars who made their data publicly available, and specifically to Peter Bouda, Claire Bowern, Johannes Dellert, Michael Cysouw, Gerhard Jäger, Harald Hammarström, Jelena Prokić, Damian Satterthwaite-Phillips, and Malcom Ross for their help in rendering their data in our formats.

Funding Information

This research would not have been possible without the generous support by many institutes and funding agencies. As part of the CLLD project (http://clld.org) and the GlottoBank project (http://glottobank.org), the work was supported by the Max Planck Society, the Max Planck Institute for the Science of Human History, and the Royal Society of New Zealand (Marsden Fund grant 13-UOA-121, RF, JML, and SJG). JML was funded by the DFG research fellowship grant 261553824 Vertical and lateral aspects of Chinese dialect history (2015)(2016). JML and TT were funded by the the ERC Starting Grant 715618 Computer-Assisted Language Comparison (http://calc.digling.org). SJG was supported by the Australian Research Council's Discovery Projects funding scheme (project number DE 120101954) and the ARC Center of Excellence for the Dynamics of Language grant (CE140100041).

Supplementary Material

The supplementary material accompanying this paper contains:

• SI:A The Concepticon lookup tool, which runs offline in the major browsers (also accessible via http://calc.digling.org/concepticon/).

• SI:B Information on how to derive Average Mutual Coverage Statistics from a given dataset.

Author Contributions

JML wrote the first draft. SJG, CA, and TT revised the first draft. JML and RF wrote the Python code for the application. RF wrote the code for the CLLD application. TM wrote the visualization routines in the standalone and the CLLD application. TT, SJG, JML, and RF provided datasets in CLDF format. All authors revised the last draft and agree with its final version.


Joris Rehm
email: joris.rehm@loria.fr

Dominique Cansell
email: cansell@loria.fr

Proved Development of the Real-Time Properties of the IEEE 1394 Root Contention Protocol with the Event B Method

We present a model of the IEEE 1394 Root Contention Protocol with a proof of Safety. This model has real-time properties which are expressed in the language of the event B method: first-order classical logic and set theory. Verification is done by proof using the event B method and its prover, we also have a way to model-check models. Refinement is used to describe the studied system at different levels of abstraction: first without time to fix the scheduling of events abstracly, and then with more and more time constraints.

Introduction

In this paper, we present a model of the IEEE 1394 Root Contention Protocol with a proof of safety and of real-time properties. We already described the pattern of our model of time, applied in a simple case study, in [START_REF] Cansell | Time constraint patterns for event B development[END_REF] as a pattern of refinement for the event B method. We show here how this pattern works over a proven development of the IEEE case study. Many different models for real-time already exist. Our goal is to find a model of time adapted to make proof by invariant with refinement over systems of events. We also argue that is better to start a proven development by an abstract model without time and to use refinement to add real-time properties. Therefore our model of time must allow us to use refinement.

The IEEE 1394, also known as FireWire, is used to connect devices like external hard-disks or movie cameras. Devices are able to configure themselves by the IEEE 1394 leader election protocol. This protocol takes the network as an acyclic graph and orients edges to obtain a spanning tree rooted by a leader. This general case is already done with the event B method in [START_REF] Abrial | A mechanically proved and incremental development of IEEE 1394 tree identify protocol[END_REF]. This work extends this result to the following case: at the end of the algorithm, or when only two devices are connected, the general algorithm can fail. In this case the signals can cross in the bi-directional channel between the two devices if they send signals at almost the same send time. Consequently the IEEE 1394 Root Contention Protocol takes place in order to choose a leader between the two devices. The algorithm is probabilistic and uses a random choice between a short and a long waiting time. This sleeping time and signal sending between devices leads to a (probable) election. We can see this illustrated in Fig. 3 on page 9. We do not take into account probabilistic properties (we replace them by non-determinism) nor the loss of signals. To model this system we need to quantify the two different sleeping times and the progression of signals over the channels. We want to prove safety properties on this algorithm and we want to be compatible with the existing B model [START_REF] Abrial | A mechanically proved and incremental development of IEEE 1394 tree identify protocol[END_REF]) in the general case. Furthermore, we want to use the language and tools of B without modifications.

The language of the B method is based on the first order classical logic with set theory. This method can be used to specifying, designing and coding software systems. B models of system are accompanied by mathematical proofs. Proofs validate an invariant over the events of the system and validate the refinement relation between models. The goal of the refinement is to connect an abstract specification to a more concrete model. And step by step we can reach a precise model of the implementation. A description of the event B method can be found in [START_REF] Cansell | Foundations of the b method[END_REF] or a shorter introduction is present in the section 2 of [START_REF] Abrial | A mechanically proved and incremental development of IEEE 1394 tree identify protocol[END_REF]. Of course, in this paper, every formal descriptions are followed by textual explanations.

The language of the B method does not contain specific real-time or distributed features but we can model them. The idea is to guard events with a time constraint like a timeout or an alarm. We say that events are linked to an "activation time" (AT). We have several sets of AT, one for each constraint timed event which corresponds to encoding a multiset of ATs.

To represent the real-time progression we use a global clock represented by the variable time. Our time is discrete so time ∈ N, but we can use unknown constants or logical expressions between different times. The time progression is expressed by an event called tick_tock.

No events except tick_tock make the time progress therefore several events can trigger in the same clock granule. This event nondeterministicly increases the variable time between time + 1 and the first activation time (if any). So we have in invariant: (at = ∅ ⇒ time ≤ min(at)) where the variable at is the union of all different AT sets. As time is a natural number we are sure that the system will reach the next active time if tick_tock is activated often enough. Finally, when time reaches an AT value we have time ∈ at; in other words, time = min(at). Therefore the event linked to this AT can trigger, do its work and remove the reached AT from its AT set. After this suppression, time is free to reach the next AT, or simply increase if at = ∅.

This paper is organised as follows. In Section 2, 3, 4 and 5 we show the model of the casestudy. We follow the methodology of refinement and we introduce respectively: the goal of the system, the details of the system without time, the real-time properties of the signals passing and the real-time properties of the sleeping times. In Section 6, we show the verification of the model. Finally in Section 7, we show related-work and we conclude.

First Model

This first model is the most abstract specification of our system. The general behaviour is to choose (elect) one device in the set N = {a, b}. The only variable leader is a subset of N and contains the chosen device (if not empty). Apart from this, the invariant states that the set leader is {a} or {b} or ∅.

Finally the transitions of this abstract system are given by the event accept in Fig. 1. This event occurs when the set leader is empty and fills it with a device. All of the following models in the paper will refine this behaviour.

First Refinement

We now introduce, through refinement, the local state of devices and two communication channels between device a and b. Almost all behaviour of the system can already be expressed abstractly at this level of abstraction. Communication will be asynchronous. In other words a signal from a to b can cross a signal from b to a. So the system can progress in two ways: if only one signal is sent, a leader will be elected; if two signals cross, a situation called "contention" will appear. In this situation the election is impossible, so the two devices will remove their signals. After a contention the devices wait for a random length of time before retrying the election process. We note that real-time properties will be added later and that model is a specification for the future real-time properties. For example, we will add a precise propagation time for the signal progress in a channel.

Devices communicate with two SIGN ALS: IDL and P N . IDL is a blank signal. P N (for Parent Notify) means that the sender does not want to be the leader. We have four different ST AT ES for the two devices a and b, devices are in the state: reset when they start; sending when they are sending the signal P N ; sleeping when they wait after a contention; and accepting when they accept to be the leader. In the refinement, the variable leader disappears through data refinement and we add nine new variables: variables a_state and b_state for devices and three variables for each channels a_in, ab, b_out and b_in, ba, a_out. (The names of variables are chosen with the intuition that the signal go into the channel, not outside the devices). We need three variables for a channel because we want asynchronous communication and we can have a maximum of two changes of signals at the same time. The three variables of a channel act in a "first in first out" way and we have an event to make the values progress inside the channel from the input to the output. Finally, the variable case does not take place in the behaviour of the system but is used to denote a special case in the invariant. We can see a graphical representation in fig. 2, which shows the very first sending of the signal P N .

Invariant

The first point to specify in an invariant is the type of the new variables: all variables of the channels are members of the set SIGN ALS; Variables a_state and b_state are in ST AT ES; and case is a boolean.

In this refinement the variable leader is not required anymore because we can deduce the leader of the election from the state of the devices. So we can replace the abstract variable leader by the concrete variables a_state and b_state. We call this a "data refinement". For this we need a "gluing invariant" that relates the value of the abstract variable with the value of the concrete variables. Here we want (leader = {a} ⇔ a_state = accepting) and the same thing for b. We also know that if the P N signal is present in both channels then leader = ∅. Furthermore, if one device is accepting then the other is sending (the signal P N ) and all signals have been received. (For device a:

leader = {a} ⇒ a_state = accepting ∧ b_state = sending ∧ ab = IDL ∧ b_out = IDL ∧ ba = PN ∧ a_out = PN.)
This part of the invariant is the most important, but there are more things to express. First of all, in the initial state of the system devices are reset. With that condition all variables of the channel from this device are equal to IDL, for device a: a_state = reset ⇒ (a_in = IDL ∧ b_out = IDL ∧ ab = IDL). When a device, for instance a, is sending then the beginning of the channel is set to P N , for instance a_in = P N . We have the equivalence: (a_state = sending ⇔ a_in = P N ). We are also sure that if a device is reset and this device receives the P N signal then the other must be sending. In this case, the receiving device can safely accept to be the leader. Consider the case where the receiving device is also in the state sending: the election is now impossible and we are in a situation of "contention". The device discovers this situation and sets its state to sleeping. In this state we have for device a: a_in = IDL and b_state ∈ {sending, sleeping} (and the symmetric case for b: b_state = sleeping ⇒ b_in = IDL ∧ b_state ∈ {sending, sleeping}). So the signal P N will be erased by IDL. After this, each device will go back to the sending state and the previous part of the invariant is used to describe the state. The level of modelling is quite abstract and we will see in the final refinement many more (real-time) statements over states, especially in the situation of contention.

Finally the case boolean variable is true if and only if: one of devices is sending and the other is sleeping: case = TRUE ⇒ (a_state = sending ∧ b_state = sleeping) ∨ (b_state = sending ∧ a_state = sleeping); and the device currently sending was previously in the state sleeping: property ensure by the events.

The variable case expresses this with relations between values of case and values of other variables. This is the key to the algorithm because when a device goes back to the state sending after sleeping, it can elect a leader if the duration of this case is long enough. We will see the utility of case in the last refinement. In other words, if the second device awakes a long time after the first: then the first device has enough time to send their signal. Otherwise, the contention reappears.

Events

Events give properties over the transitions of the system. Here we have four kinds of events: send, pass, accept and sleep. From now on we will describe the model only from the point of view of the device a. As the system is totally symmetrical between devices a and b, the reader can easily fill in the blanks. As written with the keyword "REFINES", four events refine the abstract event accept.

The guard of the event a_send express that a has never sent anything and is not receiving a signal. With this condition we send a signal to the device b. The substitution: ab := P N comes with a simplification in the use of the channel.

The ab_pass event shows how a signal progresses in the channel from a to b. We know that (a_in = ab ⇒ ab = b_out). Therefore when there is at least one change of signal in the channel we know that ab = b_out. Then we advance values from a_in to ab and from ab to b_out. However, when there are changes of signals in both channels we can make the values pass in both channels at the same time. This is done by the event pass_out. Without this event, in this abstract model, one channel can take priority over the other, for example with several activations of ab_pass_out without activations of ba_pass_out. This is not realistic behaviour, but in model with real-time properties this problem is solved. In the last line of the guard of ab_pass_out we can see an expression of the priority of the event b_sleep. To express priority, we take the guard (or a crucial part of the guard) of the event with the higher priority and put its negation in the guard of the event with the lower priority. A part of the guard is crucial if it negation is enought to prevent the execution of the event in any case. Hence both events can not trigger in the same state. Without this priority the system could execute the sequence: a_send, b_send, pass_out, a_sleep, ab_pass, a_accept. However, such a sequence is not allowed by the standard as a device has to have discovered the contention situation. In this sequence the device b failed to discover it (i.e. to execute b_sleep). In this refinement the problem is solved abstractly and in later models we will use real-time constraints.

The event a_accept triggers when the situation of contention never occurred (impossible when a state is still reset) and a device receives a signal P N .

In contrast, a device can discover a situation of contention when it is sending and it has received a signal P N . In this case it goes to sleep and starts to remove its signal P N . This is the only state where we can have two changes of signal in the same channel. It's achieved when we already have ab = b_out. Therefore the new state of the channel will be (a_in = IDL ∧ ab = P N ∧ b_out = IDL).

Finally, there are two events left: a_awake_send and a_awake_accept. They contain the same behaviour as a_send and a_accept plus the management of the variable case and some extra conditions.

In addition to the guard of a_send, the event a_awake_send must check that the previous signal P N of device a is erased from the channel from a to b. This can be seen in the last two lines of the guard of a_awake_send.

In addition to the guard of a_accept, the event a_awake_accept must check that the signal is erased in the same way. It has also to check if the device b is actually in the sending state. Otherwise one device would accept to be the leader with the other device in state sleeping because a_out = P N does not imply that b_state = sending; and it would lead to an incorrect election situation.

In conclusion, this model is enough to express all behaviours abstractly and now we can introduce the real-time.

Second Refinement

In this second refinement, we add a precise propagation time for the propagation of a signal inside a channel. This constant, called prop, is in N and is not equal to zero. This model contains three new variables: time, at_a_pass and at_b_pass. The variable time is a global clock, the value of time represents "now" the current time. The algorithm itself does not require a global clock or a synchronisation between devices. But in the B method we need closed systems, i.e. we need to model the environment. The two other variables are two sets of "Activation Time" (AT) i.e. a set of timeouts or alarms. Each AT set is linked to some particular event. Here the set at_a_pass (respectively at_b_pass ) is linked to ab_pass_out (ba_pass_out). Therefore, they are both linked to pass_out. The meaning is: the AT set contains the time in the future when the linked event will be triggered. Of course, other events can fill the AT set of another event. In a very natural way, we let the time progress in a nondeterministic way betwen time + 1 and the first AT. If there is no AT then time progression is not limited. When time reaches an activation time, the linked event can be triggered and we remove the AT from the set in the related event. With this model, we are sure that time is progressing, and every time constraint events linked to a AT set will also be triggered at the right moment. This model of time has already been described in our article [START_REF] Cansell | Time constraint patterns for event B development[END_REF].

Invariant

The typing of the new variables are (time ∈ N) and (at_a_pass ⊆ N) and (at_b_pass ⊆ N). As the system is symmetrical we only show invariants concerning the device a. The time can not go beyond an activation time, as we don't want to miss the timeout of an event:

at_a_pass ∪ at_b_pass = ∅ ⇒ time ≤ min(at_a_pass ∪ at_b_pass) As at_a_pass represents the time of the reception of a signal, and signals take the propagation time prop to progress in the channel, then this AT set is bound by time + prop: ∀x•(x ∈ at_a_pass ⇒ x ≤ time + prop) The set at_a_pass is finite and its cardinality reflects the number of signal changes travelling in the channel. In the computer model we use a formula with quantification instead of a cardinality because it is more convenient for the interactive proof.

Events

In this refinement we have a new event tick_tock. This event makes the time progress. In almost all guards, we add an extra clause to model the priority between events. The main reason for the use of priorities is the fact that the environment must act before the devices react.

Here, the environment is the three pass events, so we add time / ∈ (at_a_pass ∪ at_b_pass) in guards to let pass events trigger before the other. Of course, between the three pass events, the simultaneous passing event pass_out has higher priority. Finally, the real-time constraints model the propagation time of signals. In the next description of events, we show only the differences between events of the previous refinement. For that we mark new lines with a ⊕ and removed lines with a ⊖. All new lines of guards are connected with "∧" and lines of substitution with " ".

Third Refinement

This final refinement removes all abstract conditions in the guards and adds the two different sleep times. As we have already explained devices try to go out of the situation of contention by waiting a random time between a short and a long time. So we have two new constants st (short time) and lt (long time) both in N and non-zero. Their values have the two following properties: st ≥ prop × 2 and lt ≥ prop × 2 + st -1. Properties are chosen in order to leave enough time for the devices to react. The whole invariant of this paper is a proof of that. In this refinement we have four new variables: at_a_awake, at_b_awake, a_sleept, b_sleept. Variables a_sleept and b_sleept contain the chosen sleep time. We can see in the Fig. 3 a timeline showing a typical situation of contention with values prop = 3, st = 6 and lt = 11. The election will succeed if devices chose two different delays between st and lt. In that case, we can see in the Fig. 3 that the difference between the two awake times of devices will be enough to transmit a signal. The invariant discussed in the following section will express this formally.

Invariant

Both new AT sets at_a_awake and at_b_awake are a subset of N. Values of variables a_sleept and b_sleept are in {st, lt}. We have the same property as in the previous invariant about time and values of AT set: time can not go after the first timeout. The new AT sets contain zero or one value:

∀(x, y)•(x ∈ at_a_awake ∧ y ∈ at_b_awake ⇒ |x -y| < prop))
If chosen delays are different, then devices have the time to transmit a signal. This formula shows why this algorithm works when chosen delays are different.

(a_sleept = b_sleept⇒ ∀(x, y)•(x ∈ at_a_awake ∧ y ∈ at_b_awake ⇒ prop ≤ |x -y|)) If the cardinality of at_a_pass is two then we have b_sleeptprop between awake time and the reception time of the first signal.

(b_in = ba ∧ ba = a_out⇒ ∀x•(x ∈ at_b_awake ⇒ min(at_a_pass) + b_sleeptprop < x)) Finally, these formulae ensure the refinement of events a_awake_send and a_awake_accept:

time ∈ at_a_awake ⇒ ab = IDL ∧ b_out = IDL time ∈ at_a_awake ∧ (a_out = P N ∨ ba = P N ) ⇒ b_state = sending case = F ALSE ∧ time ∈ at_a_awake ⇒ b_state = sleeping

Events

Again we show only the difference, we mark new lines with a ⊕ and removed lines with a ⊖. If an event is not present then it does not have any differences or it is symmetrical.

With the real-time properties of awake events we can remove all abstract conditions in guard of these events. The properties, expressed with the new AT sets, ensure this requirement as we can see in the last part of the invariant. For us, the primary way of verification is done by mechanical proof. But we also have used model-checking with ProB [START_REF] Leuschel | Prob: A model checker for b[END_REF]) in order to make partial verifications and to find counter-examples. In order to have a finite number of transitions with our models, we can not let the variable time increase indefinitely. Therefore, we define another version for the event tick_tock for model-checking. This version of the event tick_tock lets the variable time always be zero but decreases the values inside the AT sets. With this version, the number of transitions of the system is finite, with a fixed value for prop. But as time always equals zero and constants are valued, an invariant, determined to be correct with the model-checker, will not always be correct for the proof. In any case, model-checking provides a convenient way to discover invariants and to test them before the proof.

With the B prover the proof is cut into small "Proof Obligations" (PO). Some of those are automatically discharged and some need user interactions. All proofs of the first model are done automatically; for the first refinement 59 PO are interactive; for the second refinement 124; and for the last refinement 222. Of course all the proofs are done with the tool of the B method. As the model is symmetrical, the proof is also symmetrical, therefore, PO comes with a version for the device a and another similar version for the device b. Both versions are taken into consideration inside the number of PO. The first refinement is very easy to prove, the proofs of second and third refinement are short but numerous.

For the model-checking the first model and the second model are finite with 4 states and 24 states respectively. The next two models have only been validated with given valuations. For the second model, with prop ∈ {1, 2, ..6} the number of states are 25, 51, 81, 117, 159 and 207. For the last model, with (prop, st, lt) ∈ {(1, 2, 3), (2, 4, 7), (3, 6, 11), (4, 8, 15), (5, 10, 19), (6, 12, 23)} the number of states are 54, 186, 376, 624, 930 and 1294. The procedure of proof, with an invariant, leads to the discovery of an invariant strong enough to be inductive. We can always start with a small invariant containing types of variables and some requirements for the refinements of data or events. If we start to do the proof with an invariant that is too weak then the proof will fail with an impossible interactive proof. With this failure we see the missing piece of information about the system state: we add it to the invariant and retry to prove.

In the case of real-time systems, we can split PO in two parts: PO coming from the event tick_tock; and PO coming from all other events. The first kind of PO requires the invariant to be inductive with the progression of the time. The second requires the invariant to be inductive with the transitions of devices states. This leads to different kinds of proof and different constraints over the invariant but the two invariants are dependant.

Related-works and Conclusion

Many of other works about IEEE Root Contention Protocol (RCP) use model-checking over timed automata [START_REF] Alur | A theory of timed automata[END_REF]). We can find a comparative study of works about RCP in [START_REF] Stoelinga | Fun with FireWire: Experiments with verifying the ieee1394 root contention protocol[END_REF], this work extends thoses results by another approach. Our approach of verification is primary focused on proof by invariant. It's clear that an interactive proof takes more time than verification by model-checker or proof with decision procedures. This is the price to pay for an expressive general language based on set theory. But the tool cuts the verification proof in small and quite easy parts. And we plan to work on the rules of the tool in order to reduce the number of interactive steps, as the proofs show a repetitive scheme a lot of improvements can be done. The idea of using a variable to model the time is shown in [START_REF] Abadi | An old-fashined recipe for real-time[END_REF]. Here the model of time (AT sets) is different.

With our method, one can model a real-time system within the B method. The refinement relation between models can be used in order to introduce time in a model and can be used again to add real-time properties step by step. If a concrete model with time refines an abstract model we can prove the timing validity of the concrete model. At every step of refinement, we can verify the model and its invariants by model-checking it first and then by a computerassisted proof. This paper shows how our pattern of refinement of real-time constraints works on the IEEE 1394 RCP. The safety proof of RCP is done and we can see from the last invariant how the election works when chosen delays are different:

If chosen delays are different (a_sleept = b_sleept), then devices have the time to transmit a signal: ∀(x, y)•(x ∈ at_a_awake ∧ y ∈ at_b_awake ⇒ prop ≤ |x -y|)) But if chosen delays are equal (a_sleept = b_sleept), then devices do not have enough time:

∀(x, y)•(x ∈ at_a_awake ∧ y ∈ at_b_awake ⇒ |x -y| < prop)) Where at_a_awake and at_b_awake are sets of natural and represent the time when devices will stop to wait. And prop is the propagation time needed by the signal to pass from one device to another. Notice when devices are not in the state sleeping and do not plan to awake then the corresponding set is empty.

Our method can be used without changes to the language of B and therefore we can extend existing results and developments in B with real-time. As the proofs about passing of time are particular, we could consider a way of handling this specificity. Our time is discrete but in our proof the most important property used is the order over natural numbers. The time model used involves a global time which interacts with a number of time of activation stored in several sets as in a global multi-set. As the studied algorithm does not require synchronisation, the global time is not a problem but we can think about localising this into several distributed clocks for other case-studies.

  FIG. 1 -Accept event FIG. 2 -Devices and channels

  init b = BEGIN a_in, b_in, a_out, b_out, ab, ba := IDL, IDL, IDL, IDL, IDL, IDL a_state, b_state := reset, reset case := FALSE END; a_send b = WHEN a_state = reset∧ a_out = IDL THEN a_state := sending a_in := P N ab := P N END; b_send b = . . . ab_pass_out b = WHEN ab = b_out∧ (b_state = sending ∨ b_out = P N ) THEN b_out := ab ab := a_in END; ba_pass_out b = . . . pass_out b = WHEN ab = b_out∧ ba = a_out THEN b_out := ab ab := a_in a_out := ba ba := b_in END; a_accept b = REFINES accept WHEN a_state = reset∧ a_out = P N THEN a_state := accepting END; b_accept b = . . . a_sleep b = ANY new_ab WHERE a_state = sending∧ a_out = P N ∧ new_ab ∈ SIGN ALS∧ (ab = b_out ⇒ new_ab = IDL)∧ (ab = b_out ⇒ new_ab = P N ) THEN a_state := sleeping a_in := IDL ab := new_ab END; b_sleep b = . . . a_awake_send b = WHEN a_state = sleeping∧ a_out = IDL∧ ab = IDL∧ b_out = IDL THEN a_state := sending a_in := P N ab := P N case := ¬case END; b_awake_send b = . . . a_awake_accept b = REFINES accept WHEN a_state = sleeping∧ a_out = P N ∧ b_state = sending∧ ab = IDL∧ b_out = IDL THEN a_state := accepting case := ¬case END; b_awake_accept b = . . .

  b_in = ba ∧ ba = a_out ⇔ at_a_pass = ∅ a_in = ab ∧ ab = b_out ⇔ card(at_a_pass) = 1 b_in = ba ∧ ba = a_out ⇔ card(at_a_pass) = 2A device can not start to send after the reception of a signal P N so we have:∀(x, y)•(x ∈ at_a_pass ∧ y ∈ at_b_pass ⇒ |x -y| < prop)If cardinality of at_b_pass is two, then the difference of members are strictly under prop because they are both bound by time + prop and because the pass events have higher priority than sleep events.∀(x, y)•(x ∈ at_b_pass ∧ y ∈ at_b_pass ⇒ |x -y| < prop) The time continues to progress after a sending and if contention is reached we have: b_in = P N ∧ b_out = P N ⇒ time + prop / ∈ at_a_pass The events pass have higher priority than the events send: time ∈ at_a_pass ∪ at_b_pass ⇒ time + prop / ∈ at_a_pass ∪ at_b_pass This part allows us to prove the refinement of the event ab_pass_out: ab =b_out ∧ time ∈ at_b_pass -at_a_pass ⇒ b_state =sending ∨ b_out = IDL

  = sending ∨ b_out = P N ) ⊕time ∈ at_b_pass -at_a_pass THEN ⊕at_b_pass := at_b_pass -{time} END; ba_pass_out b = . . . pass_out b = WHEN ⊕time ∈ at_a_pass ∩ at_b_pass THEN ⊕at_a_pass := at_a_pass -{time} ⊕at_b_pass := at_b_pass -{time} END; ∪ at_b_pass)∧ THEN . . . END; b_awake_accept b = . . . tick_tock b = ANY tm WHERE tm ∈ N ∧ tm > time∧ ((at_a_pass ∪ at_b_pass) = ∅⇒ tm ≤ min(at_a_pass ∪ at_b_pass))∧ (a_state = sending ∨ a_out = P N )∧ (b_state = sending ∨ b_out = P N ) THEN time := tm END;

  init b = BEGIN ⊕at_a_awake, at_b_awake := ∅, ∅ ⊕a_sleept, b_sleept := st, st END; a_sleep b = ANY ⊕sleep WHERE ⊕sleep ∈ {st, lt} THEN ⊕at_a_awake := at_a_awake ∪ {time + sleep} ⊕a_sleept := sleep END; a_awake_send b = WHEN ⊕time ∈ at_a_awake ⊖a_state = sleeping ⊖ab = IDL ⊖b_outs = IDL THEN ⊕at_a_awake := at_a_awake -{time} END; a_awake_accept b = WHEN ⊕time ∈ at_a_awake ⊖a_state = sleeping ⊖b_state = sending ⊖ab = IDL ⊖b_out = IDL THEN ⊕at_a_awake := at_a_awake -{time} END; tick_tock b = . . . "same pattern plus at_a_awake and at_b_awake" 6 Verification by Proof and Model-checking

This work was supported by grant No. ANR-06-SETI-015-03 awarded by the Agence Nationale de la Recherche.

This invariant restricts the possible values of at_a_awake: ab = P N ∧ b_out = IDL ⇒ time + prop / ∈ at_a_awake Here we can see that, in two different cases, the signal is received before awake time:

In the following conditions the awake time is before signal reception:

(case = TRUE ∧ a_sleept = b_sleept⇒ ∀(x, y)•(x ∈ at_a_awake ∧ y ∈ at_a_pass ⇒ x < y)) After the discovering of the contention, device a erases its signal at a propagation time before awake time:

∀(x, y)•(x ∈ at_a_pass ∧ y ∈ at_b_awake ⇒ x + prop ≤ y) If chosen delays are equal, then devices do not have the time to transmit a signal:

(a_sleept = b_sleept⇒