Member, IEEE Walid Bechkit

Member, IEEE Yacine Challal

Abdelmalik Bachir

Member, IEEE Abdelmadjid Bouabdallah

Temperature MAC Plug-in for Large Scale WSN

Keywords: Wireless Sensor Networks, Temperature Impact, Connectivity, Energy Saving

The quality of radio communication links decreases with high temperatures. In this paper, we investigate the effect of temperature on percolation-based connectivity in large scale wireless sensor networks and show that more energy can be saved by allowing some nodes to go to deep sleep mode when temperature decreases and links improve. We determine a closedform formula for a threshold network density λ * (τ ) = C 0 πR(τ ) 2 in function of temperature τ . Beyond λ * (τ ), the network percolates and guarantees connectivity. Based on this result, we propose a simple yet efficient Temperature-Aware MAC plugin (TA-MAC) that enables the underlying MAC protocol to dynamically adapt the network effective density to allow further energy savings while maintaining network connectivity. TA-MAC can be potentially used with any wireless MAC protocol. We carried out simulations and demonstrated that BMAC and SCP-MAC augmented with TA-MAC plugin allow a significant energy efficiency improvement.

I. INTRODUCTION

One of the important issues in WSN is network connectivity. Connectivity driven topology management has been widely investigated in the literature and a number of solutions have been proposed. Most of these solutions do not consider the impact of the atmospheric conditions such as temperature on the radio communication range. Temperature has been proven to significantly affect radio communication links negatively, as documented in the data sheets of low power radios [1], [START_REF]CC2530 A True System-on-Chip Solution for 2[END_REF].

When temperature increases, both transmission power and sensitivity decrease which leads to the deterioration of wireless communication links thereby affecting the overall connectivity of the network [START_REF] Bachir | Temperatureaware density optimization for low power wireless sensor networks[END_REF]. As an example, a network designed to operate under typical conditions, i.e. a temperature of 25 • C, will experience connectivity deterioration when temperature increases above 25 • C. Conversely, when temperature decreases below 25 • C, the radio link quality improves, the network becomes over-dimensioned and some nodes become less necessary for the network to remain connected. These nodes are able to go to deep sleep mode to save energy without affecting the connectivity of the network.

In this paper, we consider percolation-based connectivity and determine a closed-form formula for a threshold network density λ * (τ ) = C0 πR(τ ) 2 in function of temperature τ . Beyond λ * (τ ), the network percolates and guarantees connectivity. Based on this result, we propose a temperature-aware MAC Walid Bechkit is with Université de Lyon, INSA-Lyon, CITI-INRIA, Villeurbanne, France. E-mail: walid.bechkit@insa-lyon.fr. Yacine Challal, Abdelmadjid Bouabdallah are with Université de Technologie de Compiègne, HEUDIASYC UMR CNRS 7253, Compiègne, France. E-mails: {ychallal, bouabdal}@hds.utc.fr. Abdelmalik Bachir is with the CS Department, University of Biskra, Algeria. E-mail: a.bachir@univ-biskra.dz. plugin that allows the underlying MAC protocol to dynamically adapts the network effective density to allow further energy savings while maintaining network connectivity. TA-MAC can be potentially used with any wireless MAC protocol.

This paper is organized as follows: in Section II we present an overview of the research carried out on percolation-based network connectivity. In Section III, we present a mathematical model for wireless links and connectivity conditions. In Section IV, we analyze and model the impact of temperature on the communication range of sensor nodes. Next, we propose in Section V a temperature-aware MAC plugin that allows the MAC protocol to minimize energy consumption while ensuring network connectivity under varying temperature conditions. In Section VI, we evaluate our solution according to various criteria including the mean power consumption and traffic load. We show that our temperature-aware MAC plugin allows saving significant amount of energy without affecting network connectivity. In section VII, we present our conclusions.

II. RELATED WORK

First, it is worthwhile to point out that the connectivity in WSN has been mainly studied from two sides: the percolationbased connectivity and the full connectivity. A fundamental result of the percolation theory is that a geometric graph induced by a Poisson Point Process with a constant density λ contains an infinite connected component with non-zero probability if and only if the density is higher than a critical value λ * , we say then that the percolation occurs. In a network context, a node of this largest component can communicate with a high portion of the network. However, we may have many small disconnected components. The existence of an infinite connected component was considered sufficient in many research works, we refer to this paradigm as percolationbased connectivity. The full connectivity (resp. k-connectivity) on its turn guarantees that each pair of nodes can communicate with each others using at least one path (resp. k paths). The conditions of such connectivity were widely studied in the literature and a lot of relations were derived. As we consider large scale WSN, we will focus in what follows on solutions relying on percolation based connectivity.

In [4], Godfrey and Ratajczak proposed Naps, a completely distributed topology control protocol for ad-hoc and sensor networks. Authors considered a network deployed according to an infinite Poisson Point Process (PPP) with a high density, they rely on the percolation-based connectivity and assumed the existence of a critical threshold λ * such that for all density λ > λ * , there is a non-zero probability that a particular node is in an infinite connected component. In Naps, each node waits for a random small amount of time and then starts its time period of length T. At the beginning of this period, it broadcasts a hello message to all its neighbors. If it receives more than c reply messages, it switches off its radio and go to sleep until the end of the period. Otherwise, it remains active for the whole period. The parameter c represents then a threshold value of the average node degree allowing the network connectivity based on percolation. Its value is computed depending on the target density λ * .

In [START_REF] Kong | Distributed energy management algorithm for large-scale wireless sensor networks[END_REF], authors propose a solution very similar to Naps [4] while relying also on the percolation-based connectivity. Authors propose that each node goes to sleep with a probability φ N at each round where N is the degree of the node. Using a degree-dependent dynamic site percolation process modeling, authors proved the existence of the constant φ (2 < φ < ∞) such that the percolation occurs.

On another side, the effect of temperature has been validated independently by many researchers in the literature (e.g. [6] [7]). In [START_REF] Boano | Low-power radio communication in industrial outdoor deployments: The impact of weather conditions and atex-compliance[END_REF] and [START_REF] Boano | The impact of temperature on outdoor industrial wsn applications[END_REF], the authors studied through experiments the impact of the temperature on wireless communication links and data delivery performance in WSN outdoor deployments for industrial process. In [START_REF] Bannister | Wireless sensor networking for hot applications: Effects of temperature on signal strength, data collection and localization[END_REF], the authors separated the effect on the transmitter from the one on the receiver. However, the model they established only provides the reduction in link quality in function of the combined effects at both the transmitter and the receiver. A more accurate information about the effect of temperature on the radio transceivers can be directly obtained from radio circuits data sheets. The effect of temperature is also studied in [START_REF] Baccour | Radio link quality estimation in wireless sensor networks: a survey[END_REF].

