Following the ecological approach to visual perception, this paper investigates multimodal referring acts in Human-Computer Interaction. Preliminary results from a simulation experiment allow to: (a) clarify the effect of perceptual organization on multimodal communication; (b) provide guidelines for designing effective multimodal interfaces. Demonstrating that both the verbal and the gestural part of a referential act are influenced by perception, we confirm the need and the utility of taking into account perceptual organization to analyze referential expressions in a more robust way. As a conclusion, we show how these results can lead to an actual implementation of a gesture interpretation module directed by the reference analysis process.

Introduction

An efficient way to allow a better use of the constantly growing number of software capabilities can be to provide users with a more natural interaction form to express their communicative intentions.

Although the directmanipulation paradigm reproduces an ecological way of acting upon objects, it still implies a learning phase (to master the rules of the new interaction style) as well as a constant translation activity (to transform conceptual intentions into available elementary actions). Both these activities increase the cognitive workload required to perform computer-supported task (Norman and Draper 1986). Simplifying the translation process from intention to actions, requires interface designers to devise multimodal systems capable of handling spontaneous speech and gesture.

Perception-action

To study user behavior in a multimodal environment, we choose the perception-action cycle as the appropriate unit of analysis [START_REF] Neisser | Cognition and Reality[END_REF]. This theoretical framework explains how action planning and execution is controlled by perception and how perception is modified by active exploration. Moreover, the study is based on ecological psychology, an approach to perception, cognition, and action emphasizing the mutuality of organism-environment relationships [START_REF] Gibson | The Ecological Approach to Visual Perception[END_REF]. It is based on the 'validity' of information provided to perception under normal condition, implying, as a corollary, that laboratory studies must be carefully designed to preserve ecological validity. According to this view, perception and action are linked by affordances. Optic information about objects conveys their functional properties providing clues about the actions they can support. Functional properties can thus be considered as affordances of users' possible actions, as if the object suggested its functionality. For example, a hammer usually induces us to take it by the handle and not by the head, because the handle is visually more graspable.

In this paper, we attempt to extend the concept of affordances to explain referring acts; i.e., communication acts composed by a verbal part (referring NP) and a gestural part (referring gesture). The basic question tackled is the following: Can different perceptual organizations afford different multimodal actions?

To answer that, a simulation experiment was run. Perceptual organization was manipulated according to the principles of the Gestalttheorie [START_REF] Wertheimer | Untersuchungen zur Lehre von der Gestalt I[END_REF][START_REF] Kanizsa | Organization in vision[END_REF]. They state that individuals spontaneously organize the perceptual field into groups of percepts. Grouping allows the observer to reduce the original complexity of the stimulus. This is necessary because human capabilities to process separate units are limited. Gestalt laws of perceptual organization describe the principles underlying grouping. The main principle, prägnanzlaw, states that the elements of the visual field tend to be segregated into forms that are the most stable and create a minimal stress. The other principles describe how stability is achieved. In this paper, we focuse on similarity (objects are grouped on the basis of their salient physical attributes, such as shape and color), proximity (elements are grouped on the basis of their relative proximity), and good continuation (shapes presenting continuous outlines have a better configuration than those with discontinuous ones).

Referring acts

The grouping process of perception can be compared to the process of identifying referents. To convey their communicative intentions, speakers have to drive the attention of listeners towards a reduced area of the visual world containing the group of mentioned referents. Referring NPs, possibly in combination with referring gestures, can accomplish this task with a great flexibility in the way features are shared out between language and gesture [START_REF] Schang | Frames, a unified model for the representation of reference and space in a Man-Machine Dialogue[END_REF][START_REF] Bellalem | Which representations for a proper treatment of referring expressions in a man-machine multimodal dialogue[END_REF].

Indeed, the way referential acts are produced depends on the complexity of extracting the percepts which are to be referred to. To do so, both communication modes (speech and gesture) often convey complementary information that helps categorizing and localizing referents. On the one hand, the referring NP allows the listener to determine the category of referred percepts. On the other hand a localization is carried out by using either spatial referring NP or referring gesture. As regards categorization, the role of a referential expression is to filter a perceptual category according to the most salient features of the object. This process depends in particular on the semantic characteristics of the expression (e.g. demonstrative vs. definite usages, see below). As regards localization, the gesture determines the spatial features of the referred percepts. Such referential extraction allows the listener to isolate the focused percepts from the shared visual context.

