come

Introduction

Lay people and educators have traditionally shunned the use of two or more languages within the same interaction or utterance arguing that it stems from speakers' lack of competence in one or all the languages involved. In an effort to 'combat' language mixing, educational institutions in particular have made use of several measures ranging from punishment to educational downgrading to assigning separate time slots or spaces to different languages. It is only in recent years, probably spurred by the widespread use of such practices in many domains such as the media, music, advertising etc. that opinions about code alternation practices have been improving. However, educators and educational institutions are only timidly adopting new approaches to multilingualism such as the Translanguaging approach (e.g. [START_REF] García | Bilingual education in the 21 st century: A global perspective[END_REF]) that value people's multifaceted language competences and seek to build on them. Since code alternation practices challenge (structural) assumptions about the homogeneity of grammar and its independence from use, linguistic research has traditionally been concerned with understanding its workings, thereby seeking to legitimize its rightfulness.

Two broad lines of research have developed on code alternation. One deals with structural issues and the other is concerned with functional issues. Structural approaches to code alternation (e.g. [START_REF] Poplack | Patterns of language mixture: nominal structure in Wolof-French and Fongbe-French bilingual discourse[END_REF][START_REF] Muysken | Bilingual Speech: A typology of code-mixing[END_REF]Myer-Scotton 1993b) are based on formal syntactic and psycholinguistic models and have been mostly concerned with identifying "the nature of the grammar underlying bilingual mixture." (Winford 2003: 126). Focusing on isolated instances of intra-sentential code-mixing usually involving clearly distinct languages, this line of investigation seeks to understand whether speakers rely on a single grammar or whether different grammars are at play, and how interaction between these different grammatical systems might be organized. Social or functional approaches to code alternation (e.g. [START_REF] Blom | Social meaning in linguistic structures: code-switching in Norway[END_REF]Myer-Scotton 1993a;[START_REF] Zentella | Growing up Bilingual[END_REF], by contrast, focus on identifying the types of code-switching patterns that exist, their social functions and meanings and the social motivations for code-switching. Using methods of discourse or conversation [START_REF] Auer | Bilingual conversations[END_REF] analysis, researchers have analyzed situated discourses involving a range of languages pairs.

Migge Bettina

Although both research traditions share the same overarching goal -understanding the workings of code alternation practices -they have proceeded separately without much crossfertilization because they do not presently share the same methods of data collection and analytical frameworks. The aim of this chapter is to critically examine some of their main tenets and to highlight some areas where cross-fertilization would help to advance current knowledge. The paper argues that the two approaches are in fact complementary and should feed into each other. Greater attention to functional concerns in structural research on code alternation, for instance, would help to get a deeper understanding of the types of structural phenomena, their distribution and the constraints that govern their occurrence (see also Backus and Amuzu's papers in this volume for a discussion of related issues).

The data for this chapter come from recordings of situated interactions that were recorded in (western) French Guiana and Suriname involving mostly the closely-related English-based creoles Aluku, Ndyuka, Pamaka, that are collectively also referred to as Nengee or Eastern Maroon Creoles (EMC), and Sranantongo (SN) that originate from eastern Suriname. The paper considers both data from so-called native speakers who employ the languages as their main or only language of interaction and so-called non-native speakers who learned them later in life and only use them for some of their communicative needs.

Section 2 discusses some of the issues that arise in structural approaches to code-switching. Section 3 explores issues in social approaches to code-switching. Section 4 examines the findings and proposes an integrated approach to investigating instances of code-switching.

Conceptualizing Code-Switching: A structural perspective

From the perspective of structural research on code alternation or code-switching (CS) there are only two types of CS patterns, so-called inter-sentential and intra-sentential CS. They are differentiated based on where the switch occurs. In inter-sentential CS switches occur at clause or sentence boundaries: each sentence or clause comes from a different language. For instance, in (1) the first clause is entirely in English while the second one is entirely in Spanish.

(1) It's not the same you know, no e(-s) como acá. (English-Spanish) 'It's not the same you know, it's not like her.' (Zentella 1994: 99) Intra-sentential CS, by contrast, is broadly defined as involving insertion of single elements or phrasal entities from one language into the morpho-syntactic frame or sentence structure of another language. In (2) the French noun blague is integrated into a structure that is entirely in Kali'na.

(2) blague-mempo wa. (Kali'na-French) joke-little.person be 'I'm a little commedian.' (Alby and Migge 2007: 54) Based on the tacit assumption that the two types of CS can be easily separated, structural research has focused on intra-sentential CS because it "produces various kinds of hybrid structures that require explanation." (Winford 2003: 126). 1 Discussion of these hybrid structures has been concerned with issues such as the identification of the morpho-syntactic frame of these structures and the types of elements that may be involved in CS and the rules that govern their occurrence. I discuss each in turn.

2. 1. Classifying instance of intra-sentential CS While there are cases of congruent lexicalization [START_REF] Muysken | Bilingual Speech: A typology of code-mixing[END_REF] where two (or more) languages "share a similar structure which can be filled lexically with elements from either language", current structural approaches to CS such as the Matrix Language Model (MLF; Myers-Scotton 1993a) generally operate on the assumption that mixed utterances consist of a main or matrix language and a subordinate or embedded language. The matrix language (ML) provides the grammatical frame of a sentence, namely the morpheme order principles, rules and the function or system morphemes. Additionally, the ML generally also contributes most of the content morphemes. The embedded language (EL), by contrast, provides single content morphemes that are integrated into the ML frame. Thus, in the case of example (2), Kali'na is the matrix language while French is the embedded language as it only provides a single element, a morpheme. There are also structures where an entire phrase or island, in the words of Myers-Scotton (1993b), comes from the embedded language. In (3), for example, the French noun phrase la feuille forms an island in a Kali'na structure in that it consists of more than one French item and the rules that govern their combination also come from French rather than Kali'na.

(3) Ami la feuille se wa. (Kali'na-French) 'I want the piece of paper.' (Alby and Migge 2007: 54) It has been notoriously difficult to establish precise criteria for identifying the ML and the EL in any given case. Myers-Scotton (1993a: 68) argues that the language that provides the greater number of morphemes in a discourse sample typically also functions as the ML. However, in some cases this criterion might be too crude as it is possible that one or more changes in ML/EL take place throughout the discourse (Nortier 1990: 158). People might start out in one language and then continue in another language (or in what could be called a mixed code). Take for instance the example in [START_REF]i si a wagi disi?[END_REF]. Here the speaker produces an entire sentence in Dutch and only uses the Eastern Maroon or Nengee affirmative marker eyee as an assertive particle at the end of the sentence. The following sentence is entirely in the Eastern Maroon Creole apart from the word frank which is best classed as a borrowing from Dutch. [START_REF]i si a wagi disi?[END_REF] Maar ik heb geen waarde aan jou, eyee. Pe mi meki but I have NEG worth of you yes where I make wan dunsu frank wan dey, da i e meki… DET 1000 francs DET day then you IMPF make 'But I don't gain anything from you, yes. When I make one thousand francs 1 However, the two kinds of CS also appear side-by-side either within the same interactional context or across different ones (Pandit 1990, Paff 1979, as cited in Winford 2003: 164-5), see also section 3. a day, then you want me to…' Note: italics: Dutch; bold: Eastern Maroon Creoles But even if we pay attention to the sentence or utterance level and simply count the words in a sentence, it is often difficult to establish the makeup of the ML. Take for instance example (5) from the French Guianese corpus involving contact between Nengee and Sranantongo in the speech of a Pamaka man.

(5) A sani dati, I kan taagi en taki a tori dati mu skotu a mu kii en.

DET thing DEM you MOD tell him say DET story DEM must end s/he MOD kill it 'That thing, you can tell him that issue must end, he should stop it.' Note: regular: shared EM/SN elements In (5) four words (underlined) are clearly identifiable as belonging to Nengee, five words (bold) are associated with Sranantongo and eight words (regular) are best described as being shared between the two. It seems unsatisfactory to claim that Sranantongo is the ML of (5) simply on account of the fact that there is one more distinctive Sranantongo than Nengee word in this sentence. Since the notion of the ML is heavily dependent on the idea of function morphemes and grammatical rules and principles, categorization could also focus on these two aspects. However, this still does not provide much more certainty because all the structural principles and a total of six function morphemes (a: DET.sg (2); a: 3sg.sbj (1); en: 3sg.obj (2) i:2sg.sbj (1)) are shared, three are from Sranantongo (dati: distal demonstrative modifier (2); kan: weak obligation (1)) and one is linked to Nengee (mu: strong obligation (1)).

In addition to difficulties with applying a simple counting procedure for making decisions about the ML, there is also the issue of elements that do not appear to belong to either Nengee or Sranantongo. Such items are intermediate between Sranantongo and Nengee and thus cannot be easily assigned to either nor are they on a par with what I have so far called shared elements, i.e. elements that are found in both languages. Elements from other languages such as Dutch, French and English in particular are equally difficult to classify as it is not always clear whether they are in fact borrowings in either or both of the two languages or whether they are independent insertions. In example (6a) the word pickup could probably be classified as a borrowing from English as it is used in (certain styles of) Nengee and Sranantongo. However, based on its phonology and the fact that it is also used in Dutch, it might also be classified as a borrowing from Dutch. The case is even more complicated with respect to tweede, nooit and rei in (6b). All three of them have Nengee and/or Sranantongo alternatives that are also still being used, however to different degrees. While rei appears to be the main form to express the notion of 'drive' in Sranantongo, ley and waka are still commonly used in varieties of Nengee.

Nooit also derives from Dutch and is also common in Sranantongo; its integrated from noiti occurs in both Sranantongo and Nengee but is much more common in Nengee. 2 Finally, tweede is clearly Dutch but also widely used in urban Sranantongo, while in Nengee the form taa one 'other one' is also common. This suggests that in (6b) all three words could be classified either as being part of Sranantongo or as separate insertions from Dutch.

( Given that these kinds of structures are rather frequent in the corpus, it seems better to postulate the existence of a shared or separate frame which can be filled with elements shared by Sranantongo and Nengee, elements from other languages (i.e. Dutch), in-between elements (Table 1) and distinctive elements from different languages. Viewed from this perspective, only structures that involve predominantly Nengee (7a) or Sranantongo (7b) elements and/or are governed by principles that are distinctive of one or the other language would then count as belonging to either of these languages. Other structures such as (5 and 6) would then constitute a separate category which is neither Nengee or Sranantongo, but a bilingual or multilingual code. Social evidence in favor of such a triparte distinction comes from research on social identities and language use among Maroons [START_REF] Migge | Code-switching and social identities in the Eastern Maroon community of Suriname and French Guiana[END_REF][START_REF] Migge | Negotiating Social Identities on an Eastern Maroon Radio Show[END_REF]Migge andLeglise 2011, 2013). It shows that younger Maroon men in particular closely identify with being Maroon as opposed to members of the Afro-Surinamese creole population who are ideologically linked to Sranantongo. However, having been stigmatized as backwards, younger Maroons are also at pains to display that they are urban and modern. In order to negotiate these two aspects in their self-presentation -being Maroon but having modern sophistication -Maroons creatively combine aspects from both realms. That is, they create a 'third' 2 One of the reviewers suggests that nooit is considered Dutch if it occurs in sentence-final position without a final /-i/. However, Sranantongo noiti and Dutch nooit are indistinguishable in midsentence because, Sranantongo tends to elided final vowels in non-final position.

way of being that is fuzzy from the point of view of traditional ways of categorizing people and languages. They combine aspects from Nengee and Sranantongo (culture and language), and increasingly also from other languages such as Dutch and French that are also marked as urban, modern and 'being part of the wider world', to display their multiple connections and, more crucially, to avoid being identified with (negative stereotypes of) either. This fuzzy style is particularly common in interactions among young(er) men who are socio-culturally most closely identified with the world beyond the local networks and community. It is an important feature that traditionally distinguishes them from elders and women and thus its use makes a claim to membership in this category. It is also used in other contexts such as in conflicts with elders and flirtation, where status negotiation is at play. This then suggest that in order to determine the ML or EL of a given structure, we not only require a broad understanding of the overall social context (i.e. what kinds of modes of being and identities exist), but we must also know the types of practices (monolingual codes, mixed codes) that are part of the local sociolinguistic economy, their broad associations, characteristics and functions. This kind of information is important for distinguishing types of CS patterns that are similar on the surface but functionally different and thus are likely to be governed by different (structural) constraints.

Elements in intra-sentential code-switching

Structural approaches to CS, like Myer-Scotton's MLF model, posit that the ML provides all the system or function morphenes while the EL only contributes content morphemes. Not being structurally heavily bound, content morphemes such as verbs, nouns and adjectives can be freely switched between languages. By contrast, switching of system or function morphemes is subject to special constraints because it requires a certain amount of (perceived) congruence between the structural systems in contact. System morphemes belong to a closed class involving a range of elements such as tense, mood and aspect markers, quantifiers, inflectional morphology etc. (see Myers-Scotton 1993a: 101 for a list of elements). 3 The only exceptions to this stipulation are cases where the morphology of both the ML and EL are used on the same element, so-called cases of double morphology, and so-called EL islands, where whole phrases from the EL that contain function elements are inserted into the ML. The examples in [START_REF]Da i no sabi ala den wagi fu mi. 'Then you don't know all of my cars[END_REF] illustrate the typical distribution of the ML and EL forms. The function morphemes and most of the content morphemes are from one language and only one content morpheme -a noun (8a) and a verb (8b) -comes from another language or is distinctive. (8a) comes from a discussion carried out in the Eastern Maroon variety Pamaka; only the word prijs clearly derives from Dutch. (8b) comes from the same discussion and could be described as involving an insertion from Sranantongo, namely wroko. 4 (8) a. Mi gi i wan prijs kaba. I give you DET price already 'I gave you the price already.'

3 Note, however, that the distinction between function and content morphemes is not always that clear (Winford 2003: 115). 4 Alternatively, (8b) could also be interpreted as involving a shared Sranantongo/Eastern Maroon frame with a distinctive element from Sranantongo. 9a) follows the structural principles of both Nengee and Sranantongo and all the morphemes except la PAF come from these two languages. La PAF is best described as a French island that has been inserted into the shared Nengee and Sranantongo ML frame. It only consists of elements from French which are also combined using structural principles from French -note that the latter happen to overlap with those of the ML, however, in Nengee and Sranantongo nouns in this position would only be preceded by a determinier under certain conditions. There are also examples where the structural principles of the EL island only conform to those of the EL. In (9b) the structural makeup of the sentence follows Nengee and Sranantongo rules, however, the order of words in the EL island carte grise follows that of French as the adjective follows the noun. 5 Unfortunately, the corpus only included instances that could be seen as partially holophrasitic, but observation also 'produced' the following example Gi mi a pantalon bleu di de a ini i saka. 'Give me the blue pair of trousers that are in your bag.' which involves the same ordering of noun and adjective as in (9b While the data involve few function morphemes from European languages, some such as uit (10a) do nevertheless occur outside of so-called EL islands. 6 What is, however, striking is the fact that alternation between function morphemes such as the negation marker (EM án/ná -SN no), some modality markers such as the obligation marker (EM mu -SN musu), the potential modality marker (EM sa -SN kan) [START_REF] Migge | The origin and development of possibility in the creoles of Suriname[END_REF], the relative marker (EM di -SN san), the committative preposition (EM anga -SN nanga) are commonly used besides discourse markers (tok; EM yee -SN yere) and phono-lexical features such as the alternation of long vowels with an rV sequence (EM wooko -SN wroko) or the variation between /l/ and /r/ (EM leli -SN leri 'learn') in code alternation practices. That is, speakers do not only draw on content morphemes, but also code-switch system morphemes and these system morphemes are not typically part of EL islands as predicted by Myer-Scotton (1993b). 7 This is of course facilitated by similarities in structure between Nengee and Sranantongo, but it is not clear that typology is the only driving force. It also points to the fact that speakers, unlike linguists, do not systematically distinguish between content and function morphemes or focus on content morphemes only, as implied by structural models. Rather, in their efforts to create distinctive patterns (i.e. to encode social and interactional meaning), speakers simply focus on areas or elements where alternate forms exist without regard to their lexical status. 8 The amount of elements that are made salient depends on the context and communicative intent, i.e. whether the speaker wants to be fuzzy or align with a particular language, see below.

3. Conclusion

The discussion suggests that while structural research on CS has much advanced our knowledge about these kinds of hybrid structures, there are still a number of issues that appear to be difficult to resolve by solely relying on structural methods of data collection and analysis. While it is important to distinguish the kinds of systems that are involved in instances of CS, reliance on structural criteria such as word counts alone are problematic because it is difficult to determine indicative cut-off points or how to deal with shared or intermediate forms especially in the case of closely related languages. Speakers do not differentiate varieties or languages on structural grounds either functions as a preposition or as a prepositional or separable affix. In Surinamese languages uit always appears in post-verbal position. In this sentence is seems to be parallel to a result-expressing serial verb SN trowe/ EM towe. 7 See also Bentahila and Davies (1983: 315) for a discussion of this and related issues in relation to Arabic and French CS. 8 One area that has not received attention is this regard is the area of intonation which could be of particular importance especially in the case of closely related languages.

or apply frequency counts. Instead, issues of salience -what is considered to be distinctive of a given variety/language -and their presence or absence tend to play a more important role in choosing material from one or the other language. It is therefore vital that CS research starts out with an assessment of the broader sociolinguistic context. Based on the perspective of all social actors in the setting, we need to establish the sociolinguistic structure of the setting such as the number of varieties/languages that are recognized, their distribution and their distinctive features, before making judgments about the systems in interaction. This needs to take account of the fact that linguists' views of what constitutes a language or a system might be quite different from speakers' views. For instance, research has spent much ink on arguing for the different role of content and function morphemes in CS, however, data from French Guiana suggest that this distinction does not play an important role in the code-switched productions that emerge in this context where speakers use closely related language varieties. 9 Speakers regularly draw on both function and content morphemes (outside of so-called islands) in their production of such patterns. Detailed understanding of speakers' conceptualizations of varieties, i.e. what they consider to be emblemic, and their relationships in a given context and across settings might shed light on the importance and this distinction.

Structural research on CS has made some headway in providing insights into the principles and rules that govern CS patterns, but accounts fall short of explaining the factors that promote CS in general and the occurrence of the two types of CS patterns that they posit. In addition, there is a tacit assumption that there are only these two types of CS patterns and that they do not have an internal structure. In the next section I will take up these issues in more detail by looking at sociolinguistic approaches to CS.

Conceptualizing Code-Switching: A qualitative perspective

In contrast to structural research, sociolinguistically oriented work on CS has focused on establishing the types of CS patterns that exist and explored the functions and motivations for CS as well as the relationship between types and functions. While researchers in the area agree that there are several kinds of CS patterns (see below) beyond the two posited by structural researchinsertional and alternational CS -and that there are important linkages between CS patterns, functions and settings, there is disagreement about the nature of these linkages and ways of examining them.

1. Socially-oriented model of code-switching

One of the socially oriented approaches to CS is Myers-Scotton's (1993a) Markedness Model. It is based on the insights of [START_REF] Blom | Social meaning in linguistic structures: code-switching in Norway[END_REF] study of CS in Hemnes, Norway, which argued that alternation between codes has social significance -it conveys a change in the extralinguistic context (situational switching) or functions to assign meaning to an utterance (metaphorical or conversational switching). The basic premise of the Markedness Model is that speakers' code 9 While there is a fair amount of structural and morphemic overlap between Nengee and Sranantongo, there are also important differences. It is on these differences that people focus when code-switching to create interactional meanings. Note also that speakers are generally dominant in one or the other variety and only have varying degrees of knowledge of the other. choices are strategic and goal-oriented, being determined by speakers' interactional goals and the interaction's social characteristics, including both the extralinguistic nature of the interaction and the speech economy of the community and the setting. CS 'exploits the socio-psychological attributes that languages assume in a specific community, based on its patterns of language use' (Myers-Scotton 1993a: 3). The social motivations for CS are determined by the relative social markedness of codes in an interaction. 10 Each code indexes a specific kind of social relationship, including participants' attitudes and expectations to each other, the so-called rights and obligation (RO) set. The model posits that for each interaction, there are (relatively) marked and unmarked choices. Unmarked choices are considered relatively habitual, common or expected and employ the main or most typical medium for a given interaction, symbolizing the most typical RO set for a given interaction. Marked choices, by contrast, make use of non-typical or 'embedded' codes, are relatively rare and unexpected and are interpreted as a departure from the normative code and RO set for the interaction. They are 'a negotiation about the speaker's persona (who the speaker is) and the speaker's relation to other participants' (Myers-Scotton 2006: 160). Speakers select marked or unmarked codes based on considerations of communicative effectiveness, i.e., which choices will maximize interactional rewards and minimize interactional costs. Essentially, CS is 'a meta-message of conversational moves' and functions to negotiate 'speakers' perceptions of themselves and their relations with others' (Myers-Scotton 1993a: 111).

The Markedness Model posits four types of CS. Each one occurs in a different kind of social situation, indexes a distinct self-image of the speaker and his/her view of the relationship between interlocutors (RO set). Code-switching as a sequence of unmarked choices also referred to as sequential unmarked code-switching occurs when situational factors such as the topic, the participants or the narrative framework change during an interaction causing a change in the RO set. In order to index the new RO set and, more crucially, its acceptance, interlocutors change their interactional code. By contrast, code-switching itself as the unmarked choice or unmarked code-switching refers to a situation in which speakers frequently switch between two or more languages in the same interaction. This could involve both insertional and/or alternational switches. It differs from the other CS types in that 'each switch […] does not necessarily have a special indexicality; rather, it is the overall pattern which carries the communicative intention' (Myers-Scotton 1993a: 117). It is found in situations in which an ethnic language is highly valued but coexists with another language used for status-raising activities. Interlocutors are generally members of a common peer group and wish to actively invoke their alignment with the two social worlds that these two codes index; it is a way of making aspects of these two worlds salient. The third type she refers to as Code-switching as a marked choice. It occurs when the speaker selects a code that is seen as a marked choice in the interaction. It signals the speaker's lack of agreement with the expected RO set and their attempt to negotiate a new RO set. Finally, code-switching as an exploratory choice occurs when uncertainty exists about the appropriate RO set for the situation. Interlocutors will then switch between different codes that they share and thereby offer different RO sets until they find one on which they can both agree. [START_REF] Auer | Bilingual conversations[END_REF][START_REF] Auer | The pragmatics of code-switching: a sequential approach[END_REF] equally focuses on determining the social meanings and functions of CS.

10 '[S]peakers have a sense of markedness regarding available linguistic codes for any interaction, but choose their codes based on the persona and/or relation with others which they wish to have in place' (Myers-Scotton 1993a: 75) of two or more codes that has signaling power rather than the languages involved or the directionality of change. While each language is arguably linked to particular social meanings, settings and activities, this association is probabilistic rather than absolute. He argues that like gesture and intonation, CS functions as a contextualization cue. It does not have a fixed referential meaning, but makes relevant "some aspects of the context which, in turn, is responsible for the interpretation of an utterance in its particular locus of occurrence." (Auer 1995: 123). This means that the meaning of CS, like that of other contextualization cues, is derived at through a process of context-sensitive inferencing that has to be investigated separately for each instance of CS. There are two ways in which inferencing generates meaning. CS either creates a contrast to what went on before, indicating otherness such as lack of agreement or difference in voice, for instance. Or, in addition to signaling otherness, CS, like other contextualization cues, also restricts the number of possible inferences "because cues may have (received) an inherent meaning potential due to conventionalization or frequency of use of the pattern" (Auer 1995: 124). According to Auer (1995: 124), CS also has its own characteristics because "the situated interpretation of code-alternation as a contextualization cue is strongly related to the sequential patterns of language choice."

He distinguishes four patterns. The first one represents the case whereby an established language-of-interaction, A, for a certain context is at some point during the interaction switched to language B during turn transition from speaker 2 to speaker 1 (Ia) or within one turn (Ib). The switch in language-of-interaction is accepted by the interlocutor(s) and the conversation continues in language B. Patterns Ia and b contextualize a change in the characteristics of the interaction such as a change in conversational activity, topic, mode or participants. They are equivalent to Myers-Scotton's (1993a) sequential unmarked code-switching.

Pattern Ia: A1 A2 A1 A2//B1 B2 B1 B2 Pattern Ib: A1 A2 A1 A2 A1//B1 B2 B1 B2

A second pattern also referred to as language negotiation involves the use of different languages by the interlocutors. Either such a pattern of language alternation persists (IIa) or is resolved in favor of one of the languages at some point during the interaction (IIb). Patterns II signal speaker preference such as in terms of broad political considerations or issues of language competence. They are similar to Myers-Scotton's (1993a) code-switching as an exploratory choice and marked codeswitching though her definition carries a stronger assumption that interlocutors aim towards resolving language choice in favor of one language.

Pattern IIa: A1 B2 A1 B2 A1 B2 A1 B2 Pattern IIb: A1 B2 A1 B2 A1//A2 A1 A2 A1

The third pattern involves CS within single turns that defies clear establishment of a language-ofinteraction. The internal switches, or at least some of them, may have indexicality, but do not need to. In the latter case, they provide insights into how people view the situation and into how speakers want to position themselves, and are thus both discourse-and participant-related. Interlocutors may either decide to carry out the interaction in this mixed mode (IIIa) or adopt one of the two languages (IIIb).

Pattern IIIa: AB1 AB2 AB1 AB2 Pattern IIIb: AB1//A2 A1 A2 Pattern IV involves insertion of single words or phrases from language A into a turn otherwise carried out in language B. Auer refers to this momentary departure from the language-ofinteraction as transfer and argues that it can be discourse-and participant-related in that it may contextualize a particular interactional frame or a person's language competence. Patterns IIIa and IV are similar to unmarked code-switching in Myers-Scotton's (1993a) categorization.

Pattern IV: A1[B1]A1

The discussion suggests that there are important similarities between the two models. Crucially, both models posit that there are several CS patterns. a's approach posits a relatively close linkage between the type of pattern and its social and interactional functions as well as its interpretative approach is heavily dependent on the sociolinguistic meanings of the languages involved. In contrast, Auer's approach posits a much less fixed linkage arguing that meanings have to be carefully defined using a sequential analysis of interactional choices. The same pattern may simultaneously and/or depending on the interaction perform several functions.

2. Code-switching in the data from French Guiana and Suriname

One aspect that is very striking about the data from French Guiana and Suriname is the fact that there do not appear to be clear instances of patterns I and IIa and b. Much of the data resembles patterns IIIa or IV in that there is alternation between elements from two or more languages, including shared forms, within and across turns. Take Extract (1):

Extract (1) 1 B: Da na yu meki a wagi! 'Thus, you repaired the car!' 2 D: Aai 'Yes' 'Thus you are still walking, man really.' 15 D: No, mi mag, eyee mi o ka fini. BL, BL, da i no poti a tweede wan nooit a, a i rey?

Ya tok, ef i no poti a souda nooit a, a i rey, na mi na a souda. 'No, I am allowed to, yes, I can stop. BL so you have never yet used the second one. Does it work? Yes, ok, if you never use the Souda, it will never work. I want the Souda car.' italics: Sranantongo; bold: Nengee; italics/underlined: Dutch; bold/underlined: French Guianese Creole; roman: shared Nengee & Sranantongo

In Extract (1) several younger men interact in a local bar in Saint-Laurent-du-Maroni. There are no turns that can be unambiguously assigned to just one language. Most of the turns involve alternation between shared Nengee and Sranantongo forms and distinctive ones coming from either of the two languages or other languages such as French Guianese Creole or Dutch. Extract (1) is a case of what has been described as transfer (Auer) or unmarked CS (Myers-Scotton) in that switches mostly involve individual words and each switch does not appear to have a special indexicality.

Instead, it is the overall pattern that is of interest. It is a case of participant-related switching because speakers essentially display their diverse linguistic competence to each other, a crucial feature of peer-group behavior among them as it signals urban sophistication [START_REF] Migge | Code-switching and social identities in the Eastern Maroon community of Suriname and French Guiana[END_REF].

However, not all instances of what appears to be CS are in fact an instance of CS. Take for instance Extract (2) which was delivered by a man from Guyana who was conversing with a Maroon man who is roughly from the same age range (late 30s to mid 40s).

Extract (2)

Dede of dede wo broko a basis yere, tru efu i no wani taki, i mu denki taki moro gaan bigi basis fu Europe dya tok, da a kondre nooit i si taki a kondre abi wan bun waarder tok. A kondre no abi wan bun waarder di seti, fosi den wetman seti wan bunbun waarder na a kondre. I sabi san den man e du? 'Even if there are fatalities, we will destroy the European Space centre [in Kourou], right, honestly, if you don't want to talk, you should remember that the biggest space centre of Europe is here, right, but this country never, you never see that they value the country properly, right. The country does not have a value on its own outside of the value that the Europeans have brought to the country. You know what they did?' italics: Sranantongo; bold: Nengee; italics/underlined: Dutch; bold/underlined: French; roman: shared Nengee & Sranantongo Taking a language perspective, we see that there are elements that originate from different linguistic sources such as Nengee, French, Dutch, Sranantongo and shared Sranantongo/Nengee forms. The overall pattern closely resembles that in Extract (1). The main difference, however, is that while this kind of mixed code is only one of the styles that the interlocutors in Extract (1) do in certain kinds of interactions, this is the main or only way that many non-Maroon interlocutors speak. The latter are often either not fully aware that their way of speaking involves insertions from several languages or they assume that this is the way to speak Nengee or what is often referred to as Takitaki in French Guiana because their main interlocutors, the Maroons of this age group, typically speak like that in public out-group settings (Migge and Léglise 2013). Extract (2) is best described as a case of dialect convergence.

However, as pointed out by Auer (1995: 131-2), this kind of alternation may also have indexicality and perform both participant-and discourse-related functions. In Extract (3), a woman in her early 40s is explaining language practices to the author and another European friend of hers.

Extract [START_REF] Yu | Then you are international, man. Then I'll buy a broken car[END_REF] 1 Bs: ma a wakaman taal teki fesi hem, a wensi i go na Paramaribo, i e si taki a 2

Sranan sei, i e si taki na soso wakaman taal den man e puur kon, den 3 man e tak' in code, den man e fringi tek' i! 'but the wakaman language has become most important, even when you go to Paramaribo, you see that on the Surinamese side, you see that it's only wakaman language they are pulling out, they are speaking in disguised form, they are throwing it at you.'

In this conversation, Bs is clearly at pains to display her linguistic versatility by alternating shared Sranantongo/Nengee elements with ones that originate from Dutch (taal 'language'), non-Sranantongo/Nengee (Paramaribo) or Sranantongo (Sranan sey 'Suriname'). This kind of alternation is very fluid, not involving hesitation. However, her alternation towards the end of line (2) and in line ( 3) between shared and Sranantongo elements is discourse-related. She is using parallelism to create a climax in her description of wakaman taki, a style of Sranantongo. The carrier phrase is realized using shared Sranantongo/Nengee forms, but the descriptive part is clearly set off in the Sranantongo style that is being described and through special emphasis. This voicing assigns authority to the description.

Extract (4) comes from the same context as Extract (1). While these men commonly draw on CStransfer or unmarked CS -to display their linguistic versatility (e.g. Extract 1), CS is also used to distinguish different parts of the discourse or activities. In line (1) Br is imagining what he will do and get during a hunting trip in a somewhat dreamy way. This is done using mostly shared Sranantongo/Nengee and Nengee forms. This saliently contrasts with Pe's turn in lines (2-4) that predominantly consists of shared and Sranantongo forms and employs a somewhat creaky voice quality that is commonly associated with urban (younger) male speech. This shift negotiates Pe's irritation with Br's inability to seriously engage with the organization of the hunting trip. This suggests that variation in the relative amount and type of insertions may contextualize a change in discourse activity (dreamy speech versus complaining) and a difference in self-representation in that Pe distances himself from Br's dreamy behavior, claiming a more authorative self. Extract (4) 1 BR: Ya tok ma mi, den fisi 11 di mi o kisi dape, den o tyahipi en mi na fisi mi e go suku. 'Ok, but I, the fish that I will catch there, they'll be a lot and as for me, it's fish that I'm searching for.' 11

The word fisi (but also kisi) followed Eastern Maroon pronunciation [fɪ∫i] Structuring also occurs at the level of lexical choices. Interlocutors may draw on 'mundane' forms that are commonly known or traditional or 'racy' forms that have modern or subcultural overtones and thereby create different social identities [START_REF] Spitulnik | The language of the city: Town Bemba as urban hybridity[END_REF]) and different kinds of relationships. Compare, for instance, Extracts (1) and ( 5). In Extract (1), the interlocutors draw on elements from several languages and several of them (international, tweede, tok, ya tok, I sabi tok) have become associated with young men's in-group speech. 12 Interactions involving these kinds of forms invoke young men's life worlds and position their users as members of that in-group. By contrast, Extract (5), which comes from an interaction between titled elders at the end of a fairly formal interaction, involves only mundane forms from Sranantongo that contrast with Nengee and shared elements in lines [START_REF]i si a wagi disi?[END_REF](5). The insertions assign a Sranantongo reading to the turn, negotiating a (momentary) shift away from the relatively formal relationship that typically exists between the two elders. Interactionally, it functions to convey that the request to talk to the author is harmless (i.e. does not involve a marriage proposal).

Extract (5)

1 Anton: Ma, daaa, fa de e kai a flou nen? 'But, so what's the woman's name?' 2 Bettina: Bettina! 3 Anton: Soo Betna. (.) 'Okay, Bettina.' 4 (to O, another Kabiten) So, da (.) kabiten, mi kan taki ptyin tori anga a uman pikinso 5 'yere? A nowan mulikimuliki toli.

'Okay, well kabiten, can I chat a little bit.'with the woman, right? It's nothing bothersome.'

6 O: (nods approvingly and laughs) 7 O: Iya, iya papa! 'Yes, yes elder!' (Migge 2007: 103) 4. Conclusion: Towards an empirically adequate approach to CS The discussion suggested that while structural approaches to CS have highlighted important principles about the patterning of CS, most of the principles and assumptions that have been proposed over the years have turned out to be problematic upon closer empirical inspection. While it is intuitively right to assume that CS involves juxtaposition of two or more codes, their identification and determination of their respective roles in the juxtaposition is far from 12 It is not entirely clear whether the Dutch-marked forms should be considered as insertion from Dutch or as Dutch borrowings in Sranantongo/Nengee. More than likely, this differs among speakers.

uncontroversial. There are no adequate measures that can be applied across the board to unambiguously determine whether a language functions as the matrix language or as the embedded language, or whether we are dealing with a case of dialect convergence. Word counts run into problems because there are not clear-cut off points and because simple word counts cannot take adequate account of structural features such as word order. General assumptions about the social appropriateness of a given language in a particular setting are problematic because associations between language and social settings are rarely stable over time or across speakers; they can function at best as broad guidelines. The functions of languages may also change within the same interactional context. It may also simply be difficult to distinguish varieties/languages on structural grounds alone because forms cannot be easily assigned to one or the other language or because mixed codes have developed that defy easy lexico-structural identification. Moreover, while content morphemes clearly play an important role in CS patterns because their lack of structural boundedness facilitates interlingual identification, this does not mean that function morphemes have no role to play in CS. In fact, particularly in the case of closely related languages function morphemes may be strategically deployed for negotiating patterns of distinction. Finally, while both structurally and sociolinguistically-oriented research have identified different kinds of CS patterns, neither set of patterns (insertional versus alternational; 4 basic patterns) exhausts the kinds of tactics (e.g. variation in frequency of distinctive vs. fuzzy forms, use of racy vs. mundane forms ) that bilinguals make use of for contextualizing participant and discourse-related meanings. The discussion in this paper points to a need for a much more fine-grained, socio-pragmatically sensitive and usage oriented sequential analysis of CS (see also Amuzu's discission of Ewe-English code alternation patterns in this volume). CS, like so-called style-shifting among monolinguals, is not epiphenomenal, but an important resource for negotiating social and interactional meanings (see also Chen's discussion of code alternation and identity in Hong Kong in this volume); the meanings, in turn, influence the structure of CS patterns. Research on CS must thus be embedded in a detailed analysis of a community's speech economy that takes into account the views of all local actors and is guided by both people's ideologies and actual practices. Using an ethnographic approach, such an analysis should determine the kinds of speech forms including mixed forms that are recognized by people, their salient or emblemic linguistic characteristics as well as their social functions and uses. Since we cannot assume simple correlations to exist between social functions and language use and structural makeup and functions, each instance has to be analyzed in detail using what [START_REF] Auer | Bilingual conversations[END_REF][START_REF] Auer | The pragmatics of code-switching: a sequential approach[END_REF] refers to as a sequential approach. Thus, comprehensive analysis of CS should

• be empirical and analyze each instance of CS separately within its context of occurrence.

• focus on situated language use.

• first identify the interactional functions and patterns of instances of CS before carrying out a structural analysis

• should examine each pattern or type of CS separately as the same principles may not hold across all types. • explore how observable patterns of CS link to the negotiation of social identities and existing patterns of language use and ideologies of language.

  men don't know how to work with him.' b. ay, eyee, den presi dati yes, those places are difficult!'

  car lights are working?' Besides these classic examples, there are also examples of EL islands. Example (

Table 1 gives a few common examples from the corpus. Table 1. Forms that are intermediate between Nengee and Sranantongo

	Form	Gloss	Nengee Form	Sranantongo Form
	dape	there	ape	drape
	pliti	split	piiti	priti
	planga	planks	paanga	pranga
	heli	whole	hii	heri

  ).

	e. Mi kan	ley	tu	trip i	ferstan	tok.
	I	MOD	drive two trip you understand right
	'I can make two trips, you understand, right.'
	f. A	man ya, a	wan	man di ben	sooto tok.
	DET	man DEM FOC DET	man REL PAST	lock	right
	'This guy, he was locked up, right.'

  rather than Sranantongo phonological patterns [fɪsi].3 Mi e ley den man fu mi. Efu yu no kba, a yur di i o kba, i e gi mi so wan yuru i o kba, 4 i sabi tok. Mi e teki yu tapu a yuru fi i, i sabi tok. . . 'You don't understand what I'm doing now, I can do two trips, you understand right, I can do two trips. I drive my guys. If you are not ready, the time when you are ready, you give me a specific time when you'll be ready, you know. I come and take you at the time you want to, you know right . . .' (Migge and Léglise 2013: 277)

Note that the use of uit in this sentence does not function in the same way as in Dutch. In Dutch it


Dennis Craig, a prolific writer and highly acclaimed researcher in applied linguistics and sociolinguistics, was born in Guyana but "owed many of his accomplishments to his adopted country-Jamaica-where he lived for most of his life" (Allsopp & Jennings, p. viii). He taught at the University of the West Indies, Mona, and served as dean of its faculty of Education. In Guyana he was the first director of the National Centre for Education Research and Development and in 1991 became vice chancellor of the University of Guyana. Throughout his career he tirelessly advocated for the improvement of the educational and social conditions of creole speakers in the Caribbean. His writings inspired many of his contemporaries and continue to resonate with researchers and educators in the Caribbean and more widely. It is therefore only fitting that two volumes have been published in his honor.

Language Education in the Caribbean opens with a preface highlighting Craig's proactive social engagement through a discussion of his popular Viewpoint columns written for the Guyana Broadcasting Company and an introduction outlining the main concerns of his academic publications. It then reprints four of his articles dealing with the socio-linguistic context of the English-official Caribbean and four focusing on effective teaching and learning policies and approaches for this context. With respect to the first issue, Craig echoes the creole continuum perspective and argues that the English-official Caribbean is characterized by variation between Standard English and local creoles resulting from creole speakers' "striving for social status through English" (p. 17) and inappropriate teaching methods. This has given rise to a third system, the "interaction area" (p. 17) or the mesolect(s); children from creole dominant homes mistakenly equate it with English and thus face problems in school where Standard English norms are enforced. Craig argues that all three varieties share the same conceptual base but make use of different grammatical principles and lexical forms to express it. The creole and creole-influenced varieties (or mesolects) mostly share the same grammar and mainly differ on the lexical level. Thus shifting simply entails substituting English-like lexical forms for creole ones. However, since there are significant structural differences between the creole and English forms, acquisition of English requires learning of a set of new procedures, rules, and principles.

Given this situation, Craig argued that traditional teaching and learning models that assume Caribbean children to be native speakers of English and attempt to teach children English through implicit correction are not only ineffective but also contribute to children's linguistic insecurity and negative representations about their primary language. Instead, he advocated an approach termed Bidialectal Education that takes into account and actively raises awareness about the socio-cultural and linguistic distinctiveness of creole languages and English while at the same time acknowledging the existence of overlap, or rather similarities, between the two systems. The approach also maintains that effective language education has to be based on children's actual practices and communicative needs and should introduce new features gradually and in a systematic manner through a combination of structured communication oriented and culturally adapted activities. Instead of an immersion approach, he argued, shared and known features should be practiced before new ones are introduced. Finally, children should at all times be encouraged to freely draw on all their linguistic resources for meaning making.

Education Issues... is a collection of fifteen original essays introduced by a short foreword and preface which both pay tribute to Craig's important achievements. In the first of the book's four parts, "Dennis Craig in Caribbean Language Education," Jeff Siegel and Beverley Bryan discuss Craig's contribution to Applied Linguistics generally and English language teaching in the Caribbean. Siegel argues that Craig's work was instrumental in raising awareness about the unique educational issues in the Caribbean and related contexts and in highlighting problematic assumptions underlying traditional educational models, but that his most important contribution consisted in proposing feasible alternative models. Bryan explains how Craig's research findings spurred educational reform in Jamaica and sowed the seeds for new educational projects such as the Bilingual Education Project.

In the second part, "The Background to Caribbean Language," Richard Allsopp discusses the contribution of African languages to Caribbean creoles, and Hazel Simmons-McDonald revisits and refutes statements about the deficient nature of creoles and pidgins. Finally, Pauline Christie examines existing language teaching models in the Caribbean in the light of current research on varieties of English. She argues that Caribbean education systems need to develop their own set of norms for English based on actual usage in professional contexts.

Part Three, "Policy Issues and Perspectives on Vernacular Education in the Caribbean," includes five articles. Peter Roberts revisits Craig (1999), Teaching Language and Literacy: Policies and Procedures for Vernacular Situations, with a view to assessing the factors "that should provide a basis for adding to and modifying the detailed organization of syllabus and techniques set out in the book" (p. 82). He advocates greater attention to affective rather than rationalizing factors and to children's actual language practices. Hazel Simmons-McDonald discusses her inclusive language education program that aims to concurrently develop greater levels of proficiency in and knowledge about Standard English, the main medium of instruction in schools in St. Lucia, and children's primary languages, Kwéyòl, and the English-lexicon Vernacular. Ian Robertson's paper, in line with Craig, argues for greater attention to well-structured and systematic grammar teaching that focuses on "the meaningfulness of the element being taught" (p. 164), rather than simply formal accuracy. Some of the results of the latest education project, the Bilingual Education Project (BEP), are the focus of Hubert Devonish and Karen Carpenter's contribution. Analyzing grade 4 literacy test outcomes, they show that while "the English-language competence of the BEP pupils was not greater than that of the non-BEP group by the end of four years" (p. 179), the results confirm that bilingual Creole-English education does not negatively affect children's cognitive and English-language abilities. Finally, Valerie Youssef's essay examines language use in the classrooms of fifteen Trinidadian teachers. She demonstrates that while teachers were fully proficient in Standard English and also used it as their main means of instruction, they (particularly those below the age of 45) also made strategic use of Trinidadian Creole for a variety of reasons such as facilitating potentially face-threatening speech acts and "to establish realistic local context effectively" (p. 201).

In the final section, "Issues of Context," Kathryn Shields Brodber draws attention to the pragmatics of English in the Caribbean. Identifying Standard English in the Caribbean with the formal domain and negative politeness practices (and denying the existence of negative politeness practices in creoles), she argues that English language teaching should be used as a vehicle for teaching students about the concept of formality and decorum. Velma Pollard, discussing two thematic units for the teaching of literature, explains how a multisensual and interactive approach that extends to "creative material not usually considered literature" (p. 227) fires students' imagination and leads to positive engagement with literature. Jeannette Allsopp reviews the history of the teaching of French in the Caribbean, showing how traditional teaching methods and problematic stereotypes about the language have led to a situation where there are few competent speakers of the language despite its relative importance in the local tourist industry. Finally, two contributions focus on the North American context. Ian Roberts reflects on the social and particularly linguist situation of Caribbean children in North America, while John and Angela Rickford discuss the merits of a new reader for African American children to be adopted by the California Department of Education, and outline the way the contrastive approach can be applied to sensitively and effectively raise students' awareness about the differences between African American English and standard English.

Taken together, the two volumes provide a compact and highly stimulating overview of language education research in the English-official Caribbean. Although many of the social and language-based inequalities described by Craig still persist, it is clear that on-going social change and language-based research are contributing to the destigmatization of Caribbean language practices and are generating new responses to and understandings of this context.

Craig, Dennis R. 1999. Teaching Language and Literacy: Policies and Procedures for Vernacular Situations. Georgetown, Guyana: Education and Development Services.

Bettina Migge School of Languages, Cultures and Linguistics, University College Dublin, Dublin, Ireland bettinamigge@ucd.ie

  Zellynne Jennings (eds.) Language Education in the Caribbean: Selected Articles by Dennis Craig. Jamaica, Barbados & Trinidad and Tobago: University of the West Indies Press. 2014. xx + 171 pp. (Paper US$ 22.00) Ian Robertson & Hazel Simmons-McDonald (eds.) Education Issues in Creole and Creole-Influenced Vernacular Contexts. Jamaica, Barbados & Trinidad and Tobago: University of the West Indies Press. 2014. xii + 291 pp. (Paper US$ 40.00)


Kristine Lund
email: kristine.lund@univ-lyon2.fr

Guy Prudhomme
email: guy.prudhomme@hmg.inpg.fr

Searching for patterns in how students perform collaborative design

In the research presented here, we work to discover patterns in a collaborative design task, performed synchronously and at a distance by three university students, using the collaborative platform DREW (drew.emse.fr), developed during the European project SCALE (IST 5 th framework). Our objectives are 1) to understand how participants carry out such design tasks 2) to form hypotheses about the role of resources and tools in learning or performing such tasks and 3) to test these hypotheses. Our final goal, in collaboration with industrial partners, is thus to propose ways of improving the design task either with new methods or tools that, by hypothesis, will facilitate designers' work, thus increasing efficiency and saving time and resources. We define patterns to be recurring sequences of activities and of interactions. In our contribution to the workshop, these concepts will be defined and our theoretical framework and methodological approach will be described. Results will illustrate examples of the patterns of activities and interactions found in the corpus and finally, we will explore the relation between the two types of patterns and discuss how this can help us meet our research objectives.