As far as we can say, temperature impact on radio link quality has not been taken into consideration in designing MAC protocols for energy saving in low power networks while maintaining network connectivity. This is the aim of our solution that we present through the following sections.

III. SYSTEM MODEL

A. Wireless Network Model

We consider a wireless network where nodes are distributed according to a Poisson Point Process of constant spatial intensity λ in a surface A. All nodes transmit with a full power P t . The power of the signal emitted by Node i and received by Node j is P t L(d ij ), where L(.) is the attenuation function in the wireless medium.

The uncoordinated nature of communication allows multiple transmitters to communicate at the same time, however, creates interference at all receivers. A common connection model in ad-hoc networks is the signal-to-interference noise ratio (SINR) model, where two nodes are connected if the SINR between them is greater than a threshold.

In other words node i can transmit data to node j if the signal received by j is strong enough, compared to noise. Formally, this condition is written as

SIN R ij = P t L(d ij ) N 0 + γ k =i,j P t L(d kj ) ≥ β (1)
where N 0 is the power of the thermal background noise and β is the signal to noise ratio required for successful decoding.

The coefficient γ weights the effect of interferences, depending on the orthogonality between codes used during simultaneous transmissions. Without loss of generality, we will consider

L(d ij ) = ad -b ij ,
where a and b are parameters that describe the wireless channel, b is usually called path loss exponent.

Using this transmission condition, the network can be modeled with a graph G(N, E) where N is the set of nodes, and

E = (i, j) ∈ N × N, st. SIN R ij ≥ β.

B. Radio Communication Range

We define the radio communication range R as the range that allows a successful transmission according to the condition in equation 1, in the absence of interference (γ = 0). In this case, if we neglect the thermal floor noise (γ = 0 and N 0 = 0) the successful transmission depends on the power of the received signal, referred to as P r , which is equal to the power radiated by transmitter after attenuation:

P r = P t L(d) (2) = P t ad -b (3)
The minimum power of P r that allows successful transmission is called sensitivity, and is referred to as P s .

The previous equation ( 3) can be used to express the relation between the sensitivity P s and the communications range R. We have:

P s = aR -b P t (4)
Thus, the radio communication range can be quantified according to the following equation:

R = a P t P s 1/b (5)
If we consider that our sensor network is deployed out-door, one of the most accurate model for the path loss is the two-ray ground propagation model. In the two ray ground model, the values of a and b are the following:

a = G t G r H 2 t H 2 r (6) b = 4 (7)
where G t (resp. G r ) is the antenna gain at the transmitter (resp. receiver), and H t (resp. H r ) is the antenna height at the transmitter (resp. receiver).

C. Percolation condition under the physical model

Kleinrock and Silverster [START_REF] Kleinrock | Optimum transmission radii for packet radio networks or why six is a magic number[END_REF] studied the conditions to have an asymptotically connected network in radio networks. Authors assume that nodes are randomly distributed according to a Poisson Point Process (PPP) and found that the minimum required number of neighbors is equal to six, the 'magic number' as they called it. This 'magic number' was after that revised to eight in [START_REF] Takagi | Optimal transmission ranges for randomly distributed packet radio terminals[END_REF].

In [START_REF] Philips | Connectivity properties of a packet radio network model[END_REF] authors, proved that there is no magic number and that if the number of neighbors is constant the network will be disconnected when the region became large. They showed that for an infinite area there exists an infinite connected component (percolation) with non zero probability if the number of neighbors πR 2 λ > C 0 for some critical value 2.198 < C 0 < 10.526.

Following this condition, the minimum density required to induce network percolation is then given by :

λ * = C 0 πR 2 (8)
The minimal density in equation 8 that induces network percolation has been derived for networks without interference (γ = 0). Dousse et al. have demonstrated in [START_REF] Dousse | Percolation in the signal to interference ratio graph[END_REF] that if a threshold density λ * exists, with γ = 0 (no interference), so that ∀λ ≥ λ * the network percolates, then under the generalized physical model with interferences, there exists γ > 0 such that the network percolates ∀λ ≥ λ * . In other words, if some threshold density λ * induces network percolation under the simplified model (γ = 0, no interferences) then there exist some orthogonal coding through time or frequencies (γ > 0) such that the network percolation occurs also.

Following this result, we will consider λ * in equation 8 as the critical value that induces network percolation under the generalized physical model.

IV. EFFECT OF TEMPERATURE

A. On Communication Range