Categorization can be performed according to various criteria which are intrinsic to the perceptual features. From a linguistic point of view, this filtering action builds an opposition, also called axiology, between the different kinds of percepts occurring in the scene [START_REF] Gaiffe | Les SN définis: anaphore, anaphore associatives et cohérence[END_REF]. For instance a definite expression such as «the green triangles» organizes the referential space into opposite categories as shown in figure 1a. At a first level, the use of the definite expression operates a contrast between N-objects (N being the category) and non-Nobjects, which is then refined, in our example, into two opposites sub-categories : the green and non-green triangles. A demonstrative expression such as «those squares», also defines a similar contrast as shown in figure 1b. The initial context, where the contrast is to be performed, results from the filtering of the more global context to keep only N-object. The contrasting process then relies on the ability to isolate an element -or in the case of plural, group of elements-which is specifically in focus.

A deictic gesture, on an otherwise verbally limited context, also leads to a reduction of the focus of the listener. The perceptual criteria used then rely on the features which are extrinsic to the percept, and rather belong to properties of perceived group, or percepts, the user refers to. Features that define a group can be found in its localization, its topology, as well as in its general shape.

However, the rate of each reduction seems to be related to the heterogeneity of the elements, of their properties, as well as of the involved groups and their salience. In some cases, when the salience of the referents corresponds to their intrinsic features, this type of discrimination can be more easily done verbally, by a referential NP. For instance, a group of red triangles spread among gray squares, provides the speaker with an easy linguistic accessbecause of its strong salience. In other cases, when the scene displays groups with a sufficiently contrasted topology, the reduction can be more efficiently expressed by a deictic gesture. For instance, a circling gesture can easily isolate a group that is well separated from other percepts. These reductions reflect the contrastive effort which has to be produced by the speaker so that the listener will be able to isolate the referenced percepts.

If the features of referential access seem to be determined by the complexity of the scene and of the perceived groups, as we will show in the second part of this paper, the difficulty of extracting referents belonging to different groups also seems to influence the characteristics of the referential effort. Indeed, it is easier to reference all the elements of a same group in a scene, than several percepts spread in different groups. In the first case, the salience of each group will influence the verbal and gestural accessibility. In the second case, the possible spreading of referents among different groups requires to build another group in an explicit way.

As a whole, these results are strongly enkeeping with what has been observed for referring acts in a pure linguistically based interaction. We deal here with an extension of the concept of relevance as defined by (Sperber and Wilson 1986) and which refines the classical Gricean maxims of brevity and efficiency. The only difference is that the evaluation of the ratio between the cognitive load to compute a given utterance and the number of inferences it fires must comprise the perceptual features available to the adressee combined with the gestural information. Besides, our observation that referential interpretation is heavily based upon localized perceptual groups complements the notion of contrastive sets advocated by [START_REF] Robert | Computational Interpretations of Gricean Maxims in the Generation of Referring Expressions[END_REF], not to say that they correspond to the same kind of representations, from a cognitive point of view.

The need for empirical research

The major problem in developing multimodal systems is connected to communication variability. Such a variability is as much present in the verbal part than in the gestural one, so that the communication protocol can not be reduced to stereotypic shapes. Even though a lot of studies have aimed at improving the understanding and also the computation of verbal utterances (see, for instance, the proceedings of last ISSD 96 in Philadelphia, or of the ESCA Workshop on Spoken Dialogue Systems Visgo, 1995) providing a less artificial linguistic protocol, only a few works have dealt with gesture variability (Oviatt, De Angeli and Khun 1997) and flexibility [START_REF] Streit | Active and Passive Gestures -Problems with the Resolution of Deictic and Elliptic Expressions in a Multimodal System[END_REF]. This bias has led to some kind of weakness in our understanding and thus in our ability to compute automatically complex gestures, which has led to a standard execution form: pointing has to be included in the visual referent.