Introduction

The design patterns we refer to are patterns of interaction and activity found in situations where designers work together to find a solution to a design task. Our work centers on methods for the discovery of such patterns in CSCL situations, with a view to transposing them to CSCW situations. In what follows we will briefly define our view on interaction and activity in design, present our corpus, our analytical methods and our results. We will end with concluding remarks.

We consider an interaction between human beings to be a series of actions that mutually influence each other where this mutual influence can function on physiological, epistemic, emotional and socio-relational planes (Baker, Andriessen, Lund, Amelsvoort & Quignard, under review). Considering that argumentation is at the heart of collaborative design, we are interested in argumentative interactions. Activity is considered from a particular cognitive ergonomics point of view and is defined to be the response that the individual implements in order to carry out a task [START_REF] Prudhomme | An empirical study of engineering knowledge dynamics in a design situation[END_REF] where the task is a given goal in predetermined conditions. For these authors, both the task and the activity can be prescribed from the authority's point of view. The task and the activity can also be expected which may differ from the prescribed task, redefined from the operator's point of view, and actually carried out from the operator's point of view. We use these definitions of task and activity for the individual in the collaborative learning/work situation. The above definitions of interaction and activity show that our general theoretical framework is situated and distributed cognition.

Corpus

The technical problem we chose was given to the students by an initial document that presented a summarized principal scheme (cf. Figure 1). It described the mechanical, economic and functional specifications. The product to design consisted of an element that introduced a rotation of a wheel by the means of a double pulley that allows firstly for recuperating the mechanical power from an electric motor and secondly, for transferring part of this power to another similar system. We focus in particular on the design of the double pulley and on its liaison with the shaft (Prudhomme, Pourroy & Lund, in preparation).