There is increasing evidence that high temperature affects both the transmitter and the receiver. In [START_REF] Boano | Low-power radio communication in industrial outdoor deployments: The impact of weather conditions and atex-compliance[END_REF] and [START_REF] Boano | The impact of temperature on outdoor industrial wsn applications[END_REF], Boano et al. studied through experiments the impact of the temperature on wireless communication links and data delivery performance in WSN outdoor deployments for industrial process. In [START_REF] Bannister | Wireless sensor networking for hot applications: Effects of temperature on signal strength, data collection and localization[END_REF], the authors separated the effect on the transmitter from the one on the receiver. However, the model they established only provides the reduction in link quality in function of the combined effects at both the transmitter and the receiver. A more accurate information about the effect of temperature on the radio transceivers can be directly obtained from radio circuits data sheets. For instance, the data sheet of the widely used low-power radio CC2400 [1] provides quantitative information which shows that the values of P s and P t are not constants but are affected by temperature change. Therefore, we use the the notation P t (τ t ) (resp. P s (τ r )) to express the variation of the transmission power (resp. sensitivity) in function of the temperature τ t (resp. τ r measured at the transmitter (resp. receiver). Consequently, the radio communication range is also affected by the temperature at the transmitter and the receiver. Therefore, we have:

R(τ t , τ r ) = a P t (τ t ) P s (τ r ) 1/b (9)
The forms of the function P t (τ ) (resp. P s (τ )) depend on the radio chips. Some manufacturers provide data about this variation for some temperature values, e.g. CC2400 [1] and CC2530 [START_REF]CC2530 A True System-on-Chip Solution for 2[END_REF]. A closed-form expression for P t (τ t ) (resp. P s (τ r )) is not provided. However, the data provided in the data sheet allows to use regression to find the closed polynomial representations for P t (τ t ) and P s (τ r ).

B. On Percolation

As shown in section IV-A, the transmission range is not fixed but changes according to temperature at the transmitter τ t and temperature at the receiver τ s . For the sake of simplicity, we consider that the network is deployed over homogeneous area in which the same temperature is measured at all the nodes, i.e. τ t = τ r . In this case, we use τ to refer to temperature. For simplicity, we use the notation R(τ ) instead of R(τ t , τ r ). Similarly, the critical density that induces network percolation also depends on the temperature. Therefore, we have:

λ * (τ ) = C 0 πR(τ ) 2 (10)
V. TEMPERATURE-AWARE MAC PLUGIN FOR ENERGY

SAVING

In this section, we propose a simple yet efficient MAC plugin that adapts node's transceiver activity to ensure network connectivity while minimizing energy consumption, under varying temperature conditions. The underlying algorithm switches on and off nodes' transceivers in function of temperature. This algorithm guarantees that only those nodes that need to be on to ensure percolation and/or send data are operating. The others switch their transceivers off to save energy.

We use in what follows τ + to refer to the maximum temperature. To ensure connectivity in the worst case, the initial density of nodes should be equal to λ * τ + . We assume that Aλ * τ + nodes are initially deployed over the deployment area A following a Poisson Point Process. We assume also that nodes use the default transmission power level which is supposed to be the maximum transmission level (This is the case of most radio chips like CC2400, CC2420, CC1100, etc.). When the temperature τ is lower than τ + , a lower density is sufficient. We propose thus to put some nodes in sleep mode, and by doing so a sizable amount of energy can be saved.

We propose to calculate ρ τ = λ * τ /λ * τ + which represents the ratio of network density that is required to maintain connectivity when the temperature is τ compared to the initial deployment where the density is calculated according to the highest temperature. The value of ρ τ also represents the number of nodes required to be on when temperature is equal to τ compared to that when temperature is equal to τ + . By using equation [START_REF] Kleinrock | Optimum transmission radii for packet radio networks or why six is a magic number[END_REF], we obtain:

ρ τ = λ(τ ) λ(τ + ) (11) = C 0 πR(τ ) 2 × πR(τ + ) 2 C 0 (12) = R(τ + ) 2 R(τ ) 2 (13)
The idea of our approach is then to keep the ratio of active nodes equal to ρ τ at temperature τ . Note that, by selecting nodes which go off randomly, the distribution of the nodes which remain on maintains the same characteristics, i.e. distributed according to PPP (thanks to the thinning property of PPP). We also assume that each node is able to know its temperature (temperature sensor readings, extraction from log files, computation, expectation, etc.). Our approach called TA-MAC relies on algorithm 1 that is executed by every node periodically (a predetermined period of time) without the need to exchange information with other nodes.

VI. PERFORMANCE EVALUATION

In this section, we evaluate the energy efficiency of the proposed solution and compare it to existing MAC protocols that are not temperature-aware. First, we present the temperature model and the MAC protocols along with the energy model used in simulations. Next, we give and discuss the simulation results.

A. Temperature model

We refer to the ERBS's model [START_REF] Erbs | Models and applications for weather statistics related to building heating and cooling loads[END_REF] as derived in [START_REF] Bilbao | Air temperature model evaluation in the north mediterranean belt area[END_REF] where the average normalized diurnal temperature variation is represented by: τ (y, m, t) = τ (y, m) + A τ (y, m) [0.4632 cos(γ(t) -3.805) + 0.0984 cos(2γ(t) -0.360) + 0.0168 cos(3γ(t) -0.822) + 0.0138 cos(4γ(t) -3.513)]

where γ(t) = 2π(t -1)/24 ; t is the time in hour; τ (y, m) is the daily monthly mean air temperature; and A τ (y, m) is the monthly mean thermal amplitude in degrees Celsius [START_REF] Bilbao | Air temperature model evaluation in the north mediterranean belt area[END_REF]. For τ (y, m) = A τ (y, m) = 25 • C, figure 2 top shows the temperature variation throughout the day (time in hours).

B. MAC protocols

In order to evaluate the efficiency of TA-MAC, we will consider two MAC protocols for WSN: BMAC [START_REF] Polastre | Versatile low power media access for wireless sensor networks[END_REF] and SCP-MAC [START_REF] Ye | Ultra-low duty cycle mac with scheduled channel polling[END_REF]. BMAC is one of the most deployed protocols in WSN as it is the default protocol in most of the sensor node prototypes (Micaz, Mica-2, etc.) that rely on the operating system TinyOs. BMAC achieves high energy savings through the use of preamble sampling technique (see [START_REF] Bachir | Mac essentials for wireless sensor networks[END_REF] for a survey on these protocols) where nodes spend most of their time in sleep mode, but only wake up from time to time to check for incoming traffic. To make sure that a node does not miss an incoming data packet, each node prepends its data packet transmission with a preamble that is long enough so that any potential receiver will wake up during the transmission of the preamble. When a node wakes up and detects a preamble being transmitted, it keeps receiving it until it decodes the data packet. A more advanced version of preamble sampling is SCP-MAC in which nodes synchronize on a common sleep/wake schedule to reduce the overhead of sending long preambles.

C. Energy consumption model

We propose to evaluate P (Joules/s) the average power consumed by a node. The power P depends on many parameters such as the energy consumption of the micro-controller and the radio. For the sake of conciseness and simplicity, we consider only the power consumed by the radio which is dominant. The energy consumed by the radio depends on the underlying MAC protocol.

We use the analytical model developed in [START_REF] Ye | Ultra-low duty cycle mac with scheduled channel polling[END_REF] for the evaluation of the energy consumption of the BMAC [START_REF] Polastre | Versatile low power media access for wireless sensor networks[END_REF] and SCP-MAC [START_REF] Ye | Ultra-low duty cycle mac with scheduled channel polling[END_REF] protocols. We have:

P = P tx + P rx + P pl (14)
where P tx (resp. P rx , and P pl ) is the average power drained in transmission (resp. reception and channel sampling). We evaluate the mean power consumption on the flooding; therefore, each node transmits one packet and receives η(τ ) packets, where η(τ ) is the number of neighbors. The average power drained during transmission (resp. reception and channel sampling) is:

P tx = (T p + T data ) • P tx • r data (15)
P rx = η(τ ) • (T p /2 + T data ) • P rx • r data (16)
P pl = (T pl /T p ) • P pl (17)
where P tx (resp. P rx , and P pl ) is the power drained during the transmission (resp. reception and channel sampling). T data is the transmission duration of one data packet, T p is the channel sampling interval, T pl is the duration of channel sampling, and r data is the packet rate. We note that we assume that there are no transmission errors, and thus no retransmissions. We note that P pl which is the power drained during the sampling of the channel can be considered to be equal to P rx .

D. Simulation results

We conducted extensive simulations in order to evaluate the power consumption of our approach and compare it to MAC protocols that are not temperature-aware. We evaluate also the impact of our solution on the network connectivity. We give in Table I the common simulation parameters.

1) Impact of temperature on power consumption: In this subsection, we compare power consumption when varying temperature from -20C to +80C. We plot in Figure 1 the impact of temperature on power consumption per node when The figure shows that TA-MAC approach presents a significant improvement in terms of power consumption compared to MAC protocols without temperature awareness. This is due to the proposed temperature-aware sleep scheduling. Indeed, at each round a fraction of nodes (1 -ρ τ ) turn their radio off which allows to save a significant amount of energy.