This current lack could be explained by the features of most gestural devices and by the relatively few accurate data related to gesture parameters available to build and validate new models. Contrary to human-human communication, gesturing in HCI often requires to manipulate artificial mediators. A lot of traditional gesture devices can be categorized as mediators: mouse, trackball, joystick, pad or VR glove. In spite of this, devices exist which allow to limit this artificial limb effect at different levels. For instance, the touch screen reduces the presence of the intermediate layer sensitive to actions, but still requires some physical contacts. Other devices allow to reduce the latter constraint by, for instance, the location of an ultrasonic transmitter ring, or the disruption of a weak electric field produced by the hand position (Zimmerman etal. 1995). However, such gesture devices cannot fullly convey the richness of natural gesture. In human-human communication, locutors often use multipolar gesture, which cannot be reduced to one point, as in the case of a one-finger gesture. Multipolar gestures change the way of capturing action features, because it becomes possible to perform multi-point gestures composed by non-sequential events. Limiting gestural events to one point also reduces the potential lexical diversity of actions, and thus the ratio of semantic that the gestural movement can bring into multimodal utterances. It becomes then difficult for the user to produce utterances like «Draw a line that long» with an appropriate two-finger gesture. New generation devices can handle multi-point gestures, like the multipolar pad, or also the use of video recognizers which are able to locate hand positions [START_REF] Littman | Visual Gesture Recognition by a Modular Neural System[END_REF].

The fact that gestural interaction has for long been limited to simple pointing gesture can explain that no real urge has emerged to collect accurate data for this communication mode. Here, we present a simulation experiment where users were free to perform different kinds of gestures. These data have been collected in order to build an empirical reference interpretation model based on users' spontaneous behavior. Results will give insights about the effect of perceptual groups on verbal and gestural accessibility. In the last part of the paper, a general discussion will lead to evaluate the consequences of these influences in the modelization of multimodal analysis principles and to define some new experimental works.

Woz Simulation

In this section, we present a pilot study of an ongoing research project aimed at developing empirical predictive models that account for communication behavior in a multimodal HCI. As previously stressed, such a knowledge is essential to the design of future systems and to the development of interfaces capable of overcoming the technical constraints of the system without diminishing the intrinsic naturalness of multimodal communication. The pilot study was designed to test the reliability of the simulation environment (including system, task, procedure) and to provide preliminary results about the role of the perceptual field organizationin gesture and speech production.

Method

Participants.Seven students from the University of Nancy participated in the simulation as volunteers. All were French native speakers. Procedure. After reading hard-copy instructions describing system functions and task requirements, the participant engaged a dialogue with the simulated system to perform a typical computer-supported task, moving objects into folders. Interaction was based on speech and gestures, mediated by a microphone and an electronic pen.

Thirty different scenes were presented to each participant. The user's screen displayed a collection of objects and 8 boxes. To inhibit pure verbal references, objects were abstract-shape figures (De Angeli, Petrelli and Gerbino 1996). They could be targets or distractors. Targets were collections of two or three same-shape stimuli that have to be moved into the box displaying their figure. Distractors were exclusively used to manipulate perceptual field organization and did not have to be moved. At the end of the session, each participant filled in a user's satisfaction questionnaire and was debriefed. Design. The original study was based on a complex design manipulating several perceptual factors. In accordance to the aims of this paper, only a sub-sample of the corpus has been considered. It comprises data collected under two stimulus segregation conditions: High vs. Low Salience of group. In the high-salience condition, targets were easily perceived as a group, clearly separated from distractors. In this case, proximity and good continuation supported similarity. In the low-salience condition, targets were spontaneously perceived as elements of a broader heterogeneous group that included distractors. In this case, proximity and good continuation acted in opposition to similarity. Semi-Automatic Simulation. The system was simulated by the Wizard-of-Oz [START_REF] Fraser | Simulating speech systems[END_REF]). An ad hoc system was developed in order to support a semi-automatic simulation on two connected SUN SPARC workstations. The Wizard could observe user's actions on a graphicalinterface, where he also composed system answers (Figure 2). Wizard was supported by interface constraints and several prefixed answers. These strategies have been found to increase simulation reliability by reducing response delays and lessening the attention demanded of wizards [START_REF] Oviatt | A Rapid Semi-automatic Simulation Technique for Investigating Interactive Speech and Handwriting[END_REF].