Analyzing Interaction and Activity

We used the Rainbow framework [START_REF] Baker | Computer-supported collaborative learning in the space of debate[END_REF] to analyze the computermediated interactions that took place during the design task. Rainbow comprises seven principal categories, each assigned a different color, hence its name. The original objective of the analysis framework was to determine to what extent students engaged in argumentative interactions and thus attained the goal of the situations we designed during the aforementioned SCALE project: broadening and deepening understanding of the space of debate. We do not have space to present the Rainbow categories in depth (although see Figure 2); their names are 1) off-task, 2) social, 3) interaction management, 4) task management, 5) opinion, 6) argument and finally, 7) broaden and deepen argument.

Concerning activity, we used an observation grid (Metz, Renault & Cassier, 2006) in order to represent those activities we expected (based on a first empirical study and previous research in the literature) to observe in a situation of synchronous and remote co-design of an industrial product. Again, we do not have space to present the activity observation grid in depth, but the categories are cognitive and social synchronization, proposal of solutions, search for resources, evaluation, project management, coordination and social relation.

Results

In this section we will give two examples of patterns we found in our corpus. Figure 2 shows the analysis using the Rainbow framework of an extract of our corpus produced by DREW [START_REF] Corbel | DREW: A Dialogical Reasoning Web Tool[END_REF]. Due to lack of space, we only illustrate a short pattern that demonstrates how the expression of opinions ("i don't like solution c" or "ah well i like that solution") leads to arguments (eg. "why; because you don't have a good torque") and to the exploring and deepening of one of them ("unless the tooling is really precise"). Interventions 103-105 are considered to all form the argument categorized on line 105. DREW also allowed for the construction of argumentation graphs where the space of debate is represented by a thesis and arguments for and against that thesis (cf. Lund, Molinari, Séjourné & Baker (under review) Figure 3 shows the same extract analyzed as being part of one of the patterns of activity we found based on the dynamics of the proposal of solutions and the evaluation of them in terms of different criteria. In this vision of collaborative design, similar to the QOC (question, object, criteria) model (MacLean, Young, Bellotiv, Moran, 1996), the chat interventions that we considered as arguments for or against a solution within the Rainbow framework are now seen as criteria that are mobilized to assess the solution currently being considered (here, solution c). In this activity pattern, the solution is divided into component parts (drive shaft shoulder and cone) and different criteria are put forward in relation to the separate parts (precision and pushing effort for the drive shaft shoulder). In addition, as arguments are seen as criteria, designers can explore and deepen criteria (pushing effort is not managed unless tooling is precise), but also explore and deepen solutions in terms of characteristics of component parts, for example (a different activity pattern, not shown). Figure 3. An example of one activity pattern partially instantiated, using the same extract as was analyzed with the Rainbow framework

Concluding remarks

Our two different analytical approaches to collaborative design, through interaction and through activity have allowed us to discover specific patterns in the ways designers communicate and find solutions to the design task. In all, four different activity patterns were discovered (based on an initial Rainbow analysis of interactions) one of which was illustrated here. Our next goal is to redesign DREW and structure the design process in order to better support the patterns we discovered and test how designers' work may be facilitated through its use in CSCL and CSCW situations.

Figure 1 .

 1 Figure 1. The schema of the product to design

Figure 2 .

 2 Figure 2. An example of an interaction pattern analyzed with the Rainbow framework

  for an example). Rainbow was designed to analyze both chat and graphical interventions.

	N° Time	Designer Chat intervention content	Tool	Rainbow
	100 15/04/05 10:26	Bob	i don't like solution c	chat	5. Opinions
	101 15/04/05 10:27	Bob	y:because you don't have a good torque	chat	6. Argument
	102 15/04/05 10:27	Alan	ah well i like that solution	chat	5. Opinions
	103 15/04/05 10:27	Bob	if there's a drive shaft shoulder	chat
	104 15/04/05 10:27	Bob	we'll have	chat
	105 15/04/05 10:28	Bob	good precision but we won't be able to manage the pushing effort	chat	6. Argument
	106 15/04/05 10:28	Bob	unless the tooling is really precise	chat	7. Explore and deepen
	107 15/04/05 10:28	Bob	do you see what i mean?	chat	3. Int. Management