2) Average power consumption: In this subsection, we compare the average power consumption per node when using BMAC and SCP-MAC as MAC protocols and when using the same protocols augmented with our Temperature-Aware MAC approach. We recall that nodes are initially deployed considering the highest possible temperature (with a density equal to λ τ + ).

The mean power consumption when a given node is on is given in Eq. ( 14) and we assume that the power consumption when the node is off is equal to zero. Indeed, as explained before, the most important amount of energy is consumed by the radio and the power consumption can be negligible whenever nodes turn their radios off. We plot in Figure 2 the obtained results when considering the CC2400 radio chips and the two ray ground model (parameters are given in Table I).

Figure 2 shows that by using the basic MAC protocols where nodes do not use temperature aware energy saving, the average power consumption increases when the temperature decreases and vice versa. Indeed, when the temperature the communication range becomes higher and the number of potential neighbors of each node increases which increases the power drained by the data reception.

On the other hand, the figure shows clearly that the TA-MAC algorithm outperforms the other approaches thanks to sleep scheduling. When the temperature decreases, the communication range becomes higher which reduces the fraction of nodes required to guarantee the network percolation. This allows to save more energy since more nodes will turn off their radios. The results show that the TA-MAC algorithm allows to save a sizeable amount of energy which ranges from 0% when the temperature is maximum to about 50% (for BMAC) and 40% (for SCP-MAC) when the temperature is minimum.

3) Impact of data rate on energy savings: In Figure 3, we study the effect of traffic load variations on the mean power consumption of our Temperature MAC Plugin. We show that there is a significant difference between BMAC and SCP-MAC without our Temperature MAC Plugin and the same protocols with the Plugin. The difference in energy consumption is particularly high with BMAC because nodes running BMAC use long preambles and thus consume more energy than those running SCP-MAC in which nodes spend more time in sleep mode. Therefore, the effect of using Temperature MAC Plugin is less visible with MAC protocols having a very high sleep mode ratio and in lighter traffic loads.

4) Impact of Check Interval variation: In Figure 4, we vary the check interval (T p ) and plot the induced mean power consumption. For BMAC, we notice that there is an optimal value (0.075s for the configuration setup we used) for the check interval where the mean power consumption is minimized (Note that BMAC has a limited duty cycle [START_REF] Polastre | Versatile low power media access for wireless sensor networks[END_REF] because longer check intervals involve longer preamble transmissions and result in higher energy consumption. Therefore, the amount of energy savings that can be achieved with BMAC is limited). For values smaller than 0.075s more energy is 3. Energy savings with respect to data rate consumed because nodes spend more time in checking the channel waiting for incoming data. Smaller check intervals are only interesting for delay constrained applications. However, we notice that the optimal value for the check interval with TA-BMAC is significantly larger than that of BMAC which offers the possibility of using higher duty cycles thereby allowing higher amounts of energy savings. The reason why TA-BMAC has a higher check interval is because it has smaller number of neighbors which limits the amount of energy spent at the reception side. Also, with TA-BMAC, nodes that are not selected to continue to operate normally, will go into deep sleep mode where they do not transmit packets, which results in lesser energy spent in transmission (particularly the long preamble). For SCP, there is no limitation for the check interval and the energy consumption continues to decrease when the check interval increases. The same behavior is observed with TA-SCP.

VII. CONCLUSION

In this paper, we proposed a temperature-aware MAC plugin that can be used with potentially all existing WSN MAC protocols to make them even more energy efficient in environment where temperature variations are frequent and significant. We have shown that TA-MAC is relatively simple to implement and provides substantial benefits for large scale networks by adapting node's transceiver activity to ensure percolationbased connectivity under varying temperature conditions.

Algorithm 1 :1 6

 16 TA-MAC (Input: MAC protocol) Obtain temperature τ for the round: 2 Compute ρ τ 3 if Node has data to send then 4 Run underlying MAC protocol for the entire round 5 else Pick p a random value : p ∈ [0, 1] 7 if (p < ρ τ ) then 8 Run underlying MAC protocol for the entire round 9 else 10 Off: go to sleep mode for the entire round 11 end 12 end

Fig. 1 .

 1 Fig. 1. Impact of Temperature on Power Consumption

Fig. 2 .

 2 Fig. 2. Top: Temperature variations. Bottom: Mean power consumption per node

  Fig. 3. Energy savings with respect to data rate

Fig. 4 .

 4 Fig. 4. Energy savings in function of check interval

This work is funded in part by the French Government, through the program Investments for the future managed by the National Agency for Research (Reference ANR-11-IDEX-0004-02), and under the framework of the Labex MS2T, the Algerian Ministry of Higher Education and Scientific Research under contract B*01420130132.


TRIP CHAINING : THE PARADOX OF THE DAILY MOBILITY KIEFFER Lionel, Aix-Marseille Université, France lionel. kfr@gmail.com Please insert here the affiliations' logo(s)

Changes in daily mobility have increased the phenomenon of trip chaining. According to the logic of saving time and money, without chaining several trips back home involves a redefinition of the global parameters of modal choice. For this type of practice, the car seems much more appropriate. More flexible, it is still preferred by residents of suburban and rural areas who come in large cities mode.

This reorganization of daily practices to conflict two aspects to the extent the car is both the unchanging symbol of individualization but also the nonsustainability of mobility. The era of all-auto seems to take a turning point, it is necessary on the part of public policy to provide users with viable alternatives. This offer will be both powerful and flexible enough to encourage people to rationalize the use of their personal vehicle. To answer this contemporary issue , we wish to propose an intermediate situation between the whole car and public transport , all as required by policy . Intermodality, aided by an appropriate infrastructure (Park and Ride shuttle commuter town center , etc. . ) Becomes an alternative for those still in the grip of "freedom" offered by the use of a vehicle personnel.

