Leila Salekhova
email: salekhova2009@gmail.com

Nail Tuktamishov

Abstract thinking and bilingualism: Impact on learning mathematics

Keywords: Abstract thinking, learning mathematics, bilingualism

There are many kinds of research on the relationship between mathematics and bilingualism, but only a few papers, which suggest that bilingualism may improve a person's ability to engage in more abstract or symbolic thinking processes. For example, in her work [START_REF] Planas | One speaker, two languages: Learning opportunities in the mathematic classroom[END_REF] argues that bilingualism can actually create opportunities for learners to deal more deeply with mathematical concepts. She observed a small sample of Catalan language learners interacting with dominant Catalan speakers while solving algebra problems in groups. The Catalan language learners used different problem-solving strategies (e.g., using a geometric approach to understand an algebraic expression) to overcome the lack of specific mathematical terminology in the academic language of instruction. The Catalan language learners also focused more on the meaning of mathematical terms than dominant Catalan speakers did because they were unfamiliar with the required terminology.

In recent years, more and more research studies have focused on the potential cognitive benefits of bilingualism. Several studies confirm that the experience of using more than one language can create unique opportunities in the bilingual brain, leading to cognitive benefits for bilinguals (Adesope, Lavin, Thomson, & Ungerleider, 2010). However, the exact nature of these benefits has proved difficult to determine in relation to specific subject contents.

On the other hand, the bilingual experience may provide other cognitive benefits. A number of researchers have supported the hypothesis that the constant switching of bilinguals from one language to another leads to an increase in executive functions [START_REF] Bialystok | Bilingualism: consequences for mind and brain[END_REF]. Other scientists have not found any advantages for bilinguals over monolinguals in executive functioning [START_REF] Paap | There is no coherent evidence for a bilingual advantage in executive processing[END_REF]. [START_REF] Cummins | Interdependence of first-and second-language proficiency in bilingual children[END_REF] have shown that bilinguals can learn new rules more effectively than monolinguals and have an advantage in meta-linguistic awareness. [START_REF] Gentner | Whither whorf[END_REF] confirms that knowledge representation depends on the language of instruction; hence, there may be negative consequences when knowledge is transferred from one representative system to another. In other words, negative effects are observed when the languages of learning mathematics and knowledge extraction differ. This was confirmed by [START_REF] Spelke | Language and number: A bilingual training study[END_REF], [START_REF] Campbell | Cognitive demands and second language learners: a framework for analyzing mathematic instructional contexts[END_REF], but also in work from our context developed by [START_REF] Salekhova | Cognitive costs of bilingual education: theoretical and empirical research[END_REF][START_REF] Salekhova | The basic conditions for development of mathematical speech of students in the process of bilingual education[END_REF].

Specific research by

A bilingual student may have problems understanding the essence of a mathematical problem if he or she is not familiar with the terms used, which are associated with abstract mathematical concepts. Conversely, there may be a positive cognitive effect due to multiple transpositions. They arise whenever an abstract concept is used and transferred from one representative system to another, when there are two different language terms in the language repertoire of a person. A number of studies have shown that the linguistic complexity of texts in mathematical achievement tests can negatively affect the performance of bilinguals for whom the language of instruction and the language of testing is not their mother tongue [START_REF] Haag | Second language learners' performance in mathematics: disentangling the effects of academic language features[END_REF]. However, it is unclear which specific features of language complexity contribute to this deficiency.

The present study explores whether bilingualism can potentially influence the development of abstract thinking that plays a crucial role in learning mathematics. The study's research question derives from the assumption made by the Russian psychologist Lev [START_REF] Vygotsky | Studies in communication: Thought and language[END_REF]. He believed that bilingualism could have positive consequences for the flexibility of human thought. He argued that the ability to express the same thought in different languages allows us to understand the symbolic function of words, to consider words in more abstract, semantic terms and to see that any particular language is only one semiotic system among many. Vygotsky studied issues concerning the relationship between bilingualism and flexibility of thinking following the awareness that bilinguals can be (dis)advantaged in traditional learning environments of Russia at that time.

Research context -bilingualism in Russia and Tatarstan

A large number of ethnic groups living within the boundaries of the Russian Federation is evidence of a complicated history of migrations, wars, and revolutions. In the process of its historical development, Russia has emerged as a multinational, multicultural and multilingual state. About 150 languages are spoken in the territory of Russia. This ethnic diversity has had a strong influence on the state education policy. The Russian Constitution guarantees all ethnic groups the right to maintain their mother tongues. Although Russian is the official language, some ethnic republics have the right to establish their own official languages besides Russian. The use of an ethnic language in education depends on the development of its written forms and literary standards.

Tatarstan is one of the ethnic republics of Russia, and Tatars constitute 53% of its population. There are two official languages -Russian and Tatar in Tatarstan. They are used for teaching almost all school subjects and the choice of the language of instruction depends on the school location (rural or urban) or the model of bilingual education (immersion, partial immersion, CLIL). Tatar is spoken by most of the people in Tatarstan as either a dominant or a second language. It plays a strong role in the construction of the Tatar cultural identity. Russian-Tatar, and Tatar-Russian bilingualism is widespread in Tatarstan if we consider bilingualism as the ability to speak two languages.

Experiment and materials

The present experiment sought to address the research question of whether bilinguals would outperform monolinguals on solving difficult symbolic math tasks. Algebra typically represents the students' first encounter with abstract mathematical reasoning and it therefore causes significant difficulties for students. Symbolic abstraction is a significant component of algebraic thinking. Algebra is a fundamental discipline in higher mathematics and plays a major role in the field of STEM education. The transition from arithmetic to algebra is a challenging task for learners, as algebraic thinking requires a shift from calculating exact values to considering relationships between quantities and operations with unknown values and variables.

One of the important topics of algebra is the study of functions, and many researchers favor teaching other algebraic topics, such as the solution of equations and inequalities based on functions. Students usually perceive functions as a tool to get answers but not as a mechanism to express the relationship between variables presented as symbolic abstractions.

Since abstract thinking represents the ability to process information, special symbolic algebraic tasks were developed in order to test for possible bilingual advantages in symbolic abstraction. Images and symbols are often used in abstract thinking, and their meaning derives solely from the thinking process. Algebraic functions are presented in an unconventional form; a new symbol is used to represent a certain sequence of basic mathematical operations. The task in our study has the following form: x&y=xy+x-y. What is 5&3? The solution of this task requires an abstract-symbolic approach and the understanding that the new symbol indicates the relationship between the variables and a certain set of mathematical operations (see Table 1).

Sample tasks

The first task with its solution is given as an example. The answers are provided for the remaining tasks.

x∞y=xy+x-y

What is 4∞5? 1.

x@y=(x-y) + (2x+3y) What is 4@2? 2.

x §y=(xy) (x+y) What is 5 §3? 3.

x€y=(x+y) 2 /(x-y) What is 4€2? 4.

x#y=x 3 -y +2x+3y What is 1#7? x?y=11x/y z?7=200 What is z? 3.

x•y=(x-2y)/y 4•5=z•10 What is z? 4.

(x)=x 2 -x (y) =(y-2) What is y?

Table 1: Symbolic mathematical tasks [START_REF] Mielicki | Bilingualism and symbolic abstraction: implications for algebra learning[END_REF] introduced the types of tasks in Table 1 for school pupils. We modified them to suit our adult participants in the research. The tasks in the current study were designed to test the development of participants' abstract thinking in a way that is intended not to depend on their previous academic experiences dealing with algebraic functions.

Participants

Sixty-two bilingual and monolingual first-year students of The Institute of Philology and Intercultural Communication of Kazan Federal University (Russia) aged 18 to 20 years participated in this experiment. They perceived this kind of symbolic problems as new because they were not familiar with the concept of binary algebraic operation.

Participants were categorized as early bilinguals (N=29) and monolinguals (N=33). Bilinguals who have had a prolonged exposure to more than one language before the age of 7 are called early bilinguals. Prolonged exposure is when both parents in the family speak a language other than Russian or when the individual attended a school in which he or she did not study in Russian. We selected only early bilinguals to identify and test positive effects based on previous studies examining the cognitive benefits associated with early bilingualism [START_REF] Bialystok | Bilingualism: consequences for mind and brain[END_REF]. Native speakers of Russian, who did not experience prolonged exposure to another language from early childhood, were considered monolinguals.

The language history of the participants was compiled with the help of interviews. In the sample of bilingual respondents, 57% indicated Tatar as their dominant language. Other dominant languages were Russian (18%), Mari (7 %), Udmurt (6%), Bashkir (4%), Tajik (3%), Uzbek (2%), Kazakh (1%), Azerbaijani (1%), and Chinese (1%).

Researchers have tried to measure dominance for many years. Some scientists use such criteria as pronunciation and vocabulary to evaluate a bilingual's languages. Others apply various tests such as naming images, recognizing words, executing a command, or translating sentences from one language to another. Based on these, the experts rate the dominant language of the participant. However, these different approaches are criticized for primitivism in the analysis of language knowledge and bilingual behavior, as the two languages are evaluated independently. We preferred an approach in which bilinguals themselves assess their level of bilingualism. We defined the dominant language as one in which the bilingual has reached an overall higher level of proficiency at a given age, and/or the language used more frequently, and in a wider range of domains.

Bilingual participants were asked to describe their level of proficiency in the dominant and the second language on a scale of 0 to 10 (0=no, 10=perfect) for "speech activity" and "understanding". Bilinguals reported similar levels of proficiency in the dominant language (M=8.36; SD=1.48) and in the second language (M=8.49; SD=1.24) for "speech activity". Similar levels were reported in the dominant (M=8.66; SD=1.34) and second languages (M=8.88; SD=1.03) for "understanding".