Acknowledgements

We would like to thank Jean-Laurent Cassier for his contribution to Rainbow analyses, Franck Pourroy for discussion concerning activity patterns and all the members of the French regional projects COSMOCE and ASPIC.


Romain Deville

Elisa Fromont

Baptiste Jeudy

Christine Solnon

Mining Frequent Patterns in 2D+t Grid Graphs for Cellular Automata Analysis

A 2D grid is a particular geometric graph that may be used to represent any 2D regular structure such as, for example, pixel grids, game boards, or cellular automata. Pattern mining techniques may be used to automatically extract interesting substructures from these grids. 2D+t grids are temporal sequences of grids which model the evolution of grids through time. In this paper, we show how to extend a 2D grid mining algorithm to 2D+t grids, thus allowing us to efficiently find frequent patterns in 2D+t grids. We evaluate scale-up properties of this algorithm on 2D+t grids generated by a classical cellular automaton, i.e., the game of life, and we show that the extracted spatio-temporal patterns may be used to analyze this kind of cellular automata.

Introduction

A 2D grid is a particular geometric graph that may be used to model any 2D regular structure such as, for example, grids of pixels (i.e., images), game boards, or cellular automata. To characterize these grids, we may mine them to extract recurrent patterns [START_REF] Deville | Grima: a grid mining algorithm for bag-of-grid-based classification[END_REF]. In some applications, we use temporal sequences of grids (i.e., 2D+t grids) to model the evolution of grids through time. This is the case, for example, of videos, or sequences of actions in board games. In this paper, we motivate and illustrate our work on Cellular Automata (CA) used to model the temporal evolution of ecosystems [START_REF] Breckling | Cellular Automata in Ecological Modelling[END_REF][START_REF] Wootton | Local interactions predict large-scale pattern in empirically derived cellular automata[END_REF][START_REF] Wolfram | Cellular automata as models of complexity[END_REF]. Indeed, biodiversity of ecosystems is increasingly recognized as an important element of global change. CA-based models are used to understand, predict and control spatio-temporal spread of species which is a key issue to preserve biodiversity [START_REF] Marco | Species invasiveness in biological invasions: a modelling approach[END_REF]. A CA is a regular grid of cells. Each cell has a state which evolves through time, depending on the state of its neighbours in the grid. One of the most famous CA is the Game of Life [START_REF] Conway | The game of life[END_REF]. In this CA, the grid is in 2 dimensions (on toric grids), and each cell has 8 neighbours (horizontally, vertically, and diagonally). Initially (at time t = 0), each cell is either alive or dead. The state at time t + 1 of a cell depends on its state and on the state of its 8 neighbours at time t. It is computed by applying the following rules: 1) if the cell is alive at time t and has 2 or 3 living neighbours, then it is alive at time t + 1, otherwise it becomes dead; 2) if the cell is dead at time t and has exactly 3 living neighbours, then it becomes alive at time t + 1, otherwise it stays dead. When executing a CA from a given initial state, one may observe the emergence of spatio-temporal patterns, and these patterns are characteristic of different ecosystem outcomes. [START_REF] Wolfram | Cellular automata as models of complexity[END_REF] distinguishes four possible outcomes: (1) development of a homogeneous fixed pattern, (2) development of a periodic pattern, (3) development of a chaotic pattern, and (4) development of patterns composed of homogeneous regions and regions containing complex localized structures.