Figure 2. The Wizard Screen in the High Salience condition

All interaction data were recorded in such a way that it is possible to replay the entire experiments with precise information. Each record is actually made up of an audio file, a task evolution file as well as a gesture file, providing accurate numerical data. Data coding. The corpus was analyzed with respect to moving commands: i.e., communication actions aimed at moving targets. Individual commands were defined as single conversational turns produced by users. According to the number of objects displaced by it, each moving command was classified as group-oriented or elementoriented,

The gestural and the verbal part of each group-oriented command were further tabulated according to the strategy adopted to convey the concept of group. Two general strategies were found in the corpus: group-reference andindividual-reference. As far as gestures are concerned, group-reference was achieved by showing the perimeter or area of the group; individual-reference by indicating each element one by one. As regards language, group-reference was achieved by means of plural deictic anchor or target description (i.e., «these objects», «the two isolated objects, the two forms»; in French «ces objets», «les deux objets isolés, les deux formes»); and individual-reference by singular linguistic anchors (i.e., «this item and this item», «this object and also this one » in French «cette pièce et cette pièce», «cet objet ainsi que celui-ci»). At a multimodal level commands were classified as groupreference, mixed-reference, and individual-reference, according to the strategies adopted in each modality (speech and gesture).

Gestures were defined as trajectories in certain parameter space and classified in one of the following categories: 0-d (pointing); 1-d (targetting); 2-d (circling, free-form, scribbling). A first scoring was performed by two independent judges watching the audiovideo logging files. It appeared that pointing could have different degrees of precision. In some cases, it reproduced a very precise point with no movement at all. In others, it resembled a small straight lines or a small spot. To test if these differences were intentional or exclusively due to the gestural interface, a small experiment was run. Using the same simulation procedure that has been previously described, five persons were explicitly required to reproduce the three gestures. A corpus of 285 gestures allowed to discriminate between technical error and intentionality, as well as to set category boundaries. Then 0-d gestures were further classified as: dot, spot or line. Each pointing gesture was a dot when the range of the movement on the x-y axis was inferior to 4 pixels. Otherwise, it was classified as a spot or a line according to the presence or absence of backward movements (x+y/distance< .75 for spots).

Double scoring was conducted for 20% of the reported variables. All measures had a reliability of .95 or above.

Results

A corpus of 98 moving commands has been analyzed. Independently from group salience, a strong preference towards the more economic procedure emerged: 92% of the commands were group-oriented actions. Moreover, with only 3 exceptions, commands were performed multimodally.

As regards reference strategies at the multimodal level, a strong consistency between modalities was found. Only 1 out of 3 commands was based on a mixed strategy. It is worth noticing, that all mixed inputs were composed by verbal group-references amplified by gestural individualreferences; whereas all gestures providing group-references were always accompanied by verbal group-references. Most of the commands (40%) followed an individualreference strategy; 28% a group reference strategy.

The distribution of cases in the three reference categories differs according to group-salience ( 2 = 18.38, d.f.= 2, p< .001). In the High-Salience condition, group-reference was the most frequent strategy, and individual-references occurred as frequently as mixed-references (Table 1). On the contrary, in the Low-Salience condition, individual reference was the most frequent strategy, whereas groupreference was very rare.

Group

Mixed Individual High 46 27 27 Low 5 41 54 Table 1. Percentages of the three reference strategies as a function of experimental conditions.

To summarize, reference at the multimodal level is affected by perceptual field organization. However, the effect is stronger with respect to the gestural part of the input ( 2 =14.96, d.f.= 1 p< .0001) than with respect to the verbal one ( 2 = 6.68, d.f.= 1, p< .01).