However, this proposal depends on many factors. Knowledge of trajectories for individual mobility, the location of activity zones, are the first items to be recognized. Must analyze and understand the organizational processes of the day of a person. The choices of stops are made at a specific moment of daily activity program. Today is just the difficulty in predicting traffic. It is now necessary to understand each trip to then situate in the whole chain of travel and in the daily program.

Outlook study

There is a paradox between the desire to limit car use and practical developments chaining trips. The economic logic of mobility forces today to streamline the time and distance of travel, in direct contradiction with the main limit of public transport, namely a relatively slow and strong time dependence. All the current challenge is to reconcile sustainable mobility and efficiency in the service.


Véronique Terrier
email: veronique.terrier@unicaen.fr

Recognition of linear-slender context-free languages by real time one-way cellular automata

A linear-slender context-free language is a context-free language whose number of words of length n is linear in n. Its structure has been finely characterized in a work of Ilie, Rozenberg and Salomaa. Thanks to this characterization, we show that every linear-slender context-free language is recognizable by a real time one-way cellular automaton.

Introduction

One-way cellular automaton (OCA) is one of the simplest parallel recognizing devices. Since its introduction by Dyer [START_REF] Dyer | One-way bounded cellular automata[END_REF], it has been the subject of much interest. Numerous studies have been directed towards the real time OCA, the class of languages decidable in minimal time, and have already provided a good understanding of its abilities and limitations.

In particular, it is known that the real time OCA and the family of context free languages are incomparable [START_REF] Terrier | On real time one-way cellular array[END_REF]. This calls into question which languages they have in common. That is not the case for deterministic CFL: there exits a LL(1) CFL which is not a real time OCA one [START_REF] Okhotin | Comparing linear conjunctive languages to subfamilies of the context-free languages[END_REF]. On the other hand, linear CFL and visible pushdown languages have been proved to be real time OCA ones [START_REF] Čulík | Systolic trellis automata. I, II[END_REF][START_REF] Okhotin | Comparing linear conjunctive languages to subfamilies of the context-free languages[END_REF].

With the aim to identify more common languages, we will take into consideration the counting function that measures the number of words of length n in the language. Noticing that all CFL known to be not real time OCA have their counting function of exponential order, the best is to look at sparse languages. These are the poly-slender CFL whose counting functions are polynomial in n and, more specifically, the linear-slender CFL whose counting functions are linear. The purpose here is to show that linear-slender CFL are real time OCA ones.

The present work essentially relies on a paper by Ilie, Rozenberg and Salomaa which presents a characterization of poly-slender CFL in terms of Dyck loops [START_REF] Ilie | A characterization of polyslender context-free languages[END_REF]. Čulík's OCA which recognizes in real time the language {a n b n+m a m : n, m ≥ 0} and Okhotin's characterization of real time OCA by linear conjunctive grammars will come also into play [START_REF] Čulík | Variations of the firing squad problem and applications[END_REF][START_REF] Okhotin | On the equivalence of linear conjunctive grammars and trellis automata[END_REF].

Preliminary

Basic notions

We first recall some basic definitions and notations.

For any language L, the number of words in L of length n is denoted by n (L). For an integer k,

a language L is k-poly-slender if n (L) is in O(n k ). A language L is poly-slender if L is k-poly-slender for some k. A language L is linear-slender if n (L) is in O(n).
A language L is bounded if there exists a finite number of words

u 1 , u 2 , • • • , u k such that L ⊆ u * 1 u * 2 • • • u * k .
For any word w ∈ Σ + , the primitive root of w is denoted by ρ(w) and corresponds to the minimal word such that w ∈ (ρ(w)) * .

Poly-slender context free languages

We review the definitions and results presented in [START_REF] Ilie | A characterization of polyslender context-free languages[END_REF] that will be fundamental ingredients throughout this paper.

Definition 1 (Dyck loop). Let z = z 1 z 2 • • • z 2k be a Dyck word on {[, ]} of length 2k
. Let l i and r i denote the respective positions of the i-th opening parenthesis [ and its corresponding closing one ] in z. Given some words y 0 ,

• • • , y 2k , x 1 , • • • , x 2k , consider the map h n1,••• ,n k (z 1 z 2 • • • z 2k ) = y 0 x e1 1 y 1 x e2 2 y 2 • • • x e 2k
2k y 2k where each pair of parentheses shares the same exponent: The structure of poly-slender CFL finely corresponds to Dyck loops: Theorem 1. For any k ≥ 0, a context-free language is k-poly-slender if and only if it is a finite union of (k + 1)-Dyck loops.

e li = e ri = n i . A k-Dyck loop is any set D = {h n1,••• ,n k (z 1 z 2 • • • z 2k ) : n i ≥ 0}
The following notion captures whether the position of some word w can be distinguished or not.

Definition 2 (Link). Let u, v ∈ Σ + and w ∈ Σ * . The word w links u with v (link(u, w, v)) if and only if ρ(u)w = wρ(v). That means ρ(u) = pq, ρ(v) = qp and w = (pq) * p for some p, q. And so u m wv n is a prefix of (pq) * Example 3. With x i and y i as defined in Example 1, link(x 4 , y 4 , x 5 ) holds but link(x i , y i , x i+1 ) does not hold for i = 1, 2, 3, 5. With x i and y i as defined in Example 2, link(x 2 , y 2 , x 3 ) holds but neither link(x 1 , y 1 , x 2 ) nor link(x 3 , y 3 , x 4 ) holds.

We will make great use of the following lemma: Lemma 1. Consider some words x i ∈ Σ + and y i ∈ Σ * , and some non-negative

integers n i , m i . Denote w = y 0 x n1 1 y 1 x n2 2 y 2 • • • x nr r y r , w = y 0 x m1 1 y 1 x m2 2 y 2 • • •
x mr r y r and assume that link(x i , y i , x i+1 ) holds for no i. Then there is a constant N 0 , depending only on the lengths of the words x i and y i , such that, if n i , m i are larger than N 0 and there is i with n i = m i , then w = w .

For a general overview, we recall the result of Latteux and Thierrin [START_REF] Latteux | On bounded context-free languages[END_REF] and the one of Ginsburg and Spanier [6]: Theorem 2. A context-free language is poly-slender if and only if it is bounded. Theorem 3. The family of bounded languages is the smallest family which contains all finite languages and is closed under the following operations:

1. union 2. catenation 3. (x, y) L = n≥0
x n Ly n for any x, y words

Real time one-way cellular automaton

A one-way cellular automaton is a one-dimensional array of finite automata (the cells) indexed by N. The cells evolve synchronously at discrete time steps. Each cell takes one value from a finite set of states Q. At each step, the evolution of a cell is defined by its own state and the state of its right neighbor according to a transition function δ. Formally, denoting c, t the state of the cell c at time t, c, t