Russian was the dominant language of all the monolinguals. The average age of onset for second language acquisition was 7.13 (SD=1.53). Unlike bilinguals, monolinguals reported a higher level of proficiency in speaking Russian (M=9.61; SD=0.93), and a lower level in their second language (M=2.23; SD=1.16). Monolingual participants also described their level of understanding in Russian (M=9.65; SD=0.76) as higher than their second language (M=2.97; SD=1.57).

Procedures and results

Subsequently, the participants were offered to solve symbolic mathematical tasks (see Table 1): four types of symbolic math tasks of increasing complexity, consisting of four items. The solution to the first problem in each variant was given as an example. After completing each of the remaining three tasks, participants were informed whether they had answered correctly or incorrectly. Then the participants solved 12 more tasks of three levels of difficulty (easy, medium and difficult). The level of difficulty was determined by the number of new characters in the problem, as well as the number of operations required to solve the problem.

The tasks were presented in increasing complexity, and all participants performed the same tasks in the same sequence. Tasks were shown on the computer screen; the participants recorded the answers on a special worksheet. They were asked to make as many transformations and calculations as possible mentally but also had a pencil and paper, which they could use if necessary. Participants performed the tasks at their own pace and received one point for each correct answer.

Figure 1 shows the distribution of the number of correctly solved symbolic math tasks at each level of complexity by monolinguals and bilinguals. It signals minor differences between bilinguals and monolinguals in favor of the latter in solving easy and medium level problems. However, significant differences emerge in the other sense in solving symbolic math tasks of high complexity. A paired-samples t-test was conducted to determine the effect of bilingualism on solving symbolic math tasks. There was no significant difference between monolinguals (M=0.97; SD=0.18) and bilinguals in easier tasks (M=0.79; SD=0.41); t(60)=2, p=0.05. No evidence exists that bilingualism has an effect on solving easy symbolic math tasks that require abstract reasoning. Similarly, there was no significant difference between monolinguals (M= 0.75; SD=0.44) and bilinguals in medium tasks (M=0.83; SD=0.38); t(60)=2, p=0.05. Thus, no evidence exists that bilingualism has an effect on solving medium symbolic math tasks. However, there was a significant difference between the group of monolinguals (M=0.1; SD=0.034) and the group of bilinguals in the solution of difficult math tasks (M=0.22; SD=0.041); t(60)=2, p=0.05. Hence, we concluded that bilingualism influences the ability to solve difficult symbolic math tasks requiring advanced abstract thinking.

Bilinguals in our study performed better, particularly with the difficult problems. The advantages observed here illustrate that bilinguals may be faster to adapt to the demands of novel math tasks.

Higher performance suggests that bilinguals may have some advantage in implementing the understanding of new symbolic rules in a new context. These results show that bilinguals can have superior skills in flexible selection and application of new procedures compared to monolinguals.

Discussion

Most prior research focuses on the problems encountered while learning mathematics and teaching mathematics to bilinguals and students whose home language is not the language of instruction. However, as the current study shows, bilingualism can facilitate the development of abstract thinking, which is consistent with Planas (2014). Since our sample was small, we cannot make global conclusions about the advantage of bilingualism in abstract reasoning. However, our research confirms to some extent the results obtained by [START_REF] Mielicki | Bilingualism and symbolic abstraction: implications for algebra learning[END_REF] for USA college students that bilinguals solve better difficult mathematical problems that require advanced abstract thinking. Our study found that bilingual students coped better with difficult abstract mathematical problems. This is how the synergetic effect of bilingualism and experience in abstract thinking manifested itself; it became obvious in those tasks that contained more ambiguity.

It is believed that executive functioning plays a crucial role in solving problems and previous studies have shown the benefits of executive functioning among bilinguals [START_REF] Adesope | A systematic review and metaanalysis of the cognitive correlates of bilingualism[END_REF][START_REF] Bialystok | Bilingualism: consequences for mind and brain[END_REF]. The advantage of bilinguals in the development of executive functions could also explain the results obtained in this experiment, because memory, inhibitory control, fluid intelligence, mental flexibility and selective attention are involved in the abstract reasoning process while solving abstract math tasks.