A corpus of 184 gestures has been analyzed. As regards gesture dimensions, 0-d was the most frequently used (79%), followed by 2-d (14%), and 1-d (7%). Typically, pointing reproduced a spot (74%), otherwise it was a line (17%), or a spot (9%). To test whether pointing precision was different when users referred to a group or to a single percept, the sample was considerably increased by scoring other experimental scenes requiring to refer only to one element. Moreover, given the higher percentages of dot, only two pointing categories were considered: Highprecision (dot) and Low-precision (spot and line). A crosstabs analysis comparing Access Type (Group vs. Element) to Gesture Precision (High vs. Low) showed a significant difference on frequency distribution in the four cells ( 2 = 5.04, d.f.= 1, p< .05). Dots occurred more frequently in the case of group access (78%) than in the case of percept access (60%). Moreover, when two percepts were identified by a group access mediated by pointing, low-precision gesture occurred more frequently on the first percept (30%) than on the second (3%),  2 = 9.95, d.f.= 1, p< .01. In this case, we found also a clear preference towards the upper-down direction ( 2 = 31.16, d.f.= 2, p< .001). When percepts where displayed on a vertical line, the upper one was pointed out first 82% of the time.

Surprisingly, 2-d gestures were not associated to group reference since they occurred with the same percentages when people referred to group or to individual target. All the circling followed an anti-clockwise direction.

Discussion