+ 1 = δ ( c, t , c + 1, t ).
In order that an OCA acts as a language recognizer, we specify two subsets of Q: the alphabet Σ of input symbols and the set of accepting states Q accept . The input mode is parallel. At initial time 0, the i-th bit of the input word w ∈ Σ * is fed to the cell i: i, 0 = w i . An OCA is said to accept (resp. reject) a word w in real time, if on input w the cell 0 enters an accepting (resp. non-accepting) state at time |w| -1. It corresponds to the minimal time for the cell 0 to know the whole input. A language is a real time OCA language if there exists some OCA (Q, Σ, Q accept , δ) which accepts in real time exactly the words w ∈ L.

The computation of an OCA is usually represented by a time-space diagram (see Fig 1). The t-row corresponds to the cellular array at time t. Only those sites involved in the real time computation are depicted. As a matter of fact, there are two topologically equivalent ways to display the time-space diagram. We will use here the bilateral symmetric layout, i.e., the right one. The real time OCA class is robust: introducing the notion of conjunctive grammar, Okhotin has exhibited a characterization of real time OCA in terms of a generating device [START_REF] Okhotin | On the equivalence of linear conjunctive grammars and trellis automata[END_REF]. Let us recall its statement, it will be one of the main ingredients in this paper. An alternating grammar is a grammar enhanced with a conjunctive operation symbolized by &. Denoting N the set of variables and Σ the set of terminals, each production is of the form

A → α 1 & • • • & α k where A ∈ N and α 1 , • • • , α k ∈ (A ∪ Σ) *
. Such a production denotes that the language generated by A is the intersection of the languages generated by α 1 , • • • , α k . Analogously to linear context free grammars, a linear conjunctive grammar is defined as an alternating grammar with the restriction that for every production

A → α 1 & • • • & α k ,
no α i has more than one instance of a variable. An algorithm describing how to recognize any linear CFL on a real time OCA was already known [START_REF] Čulík | Systolic trellis automata. I, II[END_REF]. More radically, to extend linear context free grammars with the conjunctive operation & leads to a complete characterization of real time OCA [START_REF] Okhotin | On the equivalence of linear conjunctive grammars and trellis automata[END_REF]: Theorem 4. A language L is recognized in real time by an OCA if and only if L is generated by a linear conjunctive grammar.

Let us recall the conversion from a real time OCA to a linear conjunctive grammar that we will need later. See Fig. 2 to get some insight about the translation.

Lemma 2. Given any language L recognizable by some real time OCA A = (Q, Σ, Q accept , δ), L is generated by the linear conjunctive grammar G = (Σ, {S} ∪ {A q : q ∈ Q}, S, R) where R contains the following rules:

S → A q for all q ∈ Q accept A a → a for all a ∈ Σ A δ(g,d) → A g b & cA d for all g, d ∈ Q and all b, c ∈ Σ
At last, let us give some examples and properties of real time OCA to illustrate their abilities and limits. The Dyck language, the linear-slender CFL {a n b n+m a m : n, m ≥ 0}, the inherently exponentially ambiguous CFL L * with L = {a i b j c k : i = j or j = k} [START_REF] Naji | Ambiguity of context-free languages as a function of the word length[END_REF], the non CFL languages {a n b n c n : n ≥ 0} and {a n b 2 n : n ≥ 0} with a non semilinear Parikh image, are all real time OCA languages. In addition, real time OCA languages include all linear CFL and visible δ(g, d)