In this paper, we present an efficient algorithm for extracting spatio-temporal patterns in 2D+t grids. This algorithm may be used, for example, to extract meaningful spatio-temporal patterns in CA. When CA are used to model ecosystems, these patterns could be used by ecologists to better understand and control the dynamics of the ecosystems. For example, [START_REF] Breckling | Cellular Automata in Ecological Modelling[END_REF] explains that we can foresee the future of an ecosystem by identifying recurring patterns. Ecologists are also interested in understanding how dependent the patterns and the initial state are.

Our algorithm is an extension of GriMA [START_REF] Deville | Grima: a grid mining algorithm for bag-of-grid-based classification[END_REF], an algorithm for mining 2D grids which has been designed to tackle real-life applications such as image classification. This algorithm is recalled in Section 2. In Section 3, we show how to extend it to mine 2D+t grids. In Section 4, we evaluate scale-up properties of our new algorithm for mining game-of-life CA, and we show that the extracted spatio-temporal patterns are relevant for classification purposes.

Background on 2D Grids and GriMA

Definition of 2D grids, and 2D subgrid isomorphism. A 2D grid is a special case of graph such that each node has a 2D coordinate which is a couple of integer values, and each edge connects nodes which are neighbours on a grid. More formally, a grid is defined by G = (N, E, L, x, y) such that N is a set of nodes, E ⊆ N × N is a set of edges, L : N ∪ E → N is a labeling function which associates a label L(c) with every component (node or edge) c ∈ N ∪ E, and x : N → Z and y : N → Z map each node u ∈ N to its 2D coordinates (x u , y u ), and