Our findings confirm previous results (Oviatt, De Angeli and Khun 1997;[START_REF] Angeli | Visual Display, Pointing, and Natural Language: The power of Multimodal Interaction ,Advanced Visual Interfaces Conference[END_REF] showing that in a visual/spatial domain multimodal communication is highly preferred to the unimodal one (only 3 commands out of 98 were performed unimodally).

As regards commands at a multimodal level, it is worth noticing that gestures were always accompanied by a verbal anchor, in the form of a deictic expression or of a description. This contrasts with previous results (Oviatt, De Angeli and Khun 1997), showing that most multimodal constructions (59%) produced during a multimodal simulation did not contain any spoken deictic. In our opinion, such a difference can be explained considering not only the difficulty for naming the abstract shapes and the interaction language (American vs. French) but also a fundamental distinction in the two interfaces, i.e., the system reaction to user's gestures. Indeed, in the previous simulation the pen provided a detectable feedback to the users' gestures, while in the present simulation no feedback was provided. As showed elsewhere [START_REF] Angeli | Visual Display, Pointing, and Natural Language: The power of Multimodal Interaction ,Advanced Visual Interfaces Conference[END_REF], the presence of a feedback appears to favor the elision of verbal anchors leading to pure referring gesture (Petrelli et. al. 1997). To further investigate the effect of feedback on multimodal communication an experiment, based on the same simulation paradigm described in this paper, is contemplated.

The innovative contribution concerns the influence of perception on multimodal communication. Multimodal commands showed a high correlation between the reference strategies adopted by the two modalities to access groups. However, despite its unfrequent occurrence, the mixed-reference strategy (i.e., a verbal plural-reference accompanied by a gestural individual-reference) may still constitute a problem if multimodal constructions are resolved without considering the visual context. Indeed, the deictic 'these' has to be associated to n gestures (n corresponds to the number of elements forming the group), but not to other eventual gestures occurring to indicate different elements (in our case the boxes where elements had to be moved) associated to separate deictic anchors.

We also demonstrated that the effect perception was stronger on referring gesture rather than on referring NP. This difference underlines the association between perception and physical actions which is higher than between perception and cognitive actions.

Our results lead to the conclusion that group-references occur almost only when the referred group is easily detectable i.e. in the High-Salience condition. Therefore under this condition, it is necessary to extend the pointinginclusion paradigm in order to allow users to express their communicative intentions in a natural way. Such an extension has to consider the variability of gesture forms and meanings, as well as their possible ambiguity. The last phenomenon is due to the non one-to-one relationship between gesture shape and its meaning. Indeed, we have demonstrated that the same gesture can convey different semantic interpretations, as when a pointing action is performed in order to refer either to an individual element of a group or to the whole group; and when a circling is drawn to refer either to inner objects or to strike objects. Semantic ambiguity can be handled considering either the verbal part or the organization of the perceptual context on which the user is acting. Hence the modelization and the implementation are also required to take care of the graphic layout of the user's interface, in order to build robust multimodal reference interpreters.

Gestural ambiguities are often due to the fact that gestures can be based on perceptual groups. The corpus showed other problematic cases, as the ones presented in For instance the targeting gesture, performed in figure 3a, generates an intra-group ambiguity in choosing either the percept or the group. This can be resolved by taking into account the verbal categorization of granularity. The example in figure 3b, presents an inter-group ambiguity whether the gesture is considered as circling or targeting. As opposed to the first example, here the choice of the appropriate referential candidate (between the U-shaped group and the star-shaped percept) has to be made according to a measure of gestural relevance to group or percept, i.e. to the perceptual organization. Such a measure requires to calculate the rate of matching of the gestural trajectory and the perceptual candidates.

To treat these ambiguities, the information flow between the linguistic and the gestural modules has to be defined as illustrated in Figure 4. The linguistic module generates the axiologic structure allowing the gestural module to generate, as a return value, referential hypotheses within their contextual frame (dotted objects are those which do not belong to the returned contextual frame).

Our results are preliminary, but they clearly show the role of perception in multimodal communication. Moreover, they confirm the value of simulation as a tool for building HCIpredictive models that provide design guidelines for effectively integrating motor-visual language and verbal language. Further studies are planned to deeper investigate how users distribute their communication intentions across

Figure

  Figure 1: Examples of axiology a «The green triangles» b «these squares»

Figure 2 .

 2 The difficulty to resolve reference can be explained by intra-group or inter-group competition of possible candidates. a «Mets ces 3 objets ...» b «Deplacez ces objets ...» Put these three objects.. Move these objects... Figure 3. Inter-group and intra-group ambiguities.

Figure

  Figure 4. Information flow between the linguistic and the gestural modules.


Ben Soufian

Vincent Amor

Ivan Levorato
email: vincent.levorato@ephe.sorbonne.fr

Lavallée

Generalized Percolation Processes Using Pretopology Theory

Keywords: Pretopology, percolation processes, complex systems modeling

We propose in this paper a generalization of percolation processes in Z 2 using the pretopology theory. We formalize the notion of neighborhood by extending it to the concept of proximity, expressing different types of connections that may exist between the elements of a population. A modeling and simulation of forest fire using this approach shows the efficiency of this formalism to provide a realistic and powerful modeling of complex systems.

I. INTRODUCTION

Percolation Theory studies the deterministic propagation of a fluid1 on a random medium [START_REF] Grimmett | Percolation[END_REF]. As phase transition phenomenon, an abrupt change in the behavior of the system, observed in percolation processes is a characteristic property of complex systems, percolation theory was successfully applied to model and simulate complex phenomena in statistical physics, economy and recently in social networks. However, percolation processes are based on the neighborhood concept which is not well formalized. It is difficult to express a certain kind of relations between the components of the system such as remote connections, the dynamical evolution of the neighborhood basis, the heterogeneity of the interactions and the hierarchy between the components. For example, to model the spreading of oil in water, of fire through forests or infectious diseases among a population, it is difficult to express the qualitative properties of the system.

In this work, we provide a generalized formulation of percolation processes in Z 2 using pretopology theory [START_REF] Belmandt | Manuel de prétopologie et ses applications[END_REF]. This can be achieved using the pretopological concepts of pseudoclosure and closed subsets. It is a general formalism that expresses different types of connections that may exist between the components of a system. It provides also theoretical tools to express specific phenomena in distributed systems such as the alliance phenomena, acceptability processes and emergence of collective behavior.

The rest of the paper is organized as follows : in section 2, we present an overview of percolation theory. The section 3 concerns a general presentation of pretopology theory. The dynamical aspect of the structural transformation and the neighborhood notion are formalized in section 4. To illustrate the efficiency of our approach we present, respectively in section 5 and 6, a percolation based modeling of forest fire, expressed on a pretopological space, and its simulation. We conclude, in section 7, with a discussion of the results and future work.

II. PERCOLATION THEORY

The first percolation model was introduced by Simon Broadbent et John M. Hammersley in 1957, using the example of a porous stone immersed in a bucket of water. This fundamental question was asked : What is the probability that the center of the stone is wetted? Equivalently, what is the probability that an infinite size percolation cluster of pores exists. This probability depends on the porosity of the stone (i.e. the density of pores). [START_REF] Grimmett | Percolation[END_REF] Physical problems are mathematically modeled as a network of points (or vertices) and the connections (or edges) between each two neighbors may be open (allowing the liquid to pass through) with probability p, or closed with probability (1-p), and we assume they are independent. For a given p, what is the probability that an open path exists from the top to the bottom? Generally the interest concerns the behavior for large n. As is quite typical, it is actually easier to examine infinite networks than just large ones. In this case the corresponding question is : does there exist an infinite open cluster ? That is, is there a path of connected points of infinite length "through" the network. In this case we may use Kolmogorov's zero-one law to see that, for any given p, the probability that an infinite cluster exists is either zero or one. Since this probability is increasing, there must be a critical probability p c such that (figure 1) :

P (p) = 0 if p < p c = 1 if p > p c
where P is the percolation probability which indicates the probability of appearance of the giant cluster in the system.

A model where we open and close vertices rather than edges, is called site percolation (figure 2 a) while the model described above is more properly called bond percolation (figure 2 b). The model where the uncertainty concerns both sites and bonds is called mixed percolation (figure 2 c).

If we consider the percolation processes on Z 2 , for example, we have different models : depending on the chosen neighborhood, on the nature of the studied aspect (dynamic or static Fig. 2. Basic percolation models aspect of a system) and on the nature of the studied object (a specific phenomenon or a property of a system). The most used kind of neighborhoods are the Von Neumann neighborhood and the Moore neighborhood (figure 4). The values of the critical parameters depend on the used neighborhood. We can see in the figure 3 that an infinite cluster (according to a Von Neumann neighborhood) appears abruptly at a critical threshold p c ≃ 0, 6. This value is different if we consider a Moore neighborhood. In fact, with a Moore neighborhood we obtain a giant connected cluster with less density (i.e. probability of active sites.

A. Pretopology formalism

Let us consider a non-empty finite set E, and P(E) designates all of the subsets of E.

1) Pretopological space: Definition 1: A pretopological space is a pair (E, a) (figure 5) where a is a map a(.) : P(E) → P(E) called pseudoclosure and defined as follows : ∀A, A ⊆ E the pseudo-closure of A, a(A) ⊆ E such that :

• a(∅) = ∅ (P 1 ) • A ⊆ a(A) (P 2 )
The pseudo-closure is associated to the dilation process (figure 6).

We can also define a pretopological space (E, i) using the interior map (figure 7). ∀A, A ⊆ E we define the interior i(A) ⊆ E such that :

i(A) = [a(A c )] c • ∀A, A ⊆ E, i(A) ⊆ A
The interior map is associated to the erosion process (figure 8).

Definition 2: Let (E, i, a) be a pretopological space. ∀A, A ⊆ E : 2) V Pretopological space : Definition 3: A V pretopological space (E, i, a) is defined by :