g d c • • • w • • • b cw ∈ LG(Ag) wb ∈ LG(A d ) cwb ∈ LG(A δ(g,d) ) Fig. 2. The OCA's transition δ(g, d) is converted into the rule A δ(g,d) → Agb & cA d
pushdown languages [START_REF] Čulík | Systolic trellis automata. I, II[END_REF][START_REF] Okhotin | Comparing linear conjunctive languages to subfamilies of the context-free languages[END_REF]. On the other hand, several languages are known not to be real time OCA: all non regular languages over a one letter alphabet, the inherently ambiguous CFL L 1 L 1 square of the linear CFL L 1 = {1 k 0u10 k : k > 0, u ∈ {0, 1} * }, the language {uvu : u, v ∈ {0, 1} * , |u| > 1}, the deterministic CFL (to be more precise: [START_REF] Terrier | On real time one-way cellular array[END_REF][START_REF] Terrier | Language not recognizable in real time by one-way cellular automata[END_REF][START_REF] Okhotin | Comparing linear conjunctive languages to subfamilies of the context-free languages[END_REF]. Further, the real time OCA class is closed under boolean operations, reverse, operation (the one defined in Theorem 3), left and right concatenation with regular languages. The proofs are folklore. A contrario, the real time OCA class is not closed under morphism, concatenation, Kleene star and cycle [START_REF] Čulík | Systolic trellis automata: Stability, decidability and complexity[END_REF][START_REF] Terrier | On real time one-way cellular array[END_REF][START_REF] Terrier | Closure properties of cellular automata[END_REF].

LL(1) language) {c m a l0 ba l1 b • • • a lm b • • • a lz bd n : m, n, l i ≥ 0, z ≥ 1, l m = n} [1,

Poly-slender context free languages and real time one-way cellular automata

The question behind this paper is whether the poly-slender CFL are real time OCA languages. According to Theorem 3, the poly-slender CFL are the smallest family which contains all finite languages and is closed under union, concatenation and operation. Of course, real time OCA languages include all finite languages and are closed under union and operation. This is easy to prove using the grammar characterization of real time OCA. The problematic point is concatenation: can we assert that the concatenation of two Dyck loops is a real time OCA language? We do not answer this question but in the simple case: 1-Dyck loops. Precisely we will show the following result:

Theorem 5. Linear-slender context-free languages are recognizable in real time by one-way cellular automata.

The rest of the paper will be devoted to the proof of this theorem. Concretely we have to show that 2-Dyck loops are recognized in real time by OCA.

It remains to examine the most technical case where y 2 links x 2 with x 3 but link(x i , y i , x i+1 ) does not hold for i = 1 and i = 3. As y 2 links x 2 with x 3 there exists some p, q and α, β, γ such that x 2 = (pq) α , x 3 = (qp) β and y 2 = (pq) γ p. Then x n1 1 y 1 x n2 2 y 2 x n3 3 y 3 x n4 4 can be rewritten as x n1 1 y 1 (pq) αn1+βn3+γ py 3 x n3 4 . Setting z 1 = x 1 , z 2 = y 1 , z 3 = pq, z 4 = py 3 , z 5 = x 4 , such 2-Dyck loops can be reshaped into z n1 1 z 2 z αn1+βn3+γ 3 z 4 z n3 5 with the properties that z 2 does not link z 1 with z 3 and, readily verifiable, z 4 does not link z 3 with z 5 . So our task is to show that {z n 1 z 2 z αn+βm+γ 3 z 4 z m 5 : n, m ≥ 0} is a real time OCA language. It will be done in two steps:

1. Given a five letters alphabet A = {a 1 , • • • , a 5 }, whatever α, β ≥ 1 and γ ≥ 0 are, we will present a real time OCA which recognizes the language L α,β,γ = {a n 1 a 2 a αn+βm+γ 3 a 4 a m 5 : n, m ≥ 0}. 2. For any homomorphism h on A such that neither link(h(a 1 ), h(a 2 ), h(a 3 ))

nor link(h(a 3 ), h(a 4 ), h(a 5 )) holds, we will verify that h(L α,β,γ ) is a real time OCA language.

Proposition 1. The language L α,β,γ = {a n 1 a 2 a αn+βm+γ 3 a 4 a m 5 : n, m > 0}, where the symbols a 1 , • • • , a 5 are distinct, is recognizable in real time by an OCA.

Proof. The main ingredient is Čulík's OCA which recognizes in real time the language {a n b n+m a m : n, m ≥ 0} [START_REF] Čulík | Variations of the firing squad problem and applications[END_REF]. His construction makes ingenious use of a firing squad synchronization. Let us begin by recalling the process (see Fig. 3). For convenience, we identify the sites of the OCA with integer coordinates (x, y) where x + y is even. In this way, the input symbols are placed at positions (2x, 0). The unique symbol a 2 is chosen to be at the origin (0, 0) and, when the input is of shape a + 1 a 2 a j 3 a 4 a + 5 , the unique symbol a 4 is at (2j + 2, 0). The process is set up using a firing squad synchronization with two generals G g and G d located according to the unique symbols a 2 and a 4 . Precisely, the left general G g is at [START_REF] Čulík | Systolic trellis automata. I, II[END_REF][START_REF] Dyer | One-way bounded cellular automata[END_REF] and the right general G d at (2j -1, 5). Thus the synchronization occurs at points (1 + 2k, 1 + 2j) for all k with 0 < k < j. We check that the k-th firing points (1 + 2k, 1 + 2j) corresponds to the output of the input subword which begins at (2(k -j), 0) and ends at (2(1 + j + k), 0), namely the subword a j-k 1 a 2 a j 3 a 4 a k 5 . Next, Čulík showed that the construction can be adapted to recognize the languages {a i b j a k : i, k ≥ 0, mj + c = i + k} for all m ≥ 1, c ≥ 0. Actually, the same approach works in these more general settings: it exists a real time OCA deciding the language L α,β,γ = {a i 1 a 2 a j 3 a 4 a k 5 : i, j, k ∈ N, j = αi + βk + γ} for every non-negative rational numbers α, β, γ. Let us outline the modified construction. Be warned that we will use rational coordinates but the technique to revert to an OCA diagram is standard. Firstly observe that we may reduce the range of the synchronization in locating the two generals later: with the left general G g at (3 + γ, 5 + γ) and the right general G d at (2j -1 -γ, 5 + γ), the set of firing points becomes {(1 + 2k + γ, 1 + 2j -γ) : k ∈ N, 0 < k < j -γ}. We explain now the construction in terms of geometric transformations. It will be achieved by the composition of two directional scalings (see Fig. 4). Initiated from the unique symbol a 2 , the first transformation starts at point (0, 0) and applies on its cone of consequences {(c, t) : |c| ≤ t}, i.e., the future light cone of (0, 0) which encompasses the set of points impacted by (0, 0). It leaves the line t = c stable and scales by the factor 1/α in the up-left to downright direction according to the map M g = (1+α)/(2α) (α-1)/(2α) (α-1)/(2α) (1+α)/(2α) . Observe that the transformation is workable. Inside the cone, the neighborhood constraints are satisfied. The right side of the cone is stable. And the computation on the subword a + 1 occurring below the left side can easily be scaled. The second transformation is symmetric. Initiated from the unique symbol a 4 , it starts at point (2j + 2, 0) and applies on its cone of consequences {(c, t) : |c -2j -2| ≤ t}. It leaves the line t + c = 2j + 2 stable and scales by the factor 1/β in the up-right to down-left direction according to the map M d = (1+β)/(2β) (1-β)/(2β)

(1-β)/(2β) (1+β)/(2β) . Now, the composition of these two scalings applies inside the cone of consequences of (j +1, j +1): {c, t) : |c-j -1| ≤ t-j -1}, intersection of the two cones issued from a 2 and a 4 . See Fig. 5. It corresponds to the affine transformation with origin (j + 1, j + 1) and matrix M = M g × M d = (α+β)/(2αβ) (α-β)/(2αβ) (α-β)/(2αβ) (α+β)/(2αβ) . Thus the firing points {(1+2k +γ, 1+2j -γ) : k ∈ N, 0 < k < j -γ} being inside the cone of (j + 1, j + 1) are mapped to the points {(1 + j -(j -k -γ)/α + k/β, 1 + j + (j -k -γ)/α + k/β) : k ∈ N, 0 < k < j -γ}. Among these points, some of them match OCA's sites providing k/β and (j -k -γ)/α are integers. Moreover such a point, with (j -k -γ)/α, k/β ∈ N, corresponds to the output of the input subword that begins at (2(j -k -γ)/α, 0) and ends at (2j + 2 + 2k/β, 0), i.e., the subword a n 1 a 2 a j 3 a 4 a m 5 with n = (j -k -γ)/α, m = k/β. To conclude just note that αn + βm + γ = j. Proposition 2. For any homomorphism h on A such that neither link(h(a 1 ), h(a 2 ), h(a 3 )) nor link(h(a 3 ), h(a 4 ), h(a 5 )) holds, h(L α,β,γ ) is a real time OCA language.

  for some underlying Dyck word z 1 z 2 • • • z 2k and words x i , y i . Example 1. {ab n1 a(ba) n2+1 a n2+1 (ba) n1+n3+2 b n3 : n 1 , n 2 , n 3 ≥ 0} is a 3-Dyck loop for the underlying Dyck word [[]][] and words y 0 = a, x 1 = b, y 1 = aba, x 2 = ba, y 2 = a, x 3 = a, y 3 = ε, x 4 = ba, y 4 = bab, x 5 = ab, y 5 = a, x 6 = b, y 6 = ε. Example 2. {a n1 b n1+n2 a n2 : n 1 , n 2 ≥ 0} is a 2-Dyck loop for the underlying Dyck word [][] and words x 1 = x 4 = a, x 2 = x 3 = b, y 0 = y 1 = y 2 = y 4 = ε.