∀(u, v) ∈ E, |x u -x v |+|y u -y v | = 1. A subgrid of a grid G = (N, E, L, x, y) is a grid G = (N , E , L , x , y ) such that N ⊆ N , E ⊆ E ∩ N × N and L , x ,
and y are the restrictions of L, x, and y to N ∪ E , N , and N , respectively.

Looking for patterns in a grid amounts to searching for subgrid isomorphisms. Patterns should be invariant to translations and rotations. More formally, the translation of G = (N, E, L, x, y) by a vector T ∈ Z 2 , denoted G + T , is the grid obtained by moving all its nodes with respect to T , i.e., ∀u ∈ N , (x u , y u ) becomes (x u , y u ) + T . Let Θ = { 1 0 0 1 , 0 -1 1 0 , -1 0 0 -1 , 0 1 -1 0 } be the set of rotation matrices of respective angles 0, π/2, π and 3π/2. The rotation of G with respect to θ ∈ Θ, denoted θG, is the grid obtained by rotating all its nodes with respect to θ, i.e., ∀u ∈ N, (x u , y u ) becomes (x u , y u )θ. Two grids G 1 and G 2 are grid isomorphic if there exist a translation T ∈ Z 2 and a rotation θ ∈ Θ such that G 1 = T + θG 2 . Finally, G 1 is sub-grid-isomorphic to G 2 if there exists a subgrid of G 2 which is isomorphic to G 2 (see Fig. 1 for an example).