• A is a closed subset if a(A) = A • A is an open subset if i(A) = A
• ∀A, B, A ⊆ E, B ⊆ E and A ⊂ B then a(A) ⊂ a(B) • equivalently i(A) ⊂ i(B)

IV. EXPRESSING A PERCOLATION PROCESS ON A PRETOPOLOGICAL SPACE

Using pretopology we can define a general percolation process including the classical ones and allowing new ones. The advantage of this approach is that it allows us to formulate and treat structural dynamical aspects of complex systems in a unified manner. Percolation processes on Z 2 depend on the neighborhood. Using a neighborhood basis (set of objects of V(x)) expressed in a pretopological space, any neighborhood V (x) can be constructed. The diversity of the connections between the elements can be expressed by adapting the choice of the pseudoclosure to the studied problem.

A. Neighborhood sets

Let (E, i, a) be a V pretopological space. ∀x ∈ E :

V(x) = {V ⊂ E/x ∈ i(V )} V(x) is a family of neighborhoods of x. B. Pretopological transformation in Z 2 ∀A, A ⊆ E, a(A) = {x ∈ E/∀V, V ∈ V (x)
, V ∩A = ∅} If we consider, for example, three different neighborhoods as in figure 9 and construct the associated pseudoclosure the dilation process have different propagation effects (figure 10a,10b,10c).