1 Fig. 1 .

 11 Fig. 1. Time-space diagram of a real time OCA

5 a j-k 1 Fig. 3 .

 513 Fig. 3. Čulík's OCA

3 Fig. 4 .

 34 Fig. 4. Two scalings

1 Fig. 5 .

 15 Fig. 5. Composition of two scalings

As an introduction, we may observe that 1-Dyck loops are real time OCA languages. Indeed a 1-Dyck loop corresponds to a set D = {y 0 x n 1 y 1 x n 2 y 2 : n ∈ N} for some words y 0 , x 1 , y 1 , x 2 , y 2 . It is a linear CFL and so it is a real time OCA language. As a consequence, all constant-slender languages are real time OCA languages.

Let us now consider 2-Dyck loops. According to whether the underlying Dyck word is [[]] or [][], they are of shape {y 0 x n1 1 y 1 x n2 2 y 2 x n2 3 y 3 x n1 4 y 4 : n 1 , n 2 ≥ 0} or {y 0 x n1 1 y 1 x n1 2 y 2 x n2 3 y 3 x n2 4 y 4 : n 1 , n 2 ≥ 0} A first simplification is to assume that the two ends y 0 and y 4 are empty knowing that if L is a real time OCA language then so is {y 0 }L{y 4 } whatever the words y 0 and y 4 are. We will suppose also that the words x i are non-empty, the degenerate cases being easy to handle.

The underlying Dyck word is [[]].

That is the simple case. The corresponding Dyck loop {x n1 1 y 1 x n2 2 y 2 x n2 3 y 3 x n1 4 : n 1 , n 2 ≥ 0} is clearly a linear CFL and so it is real time OCA recognizable. Here it is basically the closure under the operation which is involved.

The underlying Dyck word is [][].

Now it is the closure under concatenation of 1-Dyck loops which is involved.

Case 1. link(x i , y i , x i+1 ) holds for no i = 1, 2, 3

Let N 0 be a constant as defined in Lemma 1. The Dyck loop can be divided into three subsets D 1 , D 2 and D 3 , where

: n ∈ N} is a finite union of linear CFL's and thus is alinear CFL. The subset D 2 is as well a linear CFL. Further, Lemma 1 ensures that D 3 can be specified as the intersection of two linear CFL's :

The case where y 1 links x 1 with x 2 (or in a symmetric way y 3 links x 3 with x 4 ) does not present any difficulty. By Definition 2, y 1 links x 1 with x 2 if ρ(x 1 ) = pq, ρ(x 2 ) = qp and y 1 = (pq) γ p for some words p, q and integer γ.

1 y 1 x n2 2 y 2 can be rewritten as (pq) (α+β)n1+γ py 2 and thus specifies a regular language. Moreover x n3 3 y 3 x n4 4 = x n3 3 y 3 x n3 4 corresponds to a linear CFL. Their concatenation is linear CFL and so real time recognizable by an OCA.

Proof. One has to be careful because real time OCA is not closed under morphism: each recursively enumerable language can be written as the image of a real time OCA language by a morphism [START_REF] Čulík | Systolic trellis automata: Stability, decidability and complexity[END_REF]. But here we play with the image of languages with very simple structure.

First observe that h({a n 1 a 2 a αn+βm+γ 3 a 4 a m 5 : n < N 0 or m < N 0 }) is a linear CFL, so to show that h({a n 1 a 2 a αn+βm+γ 3 a 4 a m 5 : n, m ≥ N 0 }) is a real time OCA language will suffice. According to Proposition 1, there exists a real time OCA (Q, A, Q accept , δ) which recognizes the language L = {a n 1 a 2 a αn+βm+γ 3 a 4 a m 5 : n, m ≥ N 0 }. Following Okhotin [START_REF] Okhotin | On the equivalence of linear conjunctive grammars and trellis automata[END_REF], L is defined by the linear conjunctive grammar G = (A, {S} ∪ {A q : q ∈ Q}, S, R) where R contains the following rules:

Now let us make explicit, in the grammar rules, the bounded feature of the language. All words are of shape a + 1 a 2 a + 3 a 4 a + 5 . We denote by Follow(i) the set of j such that a j follows immediately a i in the expression a + 1 a 2 a + 3 a 4 a + 5 : r,j) for all g, d ∈ Q and all i, j, r, s with 1 ≤ i ≤ r ≤ s ≤ j ≤ 5, r ∈ Follow(i), j ∈ Follow(s)

To gain a better understanding of the last derivation rule, see Fig. 6, it depicts the corresponding OCA transition. With such refinements, we get that L G (A q , i, j) is the subset of L G (A q ) whose words begin with a i , ends with a j and which are factors of a + 1 a 2 a + 3 a 4 a + 5 .

In addition, to meet later requirements, we replace all rules (A ai , i, i) → a i with the rules (A δ(ai

1 a 2 a N0 3 a 4 a N0 5 . It does not alter the expressiveness of the grammar.

Finally, in replacing each symbol a i with its image h(a i ), G is rewritten to H = (Σ, {S} ∪ {(A q , i, j) : q ∈ Q, 1 ≤ i ≤ j ≤ 5}, S, R ) where R contains the following rules:

) for all g, d ∈ Q and all i, j, r, s with 1 ≤ i ≤ r ≤ s ≤ j ≤ 5, r ∈ Follow(i), j ∈ Follow(s)

Clearly, h(L G (S)) ⊆ L H (S). Let us ensure that they are equal and, more specifically, that L H (A, i, j) ⊆ h(L G (A, i, j)) for every variable (A, i, j). The proof is done by induction on the height of the parse trees. The inductive assumption is that all words generated within H by a tree of height h and root node (A, i, j) are images by h of words generated within G by a tree of height h and root node (A, i, j).

The base case. The trees of height 1 within H display the derivations

The inductive step. We focus on the trees with root node (A q , 1, 5) and omit the ones with root (A q , i, j) when i > 1 or j < 5 that are easier to handle. Given any tree T within H of height h + 1 > 1 and root (A q , 1, 5). The root node expands into two subtrees of height at most h according to some rule (A q , 1, 5) → (A g , 1, s)h(a 5 ) & h(a 1 )(A d , r, 5) where δ(g, d) = q, s is 4 or 5 and r is 1 or 2. By assumption, (A g , 1, s) produces the image by h of a word a n1 1 a 2 a n2 3 a 4 a n3