Graph mining. Given a database D of graphs and a frequency threshold σ, the goal of the graph mining problem is to output all frequent subgraphs in D, i.e., all graphs G such that there exist at least σ graphs in D to which G is subisomorphic. This problem may be solved by gSpan [START_REF] Yan | gSpan: graph-based substructure pattern mining[END_REF], and all similar general exhaustive graph mining algorithms [START_REF] Jiang | A survey of frequent subgraph mining algorithms[END_REF]. However, as the subgraph isomorphic problem is N P-complete, these algorithms do not scale well. On the other hand, Plagram [START_REF] Prado | Mining spatiotemporal patterns in dynamic plane graphs[END_REF] and FreqGeo [START_REF] Arimura | Time and space efficient discovery of maximal geometric graphs[END_REF] are graph mining algorithms dedicated to special cases of graphs for which subgraph isomorphism becomes polynomial, i.e., plane graphs for Plagram and geometric graphs for FreqGeo. These algorithms have better scale-up properties. However, Plagram only mines patterns composed of faces and the smallest possible subgraph pattern is a single face, i.e., a cycle with 3 nodes. Using Plagram to mine grids is possible but the problem needs to be transformed such that each grid node becomes a face in the graph tackled by Plagram. This transformation artificially increases the number of nodes and edges which causes a scalability problem for Plagram. Also, grids are special cases of geometric graphs. Therefore, FreqGeo may be used to mine grids. However, it has a higher time-complexity than GriMA, the 2D grid mining algorithm introduced in [START_REF] Deville | Grima: a grid mining algorithm for bag-of-grid-based classification[END_REF].

Description of GriMA. GriMA follows the same basic principle as gSpan, Plagram, and FreqGeo to avoid generating the same pattern multiple times: It uses codes to represent grids. This code is a list of edges encountered when performing a traversal of the grid. A grid may have several codes but one of them is chosen as the signature: The canonical code, which is the largest code wrt lexicographic order. GriMA explores the search space of all canonical codes in a depth-first recursive way. It first computes all frequent edges and then calls an Extend function for each of these frequent extensions. Extend has one input parameter: A pattern code P which is frequent and canonical. It outputs all frequent canonical codes P such that P is a prefix of P . To this aim, it first computes the set E of all possible valid extensions of all occurrences of P in the database D of grids: A valid extension is the code e of an edge such that P.e occurs in D. Finally, Extend is recursively called for each extension e such that P.e is frequent and canonical. Hence, at each recursive call, the pattern grows.

2D+t Grid Mining Algorithm

A 2D + t grid is defined by a tuple (N, E, L, x, y, t) such that (N, E, L, x, y) is a 2D grid graph and t : N → Z is a function that maps nodes to temporal coordinates, i.e., ∀u ∈ N , t u is the temporal coordinate of node u. Also, edges are enforced to connect neighbour nodes in the grid, i.e.,

∀(u, v) ∈ E, |x u -x v | + |y u -y v | + |t u -t v | = 1. We distinguish two different kinds of edges: spatial edges (such that |x u -x v | + |y u -y v | = 1) and temporal edges (such that |t u -t v | = 1).
2D grid isomorphism is defined so that isomorphism is invariant to translations and rotations. When extending this definition to 2D+t grids, we still ensure that isomorphism is invariant to translations wrt all axis. However, as time is an oriented dimension, we allow rotations only along the temporal axis. Hence, we consider the set Θ = {

1 0 0 0 1 0 0 0 1 , 0 -1 0 1 0 0 0 0 1 , -1 0 0 0 -1 0 0 0 1 , 0 1 0 -1 0 0 0 0 1
} of rotation matrices of respective angles 0, π/2, π and 3π/2 along the temporal axis.

To extend GriMA to 2D+t grids, we have to define the canonical code of a 2D+t grid. A code C(G) of a 2D+t grid G is a sequence of n edge codes (C(G) = ec 0 , ..., ec n-1 ) which is associated with a depth-first traversal of G starting from a given initial node. During this traversal, each edge is traversed once, and nodes are numbered: The initial node has number 0; each time a new node is discovered, it is numbered with the smallest integer not already used in the traversal. Each edge code corresponds to a different edge of G and the order of edge codes in C(G) corresponds to the order edges are traversed. Hence, ec k is the code associated with the k th traversed edge. This edge code ec k is the tuple (δ, i, j, a, L i , L j , L (i,j) ) where :

i and j are the numbers associated with the nodes of the k th traversed edge.

δ ∈ {0, 1} is the direction of the k th traversed edge:

• δ = 0 if it is forward, i.e., j is a new node reached for the first time;

• δ = 1 if it is backward, i.e., j already appears in ec 0 , ..., ec k-1 . a ∈ {-2, -1, 0, 1, 2, 3} is the angle value of the k th traversed edge (i, j):

• if (i, j) is a temporal edge, then a = -2 if t i = t j + 1, and a = -1 if t i = t j -1; • else, (i, j) is a spatial edge.
* If (i, j) is the first spatial edge encountered since the beginning of the traversal, then a = 0. * Else, let (l, m) be the first spatial edge in ec 0 , ..., ec k-1 such that x i = x m and y i = y m . We have a = 2A/π where A ∈ {0, π/2, π, 3π/2} is the angle between (l, m) and (i, j) in the x, y plane. -L i , L j , L (i,j) are labels of i, j, and (i, j), respectively. For example, let us consider code 1 in Fig. 2. Let us explain how the code of the fourth traversed edge (E, F ) is built. δ = 0 because (E, F ) is a forward edge (F has not been reached before). (E, F ) is a spatial edge, and the first spatial edge (l, m) such that m has the same spatial coordinates as E is (B, C). The angle between (E, F ) and (B, C) is 0. So, a = 0. For the fifth edge of code 1, (F, B), δ = 1 because B has already been reached before (backward edge). As (F, B) is a temporal edge, a = -2.

Given a code, we can reconstruct the corresponding grid since edges are listed in the code together with angles and labels. However, there exist different possible codes for a given grid, as illustrated in Fig. 2: Each code corresponds to a different traversal (starting from a different initial node and choosing edges in a different order). As we did for GriMA, we define a total order on the set of all possible codes that may be associated with a given grid by considering a lexicographic order (all code components have integer values). Among all the possible codes for a grid, the largest one according to this order is the canonical code of this grid and it is unique. For example, in Fig. 2, code 1 is canonical: It is greater than codes 2 and 3, and it is also greater than all other possible codes for this grid (not shown here).

Note that it is not necessary to exhaustively build all codes when computing a canonical code. We use heuristics to first build large codes (by first choosing spatial edges with 3π/2 angles, such as for (D, B) and (B, C), for example). Also, when building a code, we stop the traversal as soon as the corresponding code becomes smaller than the largest current code.

This canonical code for 2D+t allows us to extend GriMA to mine 2D+t grids in a straightforward way, and we can show that the resulting mining algorithm, called GriMA2D+t, is both correct (it only outputs frequent subgrids) and complete (it cannot miss any frequent subgrid). The proof (not detailed due to lack of space) basically shows that every prefix of a canonical code is canonical.

GriMA2D+t enumerates all frequent patterns in O(kn 2 .|P | 2 ) = O(kn 4 ) time per pattern P , where k is the number of grids in the set D of input grids, n the size of the largest grid G i ∈ D (in number of edges) and |P | the number of edges in a pattern P .

Node-induced GriMA2D+t. In our application, the mined grids are complete and have no label on edges. Thus, we designed a variant of GriMA2D+t, called node-induced-GriMA2D+t, which computes node-induced grids, i.e. grids induced by their node sets. This corresponds to a "node-induced" closure operator on graphs where, given a pattern P , we add all possible edges to P without adding new nodes. We have shown in [START_REF] Deville | Grima: a grid mining algorithm for bag-of-grid-based classification[END_REF] that this optimization decreases the number of extracted patterns and the extraction time.

Limitation on edge extension. Moreover, to avoid mining patterns that only contain dead cells, we also limit the extension procedure of our mining process. In the Extend function, we forbid extension with edges linking two dead cells. As a consequence, every edge (i, j) in a mined pattern is such that either i, or j, or both i and j correspond to living cells.

Experiments

We study the scale-up properties of GriMA2D + t and assess the relevance of the mined patterns on a classification task related to the behavior of a CA, i.e., the Game of Life described in Section 1. More precisely, given the k first cell states, with k ∈ {1, 2, 5, 10, 20}, the goal is to forecast the outcome at time t = 1000, where we only consider two possible outcomes: dead (if all cells are dead at time t = 1000), or alive (if at least one cell is alive at time t = 1000).

Dataset. We consider four sizes of grids n × n, with n ∈ {20, 30, 40, 50}. For each size n, we randomly choose the initial state (dead or alive) of each n × n cell wrt to a cell probability p. We have chosen p in such a way that the outcome at time t = 1000 is dead or alive with equal probabilities. This way, we ensure during our dataset generation process that there is no bias towards one of the two classes. This imposes a cell probability p of 74%, 78%, 80%, and 81% for n = 20, 30, 40, and 50, respectively. Besides, to avoid trivial predictions of the class dead, due to the fact that all cells may be dead before the k th iteration, we only select initial states such that there is at least one cell alive at the 50 th iteration. For each size n ∈ {20, 30, 40, 50}, we generate a set S n of 2000 initial states such that the outcome at time t = 1000 is dead for half of them (S d n ), and alive for the other half (S a n ). We split each set S d n and S a n into two equal parts for learning (L d n and L a n ) and training (T d n and T a n ).