With the concepts of pseudoclosure, interior and neighborhood sets we can express in a general way different types of connections and take into account their evolution over time by changing their neighborhood basis. An example of the efficiency of this approach is presented in the following paragraph and concerns the forest fire modeling. Our choice was motivated by the fact that this phenomenon exhibits a phase transition behavior [START_REF] Clar | Phase Transition in a Forest-Fire Model[END_REF], which is a common property of complex systems, and the fact that several percolation based models were developed to simulate it. We can also show through it, the difficulty to express a certain kind of qualitative factors using the traditional neighborhood definition.

V. EXAMPLE OF APPLICATION : FOREST FIRE MODELING

A. Percolation and forest fire modeling

In the case of the forest fire modeling, the density of trees is the most important factor. In fact, fire spreads by ignition of nearby trees, and the density of trees decides how far the fire spreads. If the trees are sparse, the fire will burn out before it gets very far. If the forest density exceeds a certain threshold, the fire will burn straight through the forest.

Several percolation based models were presented to simulate the propagation of fire through forests. In these models, generally, trees are arranged in a rectangular grid where the spread of fire is propagated from a tree to its neighbors, defined in an ad-hoc manner. The basic difference between these model is the neighborhood definition (figure 11). For example, some models using a Von Neumann neighborhood are not realistic because they do not take into account the wind effect. For this reason models using the anisotropic percolation or oriented percolation were developed in order to provide a more realistic modeling [START_REF] Von Niessen | Dynamics of forest fires as a directed percolation model[END_REF]. All these models could be considered as particular cases of a general percolation model if the the neighborhood concept was well formalized. With the mathematical definition of the neighborhood expressed in a pretopological space we are able not only to unify percolation processes formalism but also provide a more efficient modeling.

B. Percolation based model of forest fire expressed in a pretopological space

Using the pseudo-closure, we express the propagation process of the fire according to the direction of the wind, defined using the proximity bases determining the neighborhood V(x) (figure 12).

By changing the neighborhood basis we can model the wind direction changes (figure 13). We can also model the consumed trees using the interior mapping (figure 14). The interior map is defined as follows :

∀A, A ⊆ E, i(A) = {x ∈ E/∃V, V ∈ V (x), V ⊆ A} VI. SIMULATION
A preliminary simulation and implementation of the concept of neighborhood and in a pretopological space was performed using Java (figure 15 and16). The user can define until five neighborhood bases (to express the direction of the wind or the presence of an obstacle) and specify the number of the iterations. Trees are generated randomly according to fixed probability (i.e. density) using a slider. We assumed that burning trees will be consumed after three iterations. The results of the simulation are reported in the plot representing the evolution of the consumed trees proportion over time.

VII. CONCLUSION

We showed that interesting concepts developed in pretopology theory may be applied to formalize the neighborhood notion, to generalize percolation processes in Z 2 and to enhance the modeling of complex phenomena and distributed systems. In a future work, we aim to provide a general formalism unifying the mathematical description of percolation processes and cellular automata in order to express the heterogeneity of neighborhoods and local dynamics in asynchronous distributed systems.

Fig. 1 .

 1 Fig.1. Phase transition around the critical probability. Source : in[START_REF] Stauffer | Introduction to Percolation Theory[END_REF]

Fig. 3 .

 3 Fig. 3. Appearance of a giant cluster.

Fig. 4 .

 4 Fig. 4. Moore neighborhood (eight neighbors) and Von Neumann neighborhood (four neighbors).

Fig. 5 .Fig. 6 .

 56 Fig. 5. Pretopological space.

Fig. 7 .

 7 Fig. 7. Interior map.

Fig. 8 .

 8 Fig. 8. Erosion process.

Fig. 9 .

 9 Fig. 9. Examples of neighborhood basis.

Fig. 10 .

 10 Fig. 10. The dilation process with a user-defined neighborhood (in red) and the pseudo-closure (red & blue).

Fig. 11 .

 11 Fig. 11. The neighborhood is the basic difference between various percolation processes.

Fig. 13 .

 13 Fig. 13. By changing the neighborhood basis we model the wind direction changes.

Fig. 15 .

 15 Fig. 15. The propagation process using the successive computation of the pseudoclosure and interior maps.

Fig. 16 .

 16 Fig. 16. The effect of the canges of the wind direction on the propagation process.

The word fluid is considered in the widest sense of the term(water, information, disease, etc.).