One of the drawbacks of our investigation is the assumption that the monolingual and bilingual groups used in the study were truly comparable in every aspect, except for their linguistic skills. [START_REF] Paap | There is no coherent evidence for a bilingual advantage in executive processing[END_REF] expressed concern that some previously identified differences between monolinguals and bilinguals might actually be the result of differences in socioeconomic status between samples. Since socioeconomic status is known to be associated with different cognitive skills, it is important to ensure that monolingual and bilingual samples come from the same socioeconomic background and share other important family characteristics (e.g., parents' education). This fact should be noted, thus an alternative explanation based on the status differences among the bilingual and monolingual participants cannot be ruled out.

Teachers and educators need to be aware of the strengths and weaknesses of bilingual students and teach them accordingly. The differences between bilinguals and monolinguals, if any, are specific to a particular task and can be quite subtle. Further research can explain our experimental results, which enrich the growing research on the complex picture of the existing effects of the bilingual experience and the strategic intellectual resource of bilingualism when learning mathematics.

Figure 1 :

 1 Figure 1: Performance of bilinguals and monolinguals on symbolic math tasks

Acknowledgement

Our work was done in accordance with the Russian Government Program for Competitive Growth of Kazan Federal University.


Marc Sauerwein
email: sauerwein@math.uni-bonn.de

Teaching mathematics in an international class: Designing a path towards productive disposition

Keywords: Elementary algebra, refugees, genetic principle, figurate numbers, heterogeneity

Introduction

In Germany, IVKs (German abbreviation for International Preparation Class) have been established since 2015 to structure the education of foreign pupils who migrated to Germany. Most pupils are refugees from conflict and war zones all over the world, with medium to non-existent German language skills. In general, pupils can attend these classes for up to two years (depending on the state), and the goals of these classes can be very diverse: different school degrees, transition into the regular educational system or qualifying for the start of an apprenticeship. As in every class there is a natural diversity with respect to the pupils' mathematical giftedness and abilities. However, this natural heterogeneity is intensified by a larger age spectrum (of at least 8 years) and previous experiences in the pupils' various homelands and the conditions of their flight to Germany.

Modelling strands of heterogeneity

In the tradition of Wittmann's view of mathematics education as a 'design science' [START_REF] Wittmann | Mathematics education as a 'design science[END_REF], I identified, in cooperation with various experienced teachers, different strands of heterogeneity in a design research project with multiple implementation cycles [START_REF] Sauerwein | Figurierte Zahlen als produktiver Weg in die Mathematik[END_REF]. A few of these (provisional) strands serve as a basic framework for the reasoning in the article to emphasise the crucial differences between teaching the IVK and regular classes:  Communicative strand: There is no common daily language -neither for informal communication nor for discussions in the classroom. Learning German as a foreign language thus is not only restricted to the classrooms: It encompasses the complete daily routine. The pupils' knowledge of the German language is in-between the levels A1 and B2 (with respect to the CEFRL); some do not even cover A1.

 Emotional strand: The linguistic problems are not separated from daily life. This can contribute to an overwhelming frustration of feeling inadequate in nearly every respect of everyday life. Even prior to our project, we observed many pupils approaching mathematics with more courage than other subjects, where they remained passive or even missed lessons.

 Mathematical strand: The prior knowledge of mathematics is very individual and reaches from a rudimental number sense in in the number range 1-10 up to twelve years of mathematics education. Moreover, the primary focus in the pupils' previous mathematical education seems to lie on the symbolic languages of arithmetic and algebra.

 Cultural strand: Regular school attendance is not part of every culture. In some countries, the pupils are expected to contribute to their families' income. Nevertheless, all pupils had a positive attitude towards school and were grateful for every help. However, for some pupils, a structured week with a time schedule and the learning commitments were new and resulted in an overextension. Rapid changes between gratitude and frustration were observable.

 Institutional strand: The school system in Germany probably differs from the pupils' experiences in their respective homelands. According to what some pupils tell me, teaching here is less authoritarian and contains more independent working phases; learning by heart is less dominating. This implies that lessons for these pupils are more demanding as they ask for creativity, self-initiative or mathematical discourse.

Problematic consequences

Although these strands are not explicitly addressed in class, they influence teaching in many subtle ways. For example, different beliefs of mathematics and its teaching seemed to appear in the IVK. These expressed themselves in the following observed misconceptions in practice:

 In mathematics, there is only one correct solution and it's either the teacher's or the calculator's job to decide.  Mathematics is a finished product and consists mainly of mimicking the teacher's solutions in a formal way with no deeper insights or discussions (in class).

This experience cannot certainly be generalised towards a statement about non-European school systems. These attitudes towards school in general and views on mathematics can prevent the pupils from building sustainable mathematical concepts. On top of that, they can cause challenges with respect to the integration into regular classes.

Research question

The description of different strands of heterogeneity does not imply that these could be addressed separately, as posed in Gorgorió and Planas (2001, p. 28): "It is very difficult to disentangle the social and cultural conflicts of a multiethnic mathematics classroom from the language issues."

As argued before, the above-mentioned intertwined strands influence the teaching. For simplicity we assume that they characterise the heterogeneity in the IVK. The context of an IVK is fundamentally different to bilingual classrooms (e.g., in Malta, [START_REF] Farrugia | Young children's appropriation of mathematical discourse: Learning subtraction in a plurilingual classroom[END_REF]in Catalonia-Spain, Planas & Setati, 2009;in Germany Schüler-Meyer, 2017). In general, one cannot expect to have a common language. The broad research question from the beginning can be rephrased to: Can figurate numbers help to address the special situation within an IVK in a holistic way to stimulate a meaningful learning of elementary algebra? In the next section, I address the topic of figurate numbers by building partly on data and findings of my doctoral dissertation [START_REF] Sauerwein | Figurierte Zahlen als produktiver Weg in die Mathematik[END_REF].

Figurate numbers

"If human actors invite the object to be a part of the discourse, objects can challenge the students to find a new language […]. This aspect is of special interest from a didactical point of view.

Objects cannot only relieve students on the language level, but also challenge them. They can be 'supporters' in the development of mathematical thinking and of a precise mathematical language." [START_REF] Fetzer | The interplay of language and objects in the mathematics classroom[END_REF], p. 1392) Inspired by typical generalising approaches to algebra (e.g. [START_REF] Mason | Expressing generality and roots of algebra[END_REF] we define a figurate number as a sequence of dot patterns including the corresponding integer sequence: As the definition is based on sequences and thus incorporating the (hidden) rule of construction, Figurate numbers demand naturally for a pursuit to find this rule. In keeping with [START_REF] Bruner | Towards a theory of instruction[END_REF] three modes of representation of knowledge, enactiveiconicsymbolic, figurate numbers possess iconic and symbolic components. The iconic nature allows the pupils of the IVK to find linguistically more accessible common ground for mathematical discussions and development.

Such workshop languages [or intermediate languages] which are characterised by a high vividness, situatedness and grammatical looseness, which are often supported by gestures and which may hardly be comprehensible to non-participants, will emerge inevitably from themselves and their communicative importance must be highly appreciated. (Winter, 1978, p. 13, my translation)

It should be noted that, although the language is more accessible, it does not result in a cutback with respect to the richness of its mathematical content. Similarly, [START_REF] Moschkovich | Supporting the participation of English language learners in mathematical discussions[END_REF] implicitly criticises some teaching practices which limit the pupils' opportunities by the early introduction of compulsory mathematical vocabulary:

"[…] [L]
anguage learners can and do participate in discussions where they grapple with important mathematical content.

[…] But it is only possible to uncover the mathematical content in what students say if students have the opportunity to participate in a discussion and if this discussion is a mathematical one." (Moschkovich, 1999, pp. 18-19)

Practical perspective

Each of the four implementations of the learning environment Figurate Numbers started with the dot pattern in Figure 1 which was easily continued by all pupils in an iconic way. In almost all cases with one interesting exception mentioned belowthe resulting dot pattern was a -rectangle. Since not all pupils knew the word for rectangle, they used gestures to distinguish between columns and rows while saying a number, meaning the number of dots in that particular part of the dot pattern. In this way, they were eventually able to describe the pattern and its underlying rule of construction:

-The next dot pattern consists of three horizontal rows with four dots each.

-The next dot pattern consists of four of these columns.

-One always adds the first dot pattern.

-The right dot pattern consists of the preceding two.

The first three descriptions imply that the next dot pattern consists of 12 dots. From there on, many pupils continued the number sequences in a symbolic mode, thus identifying it with the multiples of 3. Although this change of mode of representation seems to be economic, one loses some structure: The expressions , and all yield , but each of them also encodes a certain perspective onto the iconic representation, namely how it is structured and consequently counted.

What is the meaning of the fourth description? The pupil's idea incorporates the triple Fibonacci-Numbers. Cutting the dot pattern horizontally it is easily be seen that the pupil's construction is the law of construction of the Fibonacci-Numbers . Pupils were confronted with the fact, that different views on the given data permitted different and equally legitimate solutions; while the multiples of three later offered an obvious description as a closed term the pupils discovered the essential truth that mathematical observation, if taken seriously, might lead to open ends which cannot be immediately tied up on the basis of available knowledge. Therefore, it is fair to say that this insight was achievable due to the different perspective on the innocent looking figurate number. The filling glass with its richer iconic structure allows more different approaches to counting. Pupils introduced the notion of "negative points" (the missing points in the lowest row) to arrive at "recipes" like , they observed symmetry (arriving at ). To communicate these ideas the pupils used gestures and inscriptions into the dot patterns, thus enriching themas diagrams -with a basis for socially accepted reasoning (in the sense of [START_REF] Dörfler | Diagramme und Mathematikunterricht [Diagrams and mathematics lessons[END_REF]. All these views are potential starting points for generalisations. When changing the iconic pattern is allowed too (for instance changing the position of the two points to a position below the first two columns), more terms can be found, and the observation of equivalence can be generalised to consider terms as objects for further studies and in this context understanding equality among terms on a level beyond syntactical limits.

Consider now the filling glass:

When in a later state, pupils manipulate terms according to algebraic rules they can, if necessary, find in adapted iconic representations and the study of their geometric transformability into each other a reliable basis for their mathematical discourse.

Meta perspective

In the beginning of each implementation of our project we were met with the pupils' objection that these dot patterns were nothing but a puzzle for children and no mathematics at all. This pupils' prejudice, which can well be understood from the mathematical and institutional strands explained above, in the course of our project changed into a qualified appreciation of the subject.

Presenting patterns of small dots (i.e. the iconic representation of the first few elements of a figurate number) proved to offer several possibilities andreferring to our intentionsadvantages, which are closely related to their "simplicity":

 Each pupil can count the dots; hence the figurate numbers create a productive entry for different levels. Since in our project every pupil had a certain fluency in counting activities and basic arithmetic (even if limited to a certain range of numbers) the low-threshold accessibility of our project could be taken for granted.

 No tools such as calculators or other digitals tools are needed. Only a piece of paper, a pencil and a rubber are needed to gain access to the dot patterns. Taking up on [START_REF] Mason | Expressing generality and roots of algebra[END_REF] distinction of looking at vs. looking through, the plainness combined with a thorough investigation offers the chance to look through the particular pattern and grasp the general rule. Thus, the picture becomes literally a "diagram" [START_REF] Dörfler | Diagramme und Mathematikunterricht [Diagrams and mathematics lessons[END_REF] and a tool for new insights.

 All but one pattern which we used in our design project corresponded to linear counting expressions. From a mathematical viewpoint these expressions are rather elementary. As this form of representation is new to the pupils, they have to accept and discover the iconic representations as worthwhile objects of further studies and later the possibility to switch between different representations, for example between the dot pattern and the number (maybe written as sum or product) as a tool to prove the validity of an algebraic argument.

This outlined simplicity yields a situation where pupils can express their own ideas even though their skills of the German language would not allow them to do so. The stimulated discussions between the pupils were making use of a certain intermediate language [START_REF] Winter | Umgangssprache -Fachsprache im Mathematikunterricht [Colloquial language specilized language in mathematics education[END_REF]: The iconic representation becomes the basis for discussion enriched with gestures and rudimental symbolic notations. Winter emphasises the necessity of this intermediate language as a foundation for the symbolic language. Thus, he argues, one should not rush through this stage.

Epistemological perspective

An historical and epistemological analysis of [START_REF] Kvasz | Patterns of change: Linguistic innovations in the development of classical mathematics[END_REF] suggests that figurate numbers were a crucial step for the development of the symbolic language of algebra. Kvasz points out that there was no direct development from arithmetic to algebra as Frege proposed (1891). Instead, there were two instances of a certain pattern of change which he calls re-coding: Considering arithmetic and algebra as symbolic languages and geometry as an iconic language, recoding can simplistically be seen as change of the mode of representation. The first re-coding is strongly related to the Pythagoreans who invented figurate numbers by using ψῆφοι (calculi). A

Arithmetic

Geometry Algebra first detailed account on figurate numbers can be found in Nikomachos' Introduction to Arithmetic (D'Ooge, 1926) where he introduces polygonal and polyhedral numbers apart from the two fundamental sequences of quadratic and oblong numbers (Figure 4). By the inscribed gnomons it is easily possible to continue each sequence. The second re-coding is the symbolisation of the notion of a variable which was only implicitly used as a line segment of indefinite length, thus freeing the variable from three-dimensional space. The analysis of Kvasz and his view on the language of mathematics with its different stratifications where each layer has its own potentials (or cognitive aspects), yield the necessity to widen the definition of algebra as calculating with lettersit is more than just arithmetic with letters. The introduction of the symbol notation is only the first step to a new symbolic language [START_REF] Kvasz | Language in Change. Fernando Gil International Prize[END_REF]. It also involves new ways of operating with the newly introduced symbols. Therefore, one can conclude that typical mathematical activities such as generalising, conjecturing, proving, etc. are part of the use of the language of algebra.

Communicative and linguistic connotations of figurate numbers

The notion of language occurs in different contexts within this report. These contexts are strongly related to different aspects of figurate numbers. On the one hand, there is language as a medium of communication. According to the communicative strand this function influences all teaching in the IVK. In this sense of language, figurate numbers serve as a tool for discussion of pupils without a common language. On the other hand, they act as a vehicle in a process of conceptualisation, that is, the conceptualisation of the iconic manipulations which lead to language of elementary integer algebra in the sense of [START_REF] Kvasz | Patterns of change: Linguistic innovations in the development of classical mathematics[END_REF].

In contrast to the perspective of Kvasz which describes the development of mathematics, the individual process of learning algebra is not linear and straightforward. From a didactical point of view, the pattern of re-coding should be used in both ways. Consequently, figurate numbers become a mediating tool between the languages. In particular, the interplay between the iconic and symbolic components of a figurate number turned out to be fruitful. Figurate numbers opened a context where pupils could conjecture, generalise, prove, discuss, etc.

Résumé

The aforementioned examples from practice showed that figurate numbers can address the special situation in an IVK by seizing the mathematical and communicative strands: The appearance of different counting strategies led to different counting expressions for the quantity of dots and ultimately to the quest to prove equivalence of different solutions on a legitimate and more concise basis than merely counting dots in examples. The iconic form of the figurate numbers served as a sustainable and workable representation compensating the lack of a common language in the class.

Furthermore, the other strands of heterogeneity were confronted: The pupils in the IVK were not familiar with the possibility that there could exist various correct solutions and that mathematics could consist of more than numbers and symbols. Thus, the opportunity arose to tackle the mentioned misconceptions. Moreover, the correctness of a solution was not judged by the teacher; it followed from a consistent argument based on different perspectives of the structure of figurate numbers. It could be observed that the sketched approach to figurate numbers was not only addressing the strands of heterogeneity and some of their consequences but also contributing to the ambitious goal of the pupils' empowerment.

The strands of heterogeneity cannot be treated separately as they are strongly intertwined. Nevertheless, the initially observed positive attitude within the IVK towards mathematics seemed to be an appropriate starting point: This inclination of the pupils encouraged me to develop it into a "productive disposition" (NRC, 2001, p. 116).

The figurate numbers here act as a generic example for the context of elementary algebra. It could be worthwhile looking for other subject matters with similar potential with respect to mathematical and linguistic development in this social and cultural context of an international class for refugees.

  Figure 1:

  Figure 2:

Figure 3 :

 3 Figure 3: The Re-coding Arithmetic -Geometry -Algebra

Figure 4 :

 4 Figure 4: The quadratic and the oblong numbers

Acknowledgments

I want to thank the pupils of the IVK for their cooperativeness and the Otto-Kühne Schule in Bonn for all the support and opportunities to conduct the research. Moreover, I would like to express my gratitude for the long discussions with Carl-Peter Fitting leading to the report in its present form.


Alexander Schüler-Meyer
email: a.k.schuelermeyer@tue.nl

Susanne Prediger

Henrike Weinert

Which factors coincide with mathematical learning gains in bilingual classrooms? German language proficiency and mixed language use

Keywords: Multilingual math learning, teaching intervention, supply-use-model, learning gains

Although bilingual mathematical learning opportunities have often been requested for multilingual students, little quantitative evidence has been provided that activating two languages has measurable effects on learning gains. This study uses data from a bilingual teaching intervention to investigate which factors coincide most with the mathematical learning gains in conceptual understanding of fractions. Students' individual and family characteristics have been assessed and participation and language use have been coded in ~95h videotaped teaching-learning processes. A regression analysis shows that students' learning gains can best be explained by students' German language proficiency and their use of Turkish and mixed mode, while talking time did not coincide with learning gains. Thus, the connection of languages seems to be even more important for mathematical learning gains than the isolated use of home languages or active participation.

Research gap on factors for effective multilingual mathematics learning

Many qualitative case studies illustrate benefits of activating multiple languages in mathematics classrooms [START_REF] Planas | One speaker, two languages: Learning opportunities in the mathematics classroom[END_REF]. Multilingual resources have been shown to support mathematics learning and engaging students in discursive practices of problem solving, when drawing on multilingual everyday experiences [START_REF] Domínguez | Using what matters to students in bilingual mathematics problems[END_REF]. In fact, multilingual resources can support problem solving processes in general [START_REF] Wagner | Vernetzung von Sprachen und Darstellungen in einer mehrsprachigen Matheförderung [Relating languages and representations in a supportive multilingual teaching intervention on fractions[END_REF], especially when students are highly proficient in their languages [START_REF] Clarkson | Australian Vietnamese students learning mathematics: High ability bilinguals and their use of their languages[END_REF]. Furthermore, the activation or acknowledgement of students' multiple languages can have a positive effect on students' agency [START_REF] Norén | Agency and positioning in a multilingual mathematics classroom[END_REF]. Summing up, multiple positive effects have been qualitatively identified. However, little quantitative evidence could so far be provided that bilingual interventions have measurable effects on the mathematical learning gains [START_REF] Reljić | A meta-analysis on the effectiveness of bilingual programs in Europe[END_REF].

In order to close this research gap on quantitative evidence, the project MuM-Multi conducted a randomized control trial with Turkish-German seventh graders comparing a bilingual and a monolingual German intervention aiming at conceptual understanding of fractions in small group teaching (Schüler-Meyer, Prediger, Kuzu, Wessel, & Redder, 2019a). The analysis showed that on average, mathematical learning gains in the bilingual intervention were comparable to the corresponding monolingual intervention. The differential analysis of learning gains shows that they were significantly higher for the students with high Turkish language proficiency (ANOVA: F (group x time) = 4.49, p < .01, ² = .16). Additionally, a strong variance in learning gains was found for the different small groups (for which Cohens d varied between -0.12 and 2.22). A first hypothesis was that these differences might be traced back to different intensity in Turkish modes.

Hence, this study systematically investigates the factors contributing to the effective use of multiple languages in mathematics classrooms. For this, a video analysis was conducted to capture students' language use (Schüler-Meyer, [START_REF] Schüler-Meyer | Bedingungen für zweisprachige Lernangebote -Videobasierte Analysen zu Nutzung und Wirksamkeit einer Förderung zu Brüchen [Conditions for bilingual learning opportunitiesvideo-based analyses of usage and efficacy of an intervention on fractions[END_REF] with this research question:

Which factors in individual and family characteristics and students' language use significantly coincide with students' learning gains in the bilingual teaching intervention?

This research is framed by the supply-use-model [START_REF] Brühwiler | Effects of class size and adaptive teaching competency on classroom processes and academic outcome[END_REF][START_REF] Helmke | Unterrichtsqualität und Lehrerprofessionalität [Teaching quality and teacher professionalism[END_REF], which is outlined in the next section, before the methods of the study and its results are presented.

Research framework: Supply-use-model for quantitatively capturing potentially relevant factors for bilingual interventions

The supply-use model [START_REF] Brühwiler | Effects of class size and adaptive teaching competency on classroom processes and academic outcome[END_REF][START_REF] Helmke | Unterrichtsqualität und Lehrerprofessionalität [Teaching quality and teacher professionalism[END_REF] has often proven to be powerful in quantitative classroom research for modelling the factors that influence whether a supplied learning opportunity is really used to its full potential by students in a classroom and how this impacts the learning outcome. The assumption is that the relations between supply, use and outcomes (learning gains) can be influenced by context factors or students' individual or family characteristics. Figure 1 shows the general model and its adaptation for the current research (justified in detail in [START_REF] Schüler-Meyer | Bedingungen für zweisprachige Lernangebote -Videobasierte Analysen zu Nutzung und Wirksamkeit einer Förderung zu Brüchen [Conditions for bilingual learning opportunitiesvideo-based analyses of usage and efficacy of an intervention on fractions[END_REF]. Following the research question, we investigate the learning processes of multilingual seventh graders with equal conditions in the language context (cf. Schüler-Meyer et al., 2019a): All students stem from multilingual Turkish-German families (all factors held constant are colored in light grey in Figure 1), their shared language context is shaped by only monolingual math classroom experiences and the limited prestige of their home language Turkish. All small groups are taught by teachers which share many characteristics and preparations. They follow the same bilingual intervention with equal design principles and teaching materials, thus the supplied learning opportunities are held constant in the bilingual intervention on fractions.

The research question focuses on the individual use of supplied bilingual learning opportunities (in terms of percentage of individual talking time and language use) and students' characteristics. 'Percentage of individual talking time' was chosen as a use factor because active participation has often been qualitatively described as influencing learning gains [START_REF] Gresalfi | Constructing competence: An analysis of student participation in the activity systems of mathematics classrooms[END_REF]. The second use factor concerns individual language use: As all prior math experience was monolingual German, it was crucial to control whether students really use both of their languages. Like for most multilinguals, the bilingual modes are expected to be characterizable by mixed modes (e.g. various forms of Code-switching between German and Turkish), also for the second-and third-generation Turkish immigrant students [START_REF] Auer | Code-switching/mixing[END_REF].

Methodology of the study in the supply-use-model

Design of the bilingual teaching intervention

The investigated bilingual Turkish-German teaching intervention was designed to foster the conceptual understanding of fractions, which encompasses the part-of-whole concept, equivalence, and order of fractions. The intervention consists of five 90-minute weekly sessions and builds on three principles for fostering multilingual learning (cf. Schüler-Meyer et al., 2019a): (1) Providing rich contexts and problem tasks for language production [START_REF] Domínguez | Using what matters to students in bilingual mathematics problems[END_REF]; (2) macro-scaffolding, which included encouraging the use of Turkish with bilingual teaching material, bilingual teaching practices (e.g. revoicing), explicitly addressing and developing the Turkish and German academic language, and (3) systematically relating registers [START_REF] Prediger | Purposefully relating multilingual registers: Building theory and teaching strategies for bilingual learners based on an integration of three traditions[END_REF].

Design of the overarching project MuM-Multi and video corpus for the current study

The randomized control trial (Schüler-Meyer et al., 2019a) was conducted in a pre-post-follow-up design with conceptual understanding of fractions as dependent variable. The family and individual characteristics mentioned in Fig. 1 served as control variables and the contrast between mono-and bilingual intervention served as the independent variable. The groups in the bilingual intervention were taught by trained Turkish-German speaking preservice teachers in small groups of 2-5 students, for 5 sessions of 90 minutes. This study focuses only on the bilingual intervention, for this 13 x 90 minutes video material of the third session was coded from 13 small groups. The third session in the middle of the intervention was chosen because teachers had developed their routines, and the students had a chance to overcome first barriers of using Turkish in the classroom.

Measures for data collection for the individual and family characteristics

At three measurement time points, several measures were administered:

 Measures for students' conceptual understanding of fractions. The test has 28 items to test for the understanding of the part-of-whole concept, equivalence, and order of fractions. The test has a satisfactory internal consistency with Cronbach's =.83 (28 Items, N=1120).  Measures for students' socioeconomic status and general cognitive abilities. Students' socioeconomic status was measured with the economic and reliable book scale (r=0.80). The students' fluid intelligence was measured using an adapted matrix test BEFKI 7 (with Cronbach's =.763 in the initial full sample of N=1124).  Measures for German and Turkish language proficiency. Students' language proficiencies were measured by C-tests, which provide an economic and valid measure based on cloze texts. The C-tests are highly reliable: the Turkish C-Test with =.874 (N=254) and the German C-Test with =.774 (N=1122). Students' German academic language proficiency is measured with a test which assesses the use of nominalizations and other academic language features (BiSpra).

Initial sample and sample of the bilingual teaching intervention

The initial full sample encompasses N=1124 seventh-grade students from twelve secondary schools (48% female and 52% male). From the 303 Turkish speaking students, a subsample of 254 students self-selected themselves by accepting to work on the Turkish C-test (Table 1). For the intervention, students with a low conceptual understanding of fractions were selected (Cut-off of 28 points in the fraction test). This group consisted of N=128 students who were then stratified along the control variables and randomly assigned to the intervention groups. The sample of this study consisted of n=35 students who participated in the third sessions of the bilingual teaching intervention on fractions. Due to missing follow-up data, the statistical analysis has a sample of n=33 students.

Methods of data analysis I: Coding the video corpus of the third intervention sessions

All utterances of the students (S1-S4) and teachers (T) were categorized turn-wise with respect to (a) speaker and starting / ending time of the utterance, and (b) language use (Turkish, German, mixed mode). Utterances with one switch from one language to the other were splitted and each part categorized. Utterances with borrowings or multiple code-switchings were coded as mixed mode. This categorization captures lexical aspects of language, while grammatical mixes are left out. The duration of the utterances is used for operationalizing the two use factors.

 Percentages of talking time:

The operationalization of participation has to account for the fact that students in differently sized groups have different allotted talking times. Two students and a teacher theoretically have 30 min. of talking time each, while four students would only have 18 min. Hence, the allotted talking time is the theoretical talking time per group member with x group members, hence 90/x. The individual percentages of talking time is the share of actual talking time from the allotted talking time (which can be bigger than 100%). Students on average participated 90,45% of the allotted talking time. The averages in the groups are between 72% and 110%, and the individual participation varies between 20% and 210%.

 Modes of language use: The individual language use is operationalized as the share of Turkish, German and mixed modes from the total individual talking time. Table 2 shows the descriptive data for the modes of language use.

Methods of data analysis II: Hypotheses and model for the statistical data analysis

For statistically investigating the research question, the following hypotheses were validated by correlations: The learning gains of the bilingual intervention is connected to H1 the percentage of talking time; H2 the Turkish language use; H3 the language proficiency in Turkish and German.

For comparing the influences of factors, a regression analysis was conducted with the software R (https://cran.r-project.org/) for validating Hypothesis H4: Among the different factors, some exist which coincide significantly with the learning gains. If a Shapiro-Wilk test confirms the normal distribution, Pearson's Product-moment correlations r were determined, if not, Kendall's Tau τ was used. To rule out an effect of the groups on the investigated variables, the intra class correlation ICC was determined and tested for significance with boot-strapping.

Results

Descriptive findings for the modes of language use

Table 2 shows that both, teachers and students, participated in bilingual modes, i.e. in a mixed mode or in Turkish. On average, 52% of the overall talk time was Turkish or mixed (72% teachers, 30% students). Hence, there is a high degree of productive and receptive use of Turkish. Furthermore, a large percentage of the talk time is in mixed mode, so that both teachers and students seem to use every-day bilingual practices of code-switching and -mixing. However, individually, there are substantial differences in the language use. The group averages between teachers and students also vary strongly. This suggests that individual preferences of language use might in part be a result of group-specific practices of activating multiple languages. Nevertheless, in a teaching intervention in which teachers consequently invest in the use of Turkish and mixed language, these numbers show that students can nevertheless be engaged in bilingual learning processes, compensating the low prestige of Turkish and the previous monolingual education.

Findings of influences of different factors

For investigating Hypotheses H1-H3, correlations were determined between the learning gains (difference between pre-test and follow-up-test) and the potential factors: The correlation with the German language proficiency is τ = 0.38, with the Turkish and mixed modes in language use it is τ = 0.32, these are two relatively high correlations. For the language use of only Turkish modes, the correlation is low with τ = 0.14. No correlation exists with the percentage of individual talking time where τ = -0.03. Thus, the hypothesis on relevance of active participation must be refuted.

To investigate the joint effects of the different factors on the learning gains (H4), a regression analysis with a stepwise model selection was performed (Table 3). As the learning gains of the small groups provide a non-significant ICC-value of 0.29 (p > .05), a multiple linear regression model is adequate. Model 1 with all variables, while being complete, is not significant. A stepwise model selection results in a significant Model 2 (F(2,30)=7.973, p < .01), which includes German language proficiency as significant factor for learning gains (p < .05). In comparison, Model 3 and 4 are models with single variables, namely German language proficiency and the use of Turkish and mixed mode, respectively. Overall, Model 2 has the best model accuracy with R 2 (korr)=0.30. This model shows that a higher German language proficiency leads to higher learning gains: One additional point in the C-test leads to higher learning gains of 0.34. Also, the use of Turkish and mixed language is a relevant factor: 10% more use of Turkish and mixed language leads to 0.69 more points in the learning gains.

In sum, the learning gains in the bilingual teaching intervention coincide with the German language proficiency, but not the Turkish language proficiency or the German academic register. This student characteristic is combined with the use factor 'use of Turkish and mixed mode', which also shows a strong connection to learning gains.

Summary and discussion

This study contributes to the research discourse on multilingual mathematics learning as follows:

 Within usual language policies of monolingualism, the percentage of the mixed-language mode used by teachers and students is remarkable [START_REF] Norén | Agency and positioning in a multilingual mathematics classroom[END_REF]. By implementing certain principles for activating multiple languages, multilingual students can be fostered to activate their multiple languages in mathematical teaching learning situations, despite a language context which devalues the immigrant language Turkish.

 The finding that the share of Turkish and mixed language use in students' utterances best explains the learning gains in the bilingual teaching intervention (together with German language proficiency) is a quantitative evidence for many qualitative results which show how multilinguality can be a resource in learning processes [START_REF] Planas | One speaker, two languages: Learning opportunities in the mathematics classroom[END_REF][START_REF] Norén | Agency and positioning in a multilingual mathematics classroom[END_REF].

 The students' percentage of individual talking time is not correlated to the learning gains. This confirms skepticism on too simple conceptualizations of active participation as talking time.

 In light of studies illustrating how conceptual tasks involving problem solving are especially accessible to multilingual students by means of certain discursive practices like discussing (e.g. Dominguez, 2011), the finding that students' German language proficiency significantly coincides with the growth of conceptual understandings may hint at a more complex relation between conceptual tasks and their utilization in discursive practices, and the languages used.

Interestingly, not the share of Turkish from an individual student's talk time, but the share of Turkish and mixed mode together have the second strongest influence on the long term achievement (Table 3). This is in line with Auer (2011) who identifies the mixed mode as the norm for Turkish-German multilinguals, and not the "pure" use of Turkish. This suggests that in bilingual classrooms the multilingual register and mixed mode are central pillars of the classroom discourse. Furthermore, it may suggest that a mixed mode allows deeper conceptual understanding [START_REF] Wagner | Vernetzung von Sprachen und Darstellungen in einer mehrsprachigen Matheförderung [Relating languages and representations in a supportive multilingual teaching intervention on fractions[END_REF]. Hence, in spite of its methodological limitations, this study confirms research which hints at the relevance of activating multiple languages in learning processes.

Figure 1 :

 1 Figure 1: Supply-Use-Model adapted from Helmke (2009) by Schüler-Meyer et al. (2019b) (factors held constant are colored in light grey, varying factors in dark grey)

Table 1 : Descriptive data for the full sample, the bilingual subsample, and the sample of this study

 1

Table 2 : Distribution of modes of language use for teachers and students (n=37 students)

 2

3: Only German language proficiency as variable

		Regression	Standard	Standardized re-
		coefficient b	error (b)	gression coefficient
	Model 1: All variables (R 2 = 0.35, R 2 (korr.) = 0.14, F(7,22) = 1.68, p > .05)
	Intercept	-9.45	6.2
	German language proficiency (C-Test)	0.32	0.17	0.40
	Fluid intelligence (Befki)	-0.0007	0.33	-0.0004
	German academic language proficiency (BiSpra) -0.05	0.26	-0.05
	Turkish language proficiency (C-Test)	0.034	0.09	0.10
	Socio-economic Status (Book index)	0.79	0.82	0.20
	Use of Turkish and mixed mode	5.25	4.88	0.23
	Percentages of talking time	-0.91	1.91	-0.092
	Model 2: After systematic model reduction (R 2 = 0.35, R 2 (korr.) = 0.30, F(2,30) = 7.973, p < .01)
	Intercept	-9.90 *	4.17
	German language proficiency (C-Test)	0.34 *	0.13	0.41
	Use of Turkish and mixed mode	6.90	3.64	0.30
	Model (R 2 = 0.27, R 2 (korr.) = 0.25, F(1,31) = 11.39, p < .01)
	Intercept	-10.63 *	4.32
	Proficiency in German	0.44 **	0.13	0.52
	Model

4: Only Turkish and mixed modes as variable

		(R 2 = 0.20, R 2 (korr.) = 0.18, F(1,31) = 7.873, p < .01)
	Intercept	0.28	1.45
	Use of Turkish and mixed mode	10.33**	3.68	0.45

Table 3 : Results of the regression analysis with stepwise model selection

 3

Acknowledgment

"MuM-Multi: Fostering Language in multilingual mathematics classrooms effects and conditions of a content-and language integrated intervention" was funded by the German ministry BMBF (01JM1403A, grant holders S. Prediger, J. Rehbein & A. Redder). We thank T. Kuzu, A. Redder, J. Rehbein, J. Wagner, and M. Çelikkol.


The eroding rotation: Why digital pictures should not be rotated

Denis Roegel * 1st March 2009

Digital pictures are now ubiquitous and they are produced through a variety of sources: scanners, digital cameras, cell phones, web cams, screenshots, to name a few. Some of these pictures end up being published, which means that in most cases they will be printed.

But published pictures must conform to a certain standard of quality, and for a number of reasons, in particular aesthetic ones, lines are rendered as they are expected to be rendered. A photograph of some landscape, for instance, will normally be shown with the real horizon being horizontal. This seems totally obvious, but in fact it doesn't have to be so. It is just more convenient, and the photograph then becomes a natural extension of the observer.

Unfortunately, some of the pictures aimed for publication are not perfectly ready to be shown. This is for instance the case for the photograph shown below:

In practice, the defects of real pictures are not as important as in the previous example, but the author of a publication may feel a need to slightly rotate the pictures he is displaying, especially if these pictures exhibit straight lines, like in the above example. A number of subjects are not as sensitive to rotation and cropping a picture can be a quite acceptable way to hide a digital anomaly.

When however a picture has to be rotated, the effects can be more far reaching than the short-term publication. In fact, the picture may have been an archival picture, and it is then likely that this archival picture will also end up being rotated. This seems a quite benign operation, some adjustment of a very different nature than color adjustments. After all, isnt't a digital rotation just like a physical rotation? Isn't it as simple as moving the picture with our fingers? It turns out that it isn't as simple. In fact, in most cases, rotating a digital picture damages it1 .

The reason for this damage is quite simple. Most of the pictures are bitmaps, which are arrays of square pixels. These pixels are transferred on screen or paper, where similar arrays are present. One pixel of the original picture may correspond to one pixel on paper, but more likely there will be some conversion, some kind of conversion ratio. The pixels of the picture will be aligned with horizontal and vertical lines, and so will be the pixels on paper. Therefore, if a picture needs to be rotated, its pixels will first be abstractly rotated, but again fitted to another horizontal/vertical grid. In addition, pixels are not just black or white, but they can have some value in between, and these values only belong to a finite set. If you imagine one very large black pixel, and a slight rotation of this pixel around its lower left corner, some parts of the original pixel will cover other pixels, and the darkness of these other pixels may have to be changed. If the value of a pixel is only 0 or 1, then there will be some threshhold and some pixels will move, while others will not, depending where they are located. These transformations will slowly erode the picture, because some information gets lost. The process is normally not reversible. Although this loss is only very small, it should be avoided, if possible, especially by people who are holders of digital archives.

An example will make this clear. Consider the following fragment of an image, where we have two dark pixels (in gray). The pixel centers are shown, and we rotate the image around point O by 19.5 degrees. The two rotated pixels are shown as an overlay, as well as their centers.

O

The following picture shows these rotated pixels, but they do not fit the initial grid.

O

In this case, a pixel being either black or white, we must choose which pixel gets altered. This is not as simple as it seems, and we can imagine different solutions. We can for instance darken the pixels which are covered by more than a half of their surface by black pixels.

O (global approach)

Another solution is to consider individually each rotated pixel, and to check where its center is located, and darken the corresponding pixel. This does not give the same result:

O (local approach)
If we choose the global approach, and perform the inverse rotation, applying the same criteria, we end up with only one dark pixel, because the pixel in the middle has less than half of its surface covered by a rotated black pixel:

O ⇒ O ⇒ O
If, on the other hand, we choose the local approach, we end up with another result, also different from the original configuration:

O ⇒ O ⇒ O
This simple example has shown that performing one rotation in one direction, followed by the same rotation in the opposite direction can result in either pixel losses, or pixel displacements. There are of course cases where the pixels are not altered, but in the above cases only one pixel out of the two dark ones has returned in its correct position. This should be convincing enough of the non-anecdotical nature of the image erosion. Now, in order to make this loss more explicit, we consider again the initial picture, this time in its original orientation:

Original picture

We are going to apply a simple transformation to this picture, namely, rotate it counterclockwise by one degree, and then again by one degree clockwise2 . The result is:

Although the two pictures are already slightly different, this is practically impossible to notice. However, the erosion has started, and the disease is there, only at its first stage.

We now speed up the erosion, and add four more steps:

Original picture rotated by 5 × (1 -1) degrees.

The picture still seems quite acceptable, but the disease has made progress. We now add 15 steps: Original picture rotated by 20 × (1 -1) degrees.

We can now see the first signs of the damage. Although some parts are still acceptable, the overall feeling is that the picture is no longer as sharp as the previous one, but the greatest damage seems to have taken place for the upper windows, whose frames now seem to undulate.

We can still go further. Twenty steps later, we reach this picture:

Original picture rotated by 40 × (1 -1) degrees.

The damage has increased, but the house can still be recognized, as well as the trees. Incidentally, the black line on the right is an artefact of our rounding process. There is a slight drift, and this drift is made apparent because we ensure that the picture always has the same pixel size after the two elementary rotations.

We could iterate this process many times, but we are just showing two more positions, after a total of 60, and a total of 80 elementary 1 -1 steps:

Original picture rotated by 60 × (1 -1) degrees.

Original picture rotated by 80 × (1 -1) degrees. This last picture seems in very bad shape, but it is only 80 times the damage which was made to the first picture. The harm was done at the beginning.

The conclusion is: do not rotate bitmap pictures, because most of the time you will damage them! Instead, try to produce high quality pictures right away, if you can, and be sure to store the best pictures you have and protect them from the harm of rotation. It takes more time to produce good pictures at the beginning (for instance by scanning), but you will save time in the future, because you will not have to go through such a process again.

For L. B. and her Archives.

A number of web sites seem to contradict this statement, for instance the pages about "lossless JPEG rotation," but these sites concern another kind of damage, such as a loss of resolution when cropping a picture, or the loss resulting from accumulated compression/decompression, and usually only rotations of multiples of 90 degrees are considered. This is different from the problem examined here, which is inherent to the bitmap representation of images.

All the rotations were performed using the pnmrotate program on the Linux operating system.


Denis Roegel

Detecting interference through graph reduction

Keywords: graphs, nets, reduction, rewriting, interferences, concurrency, threads, TLA

Parallel programs which run in a shared-memory model have several threads that may interfere. There are constraints between the threads and these constraints can be modelled by a net. We present TLA nets, which are interesting for the representation of concurrent executions. A reduction operation is defined on these nets, in order to detect interferences. These interferences can be eliminated by adding components such as delays to the net. TLA nets are a graphical tool to explore the constraints of parallel programming.

Introduction

When parallel programs run in a shared-memory model, there are usually several threads and these threads can interfere, thereby producing unwanted side-effects. It is possible to describe the structure of a program segment by a graph whose edges represent the changes in the system, and such graphs will be useful for detecting interferences at early stages. An example of such a graph is given in figure 1.

In this graph, the wavy edges represent instructions, whereas the dashed lines represent dependencies. The wavy edges are labelled by abstract representations of the instructions, namely TLA [START_REF] Lamport | The Temporal Logic of Actions[END_REF] actions. The parallel branches represent independent actions. All these concepts and notations will be detailed in section 2.1.

First, the formalism of the nets will be precisely presented. Then it will be shown how a network can be reduced and how the reduction makes it possible to detect interferences between different threads. * Email: roegel@loria.fr.

x ′ = x + 1

x ′ = x + y y ′ = y + 1 z ′ = 2 * y y ′ = z + 1 t ′ = y y ′ = y 2 ∧ (x > 0) ∧ (x ′ = y -x) ∧ (x ≤ 0) ∧ (x ′ = y + x) x ′ = x 2 z v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9

Nets of actions

The nets of TLA actions, the TNets (TLA Nets), are defined here. The presentation is purely syntactic, and the precise semantics is defined by the reduction operation (see section 3). First, an intuitive semantics is given.

TNets are graphs having vertices and edges. There are two kinds of vertices and several kinds of edges. Some edges are labelled by TLA actions, or more precisely, by contextual TLA actions. The vertices represent states of a system and the labelled edges are its transitions.

The nets of interest to us will be finite nets: the number of vertices and edges will be finite and the loops will themselves be finite: by that it is meant that there are only a finite number of loops in the construction of the net, and that each of these loops is traversed only a finite number of times during the execution. In section 3, a procedure to eliminate the nets which do not satisfy the constraint of a finite loop execution (hence, nets which do not halt) will be given.

Finally, all the considered TLA actions will be deterministic, that is, they will actually be functional relations.

The structure of the TNets articulates around the following concepts: sequence, concurrency, alternative, delay, synchronization, local variables.

The elements at our disposal to build a TNet make it possible to construct a great many networks. However, only some of these networks are of interest to us.

Elements of a TNet

The building blocks of a TNet are 1) the edge valued by an action, that is, a relation between two consecutive states, and 2) the edge representing a waiting state. A wavy edge represents an edge valued by an action, the waving being an image of the activity, or more precisely, of the fact that variables can change their values in the corresponding action:

. For simplicity, an action will often be given as a shorthand in place of an edge valued by an action. Actions without primed variables, namely predicates, can be represented by straight edges:

. In general, edges are labelled by an action as it is the case in figure 1.

Each vertex represents a set of local states. A local state is a valuation of a set of variables. A state can actually be regarded as a control point.

These states are not given in extenso, in that the values of the variables are not given explicitely. On the contrary, what defines the valuation of the variables in a state is the way this state is reached. Other formalisms, in particular the very similar notation of Lamport (predicate/action diagrams [START_REF] Lamport | TLA in Pictures[END_REF]), associate predicates or assertions to the different control points. The presence of assertions corresponds to an operational view, whereas its absence corresponds to a denotational view.

The edges corresponding to actions are directed and link two vertices of a TNet. Intuitively, this means that the action represented by the edge allows the passage from the first state to the second state.

Two vertices can be linked by more than one action. Two cases are distinguished:

• The first case is parallelism: a and b occur simultaneously. The superior vertex is of type "AND".

a b

• The second case represents an alternative: Here, at most one of the two actions, a or b, can occur. It is possible that none of them is executed, when one considers a fragment of a net made up of two actions among three, for instance. The top vertex is of type "OR" represented by "□". Hence, we always set ourselves in the case of a deterministic choice. a b

Delay and synchronization are indicated using simple and double dashed arrows. They introduce an ordering constraint between two actions. Some variables can be local to several actions. This fact is represented by surrounding the set of concerned actions by a dotted line labelled with the local variable (see figure 1). We add as a constraint that the intersection of two dotted areas is necessarily one of these areas, which forbids nets where actions bound by two different local variables overlap.

The graphs under consideration will always have a source and a sink. This is natural since these concepts correspond to the initial and final states of the execution of a function.

However, many nets obtained by a combination of the primitive elements will give rise to problems we will try to detect and solve in section 3.

Formalization

The concepts that have been described in the previous section are formalized here.

Definition 1 (deterministic action) An action

A(x , x ′ ) is said to be deterministic if the relation represented by A is functional, that is, if x ′ is a function of x . For instance, x ′ = x + 1 (x ′ is the value of x in the next state) is deterministic, but x ′ + y ′ = x + y is not.

Definition 2 (set of actions)

We assume Act to be a set of deterministic TLA actions. This set will not be defined formally.

Definition 3 (variables of an action) The set of variables of an action is the union of the set of used variables (unprimed) and the set of modified variables (primed): Var

(a) ∆ = U(a) ∪ M(a).
x ′ is always included in M(a) even if x is not modified. One can view M(a) as the set of variables constrained by a. Definition 4 (set of variables) Let V be a set of variables such that ∀a ∈ Act, Var (a) ⊆ V.

Definition 5 (set of values) We assume a set of values Val.

We will see in section 3 that the environment of the net must be taken into account for the reduction of the nets. The interaction between a net and its environment is based on the interaction between an action and the environment. Henceforth, we will add to each action some requirements with respect to the environment. In return, this will allow us to deduce properties that the net will guarantee. This will be detailed later. The nets can now be defined:

Definition 8 (net) A

GTNet is a tuple ⟨V , br , edge, loc⟩ where:

• V is a finite set of vertices;

• br : V → {•, } is the branching function: br (s) ="•" if s is an "AND" vertex and br (s) =" " if it is an "OR" vertex.

• edge : V 2 → (P(CA) ∪ D) is the "edge" func- tion. edge(v 1 , v 2 ) ∈ P(CA) if v
{(v 1 , v 2 , ar ) ∈ V × V × CA/ar ∈ edge(v 1 , v 2 )}.
If loc(v 1 ) and loc(v 2 ) are the edges where v 1 and v 2 are local variables, then either loc

(v 1 ) ∩ loc(v 2 ) = ∅, or loc(v 1 ) ⊆ loc(v 2 ), or loc(v 1 ) ⊇ loc(v 2 )
. This constraint may make it necessary to rename some variables.

Definition 9 (source of a net) v is a source if v ∈ V and ∀u ∈ V : edge(u, v ) ̸ ∈ P(CA). Definition 10 (sink of a net) v is a sink if v ∈ V and ∀u ∈ V : edge(v , u) ̸ ∈ P(CA).
Definition 11 A TNet is a GTNet with a unique source and a unique sink. The sink v is such that br (v ) = •.

Definition 12 (action escaping from a vertex)

The action a is said to escape a vertex s if

∃r ∈ P(V) : ⟨a, r ⟩ ∈ ∪ u∈V edge(s, u)

Example of a formal representation of a net

Consider figure 1. This net has nine vertices denoted by v 1 , v 2 , . . . , v 9 . We have:

• V = {v 1 , v 2 , v 3 , v 4 , v 5 , v 6 , v 7 , v 8 , v 9 }. • ∀i ̸ = 5 : br (v i ) = • and br (v 5 ) = □. • edges: edge(v 1 , v 2 ) = {⟨x ′ = x + 1, {x }⟩}, edge(v 2 , v 3 ) =, edge(v 5 , v 7 ) = {⟨(x > 0) ∧ (x ′ = y -x ), {x , y}⟩, ⟨(x ≤ 0) ∧ (x ′ = y + x ), {x , y}⟩}, etc. • loc(z ) = {(v 3 , v 4 , ⟨z ′ = 2 * y, {y}⟩), (v 4 , v 6 , ⟨y ′ = z + 1, {z }⟩)}
• v 1 is the source and v 9 is the sink.

Reduction of a net

A TNet reduction will replace a complex net by a net composed of a unique edge which is equivalent to it (in some sense). In other words, the reduction associates a TLA action to a net. This operation modifies the granularity of a net.

Moreover, the reduction makes it possible to separate the nets into two categories: those that can be reduced into an action and those that cannot. The case of nonreducible nets will be studied in more detail.

Underspecified nets have also to be completed. For instance

x ′ = x + 1 y ′ = x + z
poses problems because it is not known how the value of z changes. The solution is twofold:

• All unprimed variables 1 in the second action must appear in the first action, in their primed form, possibly meaning the identity.

• If an action uses a variable x , it must also mention x ′ .

If these conditions are not respected, the reduction of these two actions is unknown by convention, and is denoted by ⊥.

These rules will be formalized in the next section.

Formalization

The previous section explained intuitively how the net reduction is worked out, and the need to introduce additional constraints if we want the net to be reduced in a specific way. From now on, TLA actions will no longer be manipulated. Instead, contextual actions (cf. §2.2) are used in order to handle these constraints.

The operations ∧ c , ∨ c and • c are defined on the elements of CA, the set of contextual actions. They are the contextual equivalents of ∧, ∨ and •.

Definition 13 (contextual conjunction) ⟨a 1 , r 1 ⟩ ∧ c ⟨a 2 , r 2 ⟩ is defined as follows:

• if a 1 = ⊥ or a 2 = ⊥, then ⟨a 1 , r 1 ⟩ ∧ c ⟨a 2 , r 2 ⟩ ∆ = ⟨⊥, ⊥⟩ (failure propagation) • if M(a 1 ) ∩ r 2 = ∅ and M(a 2 ) ∩ r 1 = ∅, then ⟨a 1 , r 1 ⟩ ∧ c ⟨a 2 , r 2 ⟩ ∆ = ⟨a 1 ∧ a 2 , r 1 ∪ r 2 ⟩ • otherwise, ⟨a 1 , r 1 ⟩ ∧ c ⟨a 2 , r 2 ⟩ ∆ = ⟨⊥, ⊥⟩
1 These variables can also occur as primed variables in the second action, of course.

As soon as a reduction yields ⟨⊥, ⊥⟩, the reduction of the whole TNet is undefined. The result of the execution is ignored: the TNet must be better specified.

Definition 14 (contextual disjunction) ⟨a 1 , r 1 ⟩ ∨ c ⟨a 2 , r 2 ⟩ is defined as follows:

• if a 1 = ⊥ or a 2 = ⊥, then ⟨a 1 , r 1 ⟩ ∨ c ⟨a 2 , r 2 ⟩ ∆ = ⟨⊥, ⊥⟩ (failure propagation) • if a 1 ⇒ ¬a 2 then ⟨a 1 , r 1 ⟩ ∨ c ⟨a 2 , r 2 ⟩ ∆ = ⟨a 1 ∨ a 2 , r 1 ∪ r 2 ⟩
(the dependencies are determined statically)

• otherwise, ⟨a 1 , r 1 ⟩ ∨ c ⟨a 2 , r 2 ⟩ ∆ = ⟨⊥, ⊥⟩

(exclusion of non-determinism)

Definition 15 (contextual sequentialization) Finally, ⟨a 1 , r 1 ⟩ • c ⟨a 2 , r 2 ⟩ is defined as follows:

• if a 1 = ⊥ or a 2 = ⊥, then ⟨a 1 , r 1 ⟩ • c ⟨a 2 , r 2 ⟩ ∆ = ⟨⊥, ⊥⟩ (failure propagation) • if ¬(U(a 1 ) ⊆ M(a 1 )) then ⟨a 1 , r 1 ⟩ • c ⟨a 2 , r 2 ⟩ ∆ = ⟨⊥, ⊥⟩ • if ¬(U(a 2 ) ⊆ M(a 2 )) then ⟨a 1 , r 1 ⟩ • c ⟨a 2 , r 2 ⟩ ∆ = ⟨⊥, ⊥⟩ • if M(a 1 ) ̸ = U(a 2 ) then ⟨a 1 , r 1 ⟩ • c ⟨a 2 , r 2 ⟩ ∆ = ⟨⊥, ⊥⟩ • otherwise ⟨a 1 , r 1 ⟩• c ⟨a 2 , r 2 ⟩ ∆ = ⟨a 1 •a 2 , r 1 ∪r 2 ⟩ Theorem 1 (Associativity of ∧ c , ∨ c and • c )
The three operations ∧ c , ∨ c and • c are associative. The proofs are given in [START_REF] Roegel | Étude de la sémantique de programmes parallèles « réels » en TLA[END_REF].

Theorem 2 (Commutativity of ∧ c and ∨ c ) Obvious.

Reduction rules

Reduction rules in which the actions are accompanied by an hypothesis on the environment (requirement) are stated here. Each action is therefore a pair ⟨guarantee, rely ⟩, made of an hypothesis that the environment must satisfy (rely) and of an action (guarantee) which is satisfied if the first hypothesis is true. These pairs will be manipulated in a compositional manner, in that the pair of a complex net will be obtained from the pairs corresponding to its parts. Reference [START_REF] Collette | Enhancing the Tractability of Rely/Guarantee Specifications in the Development of Interfering Operations[END_REF] gives other approaches of this paradigm for the construction of larger scale specifications.

The rules enable us to handle the interferences occuring when actions are composed.

The rules are given in table 1.

The rules involve the contextual composition operations • c , ∧ c and ∨ c . Each rule has a non-contextual counterpart, obtained by replacing • c by •, ∧ c by ∧ and ∨ c by ∨.

The rules R 1 to R 4 have a very simple expression, in spite of the fact that they take into account the possible interferences. These interferences are handled by the contextual connectives on the contextual actions. Some of the rules are explicited below.

• Rule R 1 : if ∃s 1 , s 2 ∈ V , ar 1 , ar 2 ∈ edge(s 1 , s 2 ) such that br (s 1 ) = •, then -for all s a , s b : edge ′ (s a , s b ) ∆ = edge(s a , s b ) if s a ̸ = s 1 or s b ̸ = s 2 ; -edge ′ (s 1 , s 2 ) ∆ = (edge(s 1 , s 2 ) \ {ar 1 , ar 2 }) ∪ {ar 1 ∧ c ar 2 } • Rule R 5 :
Condition : no contextual action other than a is supposed to escape from the "AND" node. and if (with [START_REF] Tennent | The Denotational Semantics of Programming Languages[END_REF]'s notations for the denotational semantics)

• Rule R 6 : "repeat until" if ∃s 1 , s 2 , s 3 ∈ V such that 1. edge(s 1 , s 2 ) = {⟨a, r a ⟩}, 2. edge(s 2 , s 3 ) = {⟨b, r b ⟩}, 3. edge(s 2 , s 1 ) = {⟨c, r c ⟩} 4. br (s 2 ) = 5. ∀s : (edge(s 1 , s) ∈ P(CA)) ⇒ ((s = s 2 ) ∧ edge(s 1 , s) = {⟨a,
1. repeat σ ∆ = (E[[¬c]]σ → σ, repeat(C[[a]]σ)) 2. ru(a, c)(σ) ∆ = C[[repeat a until ¬c]]σ = repeat(C[[a]]σ) where ru(a, c)(σ) = ⊥ if the loop diverges; then: -edge ′ (s 2 , s 1 ) = ⊥ -edge ′ (s 1 , s 2 ) = D(⟨a, r ⟩, c) where * if ∀σ, ru(a, c) ̸ = ⊥, then D(⟨a, r ⟩, c) ∆ = ⟨ac, r ⟩ with ac ∆ = σ ′ = ru(a, c)(σ) * if ∃σ, ru(a, c) = ⊥, (case of divergence) then D(⟨a, r ⟩, c) ∆ = ⟨⊥, ⊥⟩ D(a, c) is the relation associated to the function ru(a, c).
The semantics of a loop is an action if the number of loops is finite.

• Rule R 8 :

Conditions:

1. the contextual actions a 2 and b 2 escaping from the intermediate vertices are the only ones escaping from these vertices.

2. a 1 and b 2 do not interfere.

Confluence

It will be shown that the rewriting system made of rules R 1 to R 9 is confluent. First, a few notions useful for the proof are introduced.

Complexity of a net

The complexity comp(R) of a net R is defined by

comp(R) = n a + n ∨ + n + 2 • n + n l
where n a is the number of edges representing actions, n ∨ is the number of "OR" vertices, n is the number of double dependencies, n is the number of simple dependencies and n l is the number of localities. The weights are different for n and n because rule R 8 does not diminish the number of edges.

Notice that there exists a net of complexity n, for any n > 0. It is also obvious that each reduction rule decreases the complexity of a net. For instance, for (1

≤ i ≤ 9) ∧ (i ̸ = 6), comp(R i (R)) = comp(R) -1. And comp(R 6 (R)) = comp(R) -2.
Since the nets under consideration are finite, the reduction process ends. It now remains to show that the reduction is confluent. The proof is based on the locality of the rewriting rules and the permutability of the rules in some cases. The proof is by induction on the complexity of the net. See [START_REF] Roegel | Étude de la sémantique de programmes parallèles « réels » en TLA[END_REF].

R 1 : a b a ∧ c b R -→ R 2 : a b a • c b R -→ R 3 : a b a ∨ c b R -→ R 4 : a b a • c b R -→ R 5 : a a R -→ R 6 : ⟨a, r a ⟩ ⟨b, r b ⟩ ⟨c, r c ⟩ ⟨D(a, c), r a ⟩ ⟨b, r b ⟩ R -→ R 7 : ⟨a, r⟩ ⟨∃v : a, r\{v}⟩ R -→ v R 8 : R -→ a 1 b 1 a 2 b 2 a 1 b 1 a 2 b 2 R 9 : R -→ a 1 b 1 a 2 b 2 a 1 b 1 a 2 b 2
The unicity of the normal form is true even for nets which do not reduce to actions.

Definition 18 (Confluence rewriting)

N 1 R * -→N 2 if ∃M 1 , . . . , M n such that N 1 = M 1 , N 2 = M n , M i R -→M i+1 and ¬∃M p such that M n R -→M p .

Observational semantics of a TNet

The observational semantics of a TNet is defined in the following way:

Definition 19 (Observational semantics) [[.]] :

Net → CA where

• [[N ]] ∆ = R * -→(N ) if R * -→(N ) ∈ CA • [[N ]] ∆
= ⟨⊥, ⊥⟩ otherwise; (this case occurs when none of the rules can be applied) and • CA is a set of contextual actions (see definition 6).

• Net is the set of nets.

Because of its global aspect, the observational semantics is of course similar to the denotational semantics.

Non-reducible nets

The rules seen in section 3.2 make it possible to reduce a net when the rules are read from left to right. However, if they are read from right to left, they represent construction rules.

The RTNets are defined as TNets whose reduction is a TLA action. It is easy to find TNets which are not reducible, and thus, which are not RTNets. Almost all TNets are not reducible, which is easily understood, since a program written randomly is very unlikely to do something meaningful (or, let us say, interesting).

Definition 20 (generated nets) RTNets

= {t ∈ TNets/ R * -→(t) ∈ Act}
For instance, the net of figure 2 cannot be reduced to an action and can therefore not be generated by the inverse rules.

Related work

A net formalism has often been employed in order to represent and analyze concurrent systems. Rabinovich [START_REF] Rabinovich | Modularity and Expressibility for Nets of Relations[END_REF] presents ideas which have much in common with ours. He introduces a notion of nets made from two kinds of vertices: circles which represent places and squares which represent ports. The edges are called channels. Ports correspond to data or variables and places to operations on these data.

Rabinovich considers such nets where a function is associated to each place output. These functions take the data from input ports and compute the output. If the ports and internal places of the net are hidden, a solution to the equations determined by the functions is a function determining the outputs in terms of the inputs. This is what Rabinovich calls the observable relation. The places can also be labelled by relations.

The TNets are different from Rabinovich nets in that all vertices in TNets represent states, corresponding therefore to ports in Rabinovich's formalism. The edges of a TNet correspond to the functions labelling Rabinovich places. Furthermore, the TNets have two kinds of branching at the vertices and have notions of dependencies and local variables.

The "reduction" of a Rabinovich net is a solution to the functional or relational equations defined by the places. These equations are not conditional, as in the TNets, since there are no dependencies or choices. Moreover, there is no possibility in Rabinovich's nets to have two branches in parallel, that is to have a port which would be obtained from two functions. So, there is no notion of interference, as is the case with the TNets, but there might be no solutions to the equations defined by the net. Rabinovich doesn't give a rewriting system, but could define the reduction of a system in that way.

In [START_REF] Lamport | TLA in Pictures[END_REF], Lamport defines the predicate/action diagrams which are graphs labelled by a property (predicate) [START_REF] Lamport | Control Predicates are Better than Dummy Variables for Reasoning about Program Control[END_REF] and represent the states satisfying this property, and whose edges are actions. A predicate/action diagram denotes a TLA formula. The purpose of this formalism is to give a graphical view of some components of a system, for instance by restricting ourselves to the behaviour of some variables.

The formalism is hence very close to the TNets' formalism, but Lamport does not study the reduction of these nets. In the TNets, the vertices are not labelled by predicates because we are not interested by a local study of the net, but by a global study.

Conclusion

The reduction of TLA nets proves to be interesting for the detection of interferences in parallel executions. The reduction is based on a few rewriting rules and is confluent. Hence, a well-defined net has a clear semantics which is its reduction. The use of a graphical representation helps linking the net with a real execution.

Figure 1 :

 1 Figure 1: Example of a TNet

Definition 6 (

 6 contextual actions) Let CA = (Act × P(V)) ∪ {⟨⊥, ⊥⟩}; CA represents the set of actions with a condition on the context; ⟨a, r ⟩ ∈ CA if r is a set of variables which must not be modified by the environment. In general, ⟨a, r ⟩ = ⟨a, U(a)⟩ where U(a) is the set of variables used in a. Definition 7 (set of dependencies) D = {⊥, , ,} is the set of dependencies. The elements of D must be distinct from the elements of Act. ⊥ will represent the absence of any link between two vertices of a net. and will represent the delay and the synchronization.

6 .

 6 r a ⟩}) (No action other than a can escape from a top node) Pred (c) (c is a predicate) 7. U(c) ⊆ M(a) (the variables of c must be primed in a) 8. c ⇒ ¬b 9. b ∨ c

Theorem 4 (

 4 Confluence) The rewriting relation R -→ is confluent. This is an immediate consequence of the unicity of the normal form. Since the R -→ relation is confluent, a new rewriting relation R * -→ can be defined. It represents the iterated relation of the R -→ relation.

Figure 2 :

 2 Figure 2: Non reducible net

Table 1 :

 1 Reduction rules The rewriting relation→ is confluent in x , if for all x 1 , x 2 , if x → * x 1 and x → * x 2 , there exists x ′ such that x 1 → * x ′ and x 2 → * x ′ .

	3.3.2 Confluence
	Let → * be the reflexive transitive closure of some
	binary relation →.
	Definition 16 (Normalization) A net G is nor-
	malizable if there exists a reduction G → * G ′ where
	G ′ is not reducible.
	Definition 17 (Confluence) Theorem 3 (Unicity of normal form) A net G
	has a unique normal form.