2D+t grids. For each state s i ∈ S n (with n ∈ {20, 30, 40, 50}), and for each temporal horizon k ∈ {1, 2, 5, 10, 20}, we build a 2D+t grid G(s i , k) which is a temporal sequence of k 2D grids: The first one corresponds to the state s i , and the next k -1 ones correspond to states obtained by iteratively applying the game-of-life rules starting from s i . Each node is labeled with either 0 (dead cell) or 1 (cell alive), and all edges have the same label.

Mining process. For each size n ∈ {20, 30, 40, 50} and each temporal horizon k ∈ {1, 2, 5, 10, 20}, we mine frequent patterns in the learning sets. This is done for each class separately: We compute the set F d n,k (resp. F a n,k ) of frequent patterns in all G(s i , k) with s i ∈ S d n (resp. s i ∈ S a n ). We consider two different frequency threshold σ ∈ {50%, 100%}: When σ = 50% (resp. σ = 100%), a pattern is frequent if it is present in half of the grids (resp. all the grids). Note that, the higher the frequency, the lower the number of mined patterns and the more efficient the mining process. Each mining process has been limited to 12 hours of CPU time: If the mining process is not completed after 12 hours, we stop it and consider the subset of patterns that have been extracted within this time limit.

Classification process. For each size n ∈ {20, 30, 40, 50} and each temporal horizon k ∈ {1, 2, 5, 10, 20}, we build the set

F n,k = F a n,k ∪ F d n,
k that contains all frequent patterns (in the two classes). Then, for each state s i ∈ L d n ∪ L a n , we count the number of occurrences of each pattern of F n,k in G(s i , k), and build a frequency vector that gives the frequency of each pattern. Hence, each state is represented by a histogram of frequent substructures.

We report two sets of experiments: One with histograms created using all the patterns mined on both classes (which can be very sparse) and one with a selected subset of 100 patterns. This post-processing selection is performed using the relevance score and the greedy selection algorithm presented in [START_REF] Fernando | Mining mid-level features for image classification[END_REF]. To fasten the preprocessing step, we delete at each of the 100 iterations of the greedy algorithm, the patterns with the 10% lowest scores.

Frequency vectors (of length |F n,k | or 100) are used to train a binary Support Vector Machine (SVM) to discriminate between the two classes. We use the Libsvm [START_REF] Chang | LIBSVM: A library for support vector machines[END_REF] library with the intersection kernel presented in [START_REF] Odone | Building kernels from binary strings for image matching[END_REF] (known to be good on histograms).

Finally, we use the trained model to forecast the class of each state in our training set: For each state s i ∈ T d n ∪ T a n , we count the number of occurrences of each pattern of F n,k (or the 100 selected patterns of F n,k ) in G(s i , k), and build a frequency vector which is used by the SVM model to forecast an outcome (dead or alive) which is compared to the true outcome (dead for states coming from T d n and alive for states coming from T a n ). We report accuracy results, i.e., the percentage of states for which the forecasted outcome is equal to the true outcome.

Accuracy results. We report accuracy results in Table 1. When increasing the temporal horizon k (i.e., the temporal size of the mined grids), accuracy results are improved. This shows the relevance of the GriMA2D+t algorithm compared to GriMA. However, when increasing k, the mining process needs more time and we often had to stop the mining process after 12 hours (red cells) for the largest values of k. In this case, we only explored part of the substructure search space.

Also, the larger the grid size n, the better the results. It is well known that, for the game of life, large grids have higher probabilities of containing stable patterns that may characterize alive outcomes. However, as with k, we often had to stop the mining process after 12 hours for the largest grids. This shows the necessity of efficient algorithms to tackle real-life problems. The number of mined patterns |F n,k |, is smaller when the frequency threshold σ = 100% than when it is 50%. For small temporal horizons k ∈ {1, 2}, the number of mined patterns is not large enough (smaller than 27 for k = 1 and than 79 for k = 2). In this case, the results obtained with σ = 100% are worse than those obtained with σ = 50%. However, for larger time horizons k ∈ {5, 10, 20}, the number of mined patterns becomes large enough for σ = 100% while it becomes so large for σ = 50% that the mining process is never completed. As we only have a subset of the frequent patterns in this case, it may be possible that some relevant patterns have not be found. We observe that in this case the results are worse with σ = 50% than with σ = 100%.

Finally, let us compare the results obtained when all patterns of F n,k are used for the classification (All Pat) with the results obtained when we only use the 100 first patterns selected by the post-processing process (100 Pat): The difference is usually rather small, and in some cases it improves results (e.g., k = 20, n = 40) whereas in some other cases it degrades them (e.g., k = 20, n = 20). However, the post-processing improves the efficiency of the counting step: The process of counting all occurrences of all patterns of F n,k (to create histograms used as inputs for the SVMs) takes on average 0.002 seconds when k = 1 and up to Overall, those results show that taking into account the structural information along the spatio-temporal grids can be used for the prediction of the outcome of cellular automata and the extension to temporal dimension of our grid mining algorithm can be used to tackle spatio-temporal problems.

Patterns statistics. Table 2 reports some statistics about the mined patterns (all patterns in F n,k , or the 100 ones selected by post-processing). We report the average and maximum (in parenthesis) number of nodes of each pattern as well as their depth, i.e., the number of temporal steps on which the patterns are present (spatial patterns have a depth of 0). The average number of nodes and the depth of the patterns selected by post-processing are usually less important than the same statistics for all the mined patterns. This may come from the fact that deep patterns are not diverse enough to be selected by the post-processing step which in turn suggests that, when the timeout is reached, the diversity of the mined pattern is not high enough. To further increase this diversity, stochastic search methods such as Monte-Carlo Tree Search [START_REF] Bosc | Any-time diverse subgroup discovery with monte carlo tree search[END_REF] could be integrated in our algorithm.

Conclusion and future work

We have presented GriMA2D+t, an algorithm to mine temporal sequences of 2D regular structures called grids. We have shown on experiments on a classical cellular automaton, the game of life, that GriMA2D+t can effectively extract spatio-temporal patterns in temporal grids. We have also shown that those patterns can be used as new features for classification algorithms and, in particular, to successfully predict the outcomes of cellular automata. This opens interesting new paths in the automatic analysis of the evolution of ecosystems and, in particular, to predict and control spatio-temporal spread of species in order to preserve biodiversity.

To further increase the efficiency of the classification process and scale to larger problems, we proposed to use a post-processing step that allows us to select a good subset of the mined patterns. In future work, we planned to directly mined a relevant subset of the possible patterns by using Monte-Carlo tree search methods. We also plan to apply this algorithm to analyze other temporal structures such as videos.

Fig. 1 :

 1 Fig. 1: Left: First three states of a 6 × 6 game of life modelled with a 2D + t grid. Living (resp. dead) cells are displayed in black (resp. gray). (x, y) coordinates are displayed in green and blue, respectively. Temporal edges are not displayed, but there is a temporal edge between each pair of nodes (i, j) such that xi = xj, yi = yj, and |ti -tj| = 1. Right: Two examples of spatio-temporal patterns (temporal edges are not displayed). P1 is isomorphic to a subgrid of the grid on the left (with translation T = (2, 4, -4) and rotation θ = -π/2). P2 is also isomorphic to a subgrid of the grid on the left. P2 is not isomorphic to P1 because the angle between edges (a, b) and (b, c) with xa = ya = y b = 2, x b = xc = 3, and yc = 1 in P1 is not preserved in P2.

Fig. 2 :

 2 Fig.2: Left: A 2D+t grid (temporal edges are displayed in red, node labels are displayed next to nodes, and all edges have the same label 0). Right: 3 codes for this grid (other codes may be built by changing the traversal).

  Pat All Pat 100 Pat All Pat 100 Pat All Pat 100 Pat All Pat 100

Table 1 :

 1 Accuracy results for the classification of states in T d n ∪ T a n . For each size n ∈ {20, 30, 40, 50}, the first line reports the number of frequent patterns |F n,k |, and the cell is colored in red if the 12 hour time-out has been reached and green otherwise; the second and third line report accuracy results with vectors of size |F n,k | and 100, respectively (if |F n,k | < 100, results are not given for vectors of size 100). Each line gives results for k = 1, 2, 5, 10, and 20, and with σ = 50% and 100% .

		k	1	2		5	10	20
	n		σ 50% 100% 50% 100%	50% 100%	50% 100%	50% 100%
		|F n,k | 673	22 23589	64 824616 2478 707743 96762 417724 213861
	20	All Pat 72.40 70.70 77.30 72.50 83.40 85.20 85.00 88.70 88.30 91.30
		100 Pat 72.70	75.80		83.80 83.50 84.10 87.80 85.60 89.50
		|F n,k | 662	18 28795	68 783701 2472 688546 99827 355381 252891
	30	All Pat 77.00 68.40 81.60 76.60 84.80 87.80 88.00 89.10 92.70 92.80
		100 Pat 74.10	79.90		84.40 86.90 88.40 89.40 91.80 92.20
		|F n,k | 667	27 38103	77 786619 4620 634501 178710 403411 246885
	40	All Pat 79.10 70.90 86.50 82.10 89.90 92.50 91.60 93.10 95.50 96.00
		100 Pat 77.10	84.40		86.80 90.10 89.40 93.60 94.30 96.80
		|F n,k | 740	26 46235	79 906209 4171 720779 206508 373600 282003
	50	All Pat 78.60 72.70 82.80 79.70 89.30 90.90 91.80 93.20 96.40 95.80
		100 Pat 77.90	84.20		88.50 89.40 89.90 92.90 91.90 96.40

Table 2 :

 2 Average and Maximum (in parenthesis) depth and number of cells for all patterns of F n,k or only those selected with post processing. to 0.008 seconds when k = 20 if we only count occurrences of the 100 patterns selected by post-processing.

Acknowledgements

This work has been supported by the ANR project SoLStiCe (ANR-13-BS02-0002-01)

Code 1

Code 2 Code 3 edge δ i j a L i L j L ij edge δ i j a L i L j L ij edge δ i j a L i L j L ij