Nicolas Bacquey
email: nicolas.bacquey@unicaen.fr

Leader election on two-dimensional periodic cellular automata

Keywords: cellular automata, leader election, bi-periodical configuration, equivalence classes, uniform computation

This article explores the computational power of bi-dimensional cellular automata acting on periodical configurations. It extends in some sense the results of a similar paper dedicated to the one-dimensional case. More precisely, we present an algorithm that computes a "minimal pattern network", i.e. a minimal pattern and the two translation vectors it can use to tile the entire configuration. This problem is equivalent to the computation of a leader, which is one equivalence class of the cells of the periodical configuration.

Introduction

Cellular automata are a well-studied computational model. Its uniform and local properties capture a large range of natural problems, and the model is simple enough to allow definitions of algorithms, or complexity classes. However, the infinite nature of its underlying structure may raise some issues when confronted with finite objects. There are two naive ways of solving these issues: either working on a finite subset of the automaton, or requiring the whole infinite configuration to be periodical.

Periodical configuration is quite a natural concept in the context of tiling problems. As a significant example, it was first (erroneously) conjectured by Hao Wang in [START_REF] Hao | Proving theorems by pattern recognition I[END_REF] that each finite set of tiles that tiles the plane can always do it by some periodical configuration. Periodical configurations have also been extensively studied on cellular automata, when those are considered as dynamical systems: typically, questions of undecidability of the injectivity or reversibility of the transition function have been studied [START_REF] Kari | Theory of cellular automata: A survey[END_REF]. On the other hand, periodical configurations are much less studied from the point of view of computation, with some notable exceptions, such as the density classification problem [START_REF] Mark | No two-state CA for density classification exists[END_REF].

A natural problem would be to compute a "minimal period" of a periodical configuration. However, performing computations on periodical configurations is somehow counterintuitive, because one cannot easily define essential notions, such as the origin and termination of the computation, or the time complexity of an algorithm. These difficulties are mainly due to the fact that unlike what happens on classical models such as Turing machines, you cannot choose a single cell to start the computation or bear its result. This difficulty is overridden when the input of a cellular automaton is bounded by persistent symbols, because then you can identify cells that are on the border of the computation area, and use them as starting or stopping points. However, one cannot use such tricks when the configuration is periodical; in that case, all notions related to computation should be global.

This paper presents an extension of a previous work [START_REF] Bacquey | Complexity classes on spatially periodic cellular automata[END_REF] dedicated to the simpler one-dimensional case. In [START_REF] Bacquey | Complexity classes on spatially periodic cellular automata[END_REF] we exhibited a one-dimensional cellular automaton that computes in polynomial time a minimal period of an infinite one-dimensional periodic configuration. We now want to deal with bi-periodical configurations of dimension 2, i.e. configurations that have two independent vectors of periodicity. A natural starting point would be to compute the minimal pattern of a given configuration, i.e. the smallest pattern with which we are able to rebuild the whole configuration by translation along the two orthogonal axis. This problem is unsolvable in the case of cellular automata of dimension ≥ 2, as it is briefly suggested on Fig 1 . Instead, we will solve the problem of exhibiting a minimal pattern network, i.e. a minimal pattern and the two translation vectors it can use to tile the entire configuration. We can see that this minimal pattern network can be computed through the election of a leading equivalence class of cells. This leader election will be the main subject of this article. While leader election on two dimensional cellular automata has already been extensively studied [START_REF] Nichitiu | Algorithms for leader election by cellular automata[END_REF], all the algorithms that already exist cannot be applied to our model, because they heavily rely on the existence of computational borders, that frame the finite computational area. Due to the periodical nature of the configurations we study, such borders cannot exist in our framework. In that sense, this article presents a new algorithm that performs leader election on a broader class of configurations.

After having clearly defined the problem of leader election on periodical cellular automata, we will present some algorithmic tools that fit our needs. Finally, we will present an algorithm that performs leader election in polynomial time.

Context and basic definitions

1.1. The computational model

We will use along this article the standard definition of cellular automata (CA) as a tuple A = (d, Q, V, δ) (see [START_REF] Kari | Basic concepts of cellular automata[END_REF]). In these lines, we will work with d = 2, i.e. with cellular automata whose underlying network is Z 2 . Q denotes the set of states, and V is the standard Moore neighbourhood1 . The local transition function of the automaton is denoted by δ : Q V → Q. As we work with cellular automata from the point of view of language recognition, we will identify a particular subset Σ ⊆ Q as the input alphabet. A configuration is an application C : Z 2 → Q. We also introduce the global transition function

F δ : Q Z 2 → Q Z 2
defined by the global synchronous application of δ over configurations of Z 2 .

We suppose that the reader is familiar with the notions of signals and computation layers on cellular automata. If it is not the case, we strongly encourage the reading of [START_REF] Kari | Basic concepts of cellular automata[END_REF] or [START_REF] Mazoyer | Computations on one-dimensional cellular automata[END_REF] for such general matters on cellular automata.

Definition 1. We define a Toric-Cellular Automaton (toric-CA) as a cellular automaton whose initial configuration (and therefore any subsequent configuration) is bi-periodic ( i.e. periodic in two independent directions).

Note that this model is equivalent to an automaton that would work on a finite, torus-like cell network. Definition 2. Let w be a rectangular word over Σ, we denote C w ∈ Q Z the configuration formed by the uniform repetition of w over Z 2 . Definition 3. We call a cell an element of the underlying network Z 2 and the state of Q associated with it.

Note that the state of a given cell may change through time.

Leader election on toric-CA

We now consider our bi-periodic configurations, and will try to perform leader election upon them. We will see that it is not possible to elect a single cell on the configuration, and will introduce the definition of equivalence classes to deal with that issue.

Equivalence classes of cells

Let C be a bi-dimensional, bi-periodic configuration over Q. Definition 4. We say that two cells c 1 and c 2 of C are equivalent if the translation that moves c 1 on c 2 leaves the configuration unchanged.

It is immediate to see that the previous definition induces an equivalence relation. Let us now consider the equivalence classes of that relation. As all the cells of an equivalence class have the same state and the same neighbourhood, the application of the transition function on these cells will give the same resulting state. By recurrence, it appears that at any given time during the computation, each cell of an equivalence class will be in the same state. From a computational point of view, the cells of a given equivalence class are indistinguishable from each other (See Fig 2).

Because the configuration C we are considering is bi-periodic, it also appears that each cell belongs to an infinitely large equivalence class, and that there only exists a finite number of equivalence classes.

Definition 5. We define the size of a bi-periodic configuration as the number of its equivalence classes. The size of the initial configuration will be denoted as N .

It is clear that N is the only pertinent parameter when one wants to discuss time complexity of algorithms running on toric-CA.

Proper definition of leader election

As a corollary of previous statements, it appears that it is impossible to elect a single cell of the configuration as a leader (or any finite subset of cells for that matter).

The leader election problem on bi-periodic configurations actually sums up to the election of a single equivalence class.

Main result

In the following sections, we will describe an algorithm that performs leader election on toric-CA. More precisely, the algorithm will process bi-periodic configurations such that after a certain time:

• The states of all the cells of the elected equivalence class will be in a certain final subset of states F ∈ Q and will never leave it.

• The states of every other cell will never be in F any more.

Theorem 1. The algorithm presented in this paper solves the leader election problem in a time polynomial in the size N of the initial configuration.

At the beginning, all cells will be candidates to this election, then our algorithm will perform a percolation amongst those cells, only sparing those which belong to a single equivalence class. Note that due to the nature of our computational model, it is impossible for a single cell to assert that the election is over and no more cells are to be percolated. This can only be done by an observer outside of the model.

Basic objects and tools

We will consider patches as the basic objects in this article. A patch denotes a finite set of neighbouring cells, upon which computation will be performed. We precisely intend to subdivide the whole configuration into patches, and we want the behaviour of a patch to depend only on its content and the content of its neighbours. Later in the article, we will introduce signals that will travel along the borders of the patches. We want a single signal to be able to travel through the entire border of a patch, which forbids patches to have holes. However, we present in the next section a method to process patches that may have holes.

Patches, borders and contents

In order to properly define what a patch of cells is, we have to subdivide the cell network. More precisely, each cell of the network will be divided into four sub-cells (See Fig 3). Please note that this rather unusual definition is due to the dynamics of the main algorithm. It is convenient to first define a patch as a simple closed curve, and then as a set of cells. Definition 6 (patch as a curve). We define a patch as a finite, simple, closed curve in the subdivided cell network that obeys some restrictions, which will be detailed thereafter.

The restrictions focus on the angles of the curve, and consist of a set of allowed and forbidden angles, such as shown on Fig 4. They can be informally summarized as follows :

• Each outer angle (i.e. 90 • angle when measured from the inside) must externally correspond to a full line corner.

• Each inner angle (i.e. 270 • angle when measured from the inside) must internally correspond to a dashed line corner. Definition 7 (border). The border of a patch is canonically defined as the projection of its curve over the corresponding outer cell edges of the original network.

Definition 8 (patch as a set of cells). We define the content of a patch as the set of cells within its border, or indifferently the initial state of those cells.

As an abuse of notation, we may use the term patch to denote its content.

Examples of patches with their contents and borders are shown on Proper patches. We can see that some parts of the border of a patch might be useless (see Fig 7). The following definition will give us a canonical representative for those patches.

Definition 9 (Proper patch). We say that a patch is a proper patch if the curve defining it does not contain the pattern presented in Fig 7a . The proper patch associated to a given raw patch is the patch where all the occurrences of the forbidden pattern have been locally deleted (see Fig 7). Note that this operation does not change the content of a patch.

We would like to be able to distinguish a particular cell in a patch; this is the goal of the next definition.

Definition 10 (Patch leading cell). We define the leading cell of a patch as the uppermost cell amongst its leftmost.

Note that this notion is a priori unrelated with the leader election problem we exposed earlier.

Patch word

We are going to design an algorithm able to compare patches. Because a patch is a rather complex object, we have to find a canonical representation that our computational model can handle. A patch will be represented by a word encoding both the shape of its border and its content.

Definition 11 (Border word). We define the border word associated to a patch as the word over the alphabet Γ = {↑, ↓, ←, →} that represents its border in clockwise order, starting from the upper left angle of the patch leader.

For instance, the border word of Fig 8 is →→→↓↓↓→↓←←←←↑→↑←↑↑

Now we must extend our concept of border word to take the content of the patch into account. A trivial solution that first comes to mind is to enumerate the content of all the cells in reading order, starting from the patch leader. However, this solution raises some issues due to the fact that it is hardly locally computable. We propose instead the construction of a spanning tree over the cells of a patch, whose root is the leading cell. We admit for the moment, for the sake of simplicity, that we can easily construct such a spanning tree on a proper patch with local rules, once the leading cell is identified (the proof of this point will be given in section 5.4.3). The spanning trees associated to different shapes of patches can be seen on Fig 9.

Definition 12 (patch word). Let Σ be the input alphabet of our automaton, we define the patch word associated to a proper patch as the word w c = w Γ w Σ , where w Γ ∈ Γ * is the border word of the patch, and w Σ ∈ Σ * is the content of the cells of the patch, ordered by the prefix order depth-first search of the spanning tree associated to the patch (for a fixed order of the directions).

w c =→→→↓↓↓→↓←←←←↑→↑←↑↑ 011010011010
We note that there is a one-to-one correspondence between proper patches and their patch word, assuming the algorithm used to construct the spanning tree is deterministic and only depends on the shape of the patch. We will outline a deterministic algorithm in section 5.4.3.

Local neighbourhoods

We introduce the partition of the border of a proper patch into local neighbourhoods as follows: Definition 13. A local neighbourhood is a maximum, connected component of the border for which the neighbouring patch does not change. We then canonically define the local neighbour associated with this neighbourhood as the adjacent patch.

As we want the entire configuration to be partitioned into patches, the assumption that each patch must have neighbouring patches is satisfied during the algorithm.

We can also see on Fig 10 that the number of local neighbours of a patch can be greater than the number of its distinct adjacent patches. We also note that a proper patch can be its own local neighbour.

Overview of the leader election algorithm

All along the algorithm, the configuration will be entirely partitioned into patches, as defined previously. Instead of talking about the behaviour of cells, and for a better preliminary comprehension of the algorithm, we will talk about meta-states of patches, and how those meta-states must evolve according to a meta-algorithm. At the beginning of the algorithm, the configuration will be entirely decomposed into patches of size 1, i.e. each cell will be alone in its own patch. The final goal of the algorithm is to merge patches together, until the configuration is only composed of the periodical repetition of the same big patch. Fig 11 presents the evolution of a configuration from the starting point to the final state.

Meta-states and meta-algorithm

Each proper patch will have a meta-state for each of its local neighbourhoods (we will call them merging states), plus one special state (the waiting state). Merging states can be interpreted as if the patch was trying to merge with the local neighbour associated with the state, while the waiting state means that the patch is performing some lower level computation.

The behaviour of a proper patch will follow those rules:

• At the beginning of its existence, a patch will be in the waiting state for a finite time.

• After this time is over, the state will cycle over the merging states until the patch merges.

The essential point is that each pair of adjacent patches simultaneously in a merging state that corresponds to the same local neighbourhood must merge with each other (see Fig 12). The actual merging process will be detailed later.

Reformulating the main result

We will now explain the link between patches and leader election. It is clear that a single patch cannot contain two representatives of the same equivalence class, because two cells of the same equivalence class cannot have different behaviours during the computation. It follows that the maximum size of a patch (i.e. the maximum number of cells it contains) is the number N of equivalence classes. Moreover, if a patch of size N is eventually constructed by the algorithm, then the configuration is entirely tiled by translations of it. We can then elect a single equivalence class by simply selecting all the patch leading cells of the configuration (those cells obviously belong to the same equivalence class).

In order to stick with the formalism used in theorem 1, we say that a cell is in the final subset F ∈ Q if it currently is a patch leading cell.

The goal of the algorithm is therefore to perform merging between patches as long as there exist two adjacent patches that are different. Indeed, if there exists two different adjacent patches on the configuration, then they are not of maximum size.

Keeping this in mind, proving the following lemma is sufficient to prove the main result: Lemma 1. If at a certain time there exists two adjacent patches whose patch words are different, then at least one of them must merge within polynomial delay.

Detailed algorithm

Cell division

As we stated before, we will subdivide each cell of the configuration into four sub-cells that will hold actual computation. We will talk about the divided configuration when it is necessary to consider all four sub-cells separately, and united configuration when it is not. The set of states Q of the automaton is therefore the product Σ × Q 4 s , where Σ is the input alphabet and Q s is the states set of sub-cells. As we want to retain the input information at all time, the projection of Q over Σ will never change.

If we associate each sub-cell to a corner of the original cell, we obtain the informal division we used to define patches.

Detailed implementation of the meta-algorithm

In order to simulate the merging meta-states, each patch will construct and maintain a signal that will travel along its border. More precisely, this signal will cycle along each edge of the border, sometimes waiting longer than one time step on each edge. From an intuitive point of view, the signal will travel on the intersecting points between the closed curve we used to define a patch and the subdividing lines in the cells (see Fig 13). As there exist at most four of those points in a single cell, we can match each of them to a single sub-cell.

Moreover, each of those points can also be associated to a single neighbouring cell, and therefore to a single local neighbourhood of the patch. Keeping this in mind, we now claim that a patch is in the merging state corresponding to the local neighbourhood associated to the point where its signal currently stands.

We note that, as we use Moore neighbourhood on the united configuration, the signal can travel from an intersection point to the next one in one time step. This signal will encode the shape and content of its patch into waiting delays along the border (this encoding will be detailed in section 5.4.4). It will behave so that the signal of two different patches will eventually de-synchronize and meet each other, thus leading to a merging.

First step

At the first time step, the automaton will construct patches of size 1 all over the configuration. The result of this operation, which can be performed locally, can be seen on Fig 14 . Note that patches retain their input information at any time.

Ongoing behaviour

In this section, we will consider the life cycle of a patch, from its birth to its death. We make the assumption that the border of this patch is synchronized, as done by a firing-squad-like algorithm (See [START_REF] Balzer | An 8-state minimal time solution to the firing squad synchronization problem[END_REF] or [START_REF] Umeo | Firing squad synchronization problem in cellular automata[END_REF]). This assumption is satisfied at the beginning of the computation, because this beginning in itself trivially is a synchronizing event. We will see later how a patch can synchronize itself when it is newly created. We do not make the assumption that the patch is a proper patch at the beginning of its existence.

The existence of a patch can be summarized as follows:

• The patch selects its leading cell (5.4.1),

• The raw patch is transformed into a proper patch by local modifications (5.4.2),

• The spanning tree is constructed (5.4.3),

• A signal is launched around the border of the patch (5.4.4).

• When two signals encounter each other, both patches are merged and synchronize their borders (5.4.5).

Patch leader selection

Let us consider a newly created patch, that is assumed to be synchronized. The first thing we want to do is to select the patch leading cell, as defined previously. Let us also consider the set of sub-cells defining the border of the patch. Those cells can be identified locally and form a ring-like structure. If we select the leftmost amongst the uppermost of those sub-cells, it can be trivially matched to the patch leading cell (see Fig 15).

It happens that the election of a particular cell on a ring-like structure on cellular automata is a well studied problem, and that [START_REF] Nichitiu | Algorithms for leader election by cellular automata[END_REF] provides an algorithm that exactly fits our needs. We assumed that the border of the patch is synchronized, so all we have to do is to run the algorithm presented in [START_REF] Nichitiu | Algorithms for leader election by cellular automata[END_REF] on the sub-automaton (i.e. the automaton whose cells match our sub-cells), then select as a patch leading cell the one whose upper left sub-cell has been selected by the algorithm. We note that this algorithm runs in polynomial time.

Healing the patch

We now want to turn our raw patch into a proper patch. This will be done by deleting all occurrences of the local pattern forbidden into a proper patch (see Fig 7a). From a practical point of view, a signal will be sent from the leading cell and travel along the border. This signal will replace local patterns according to the local rule presented in Fig 16 . It is immediate to see that the iterative application of this local rule will turn the patch into its associated proper patch (see Fig 7).

Building and browsing the spanning tree

Now that the patch is proper and the leading cell is identified, we can build the spanning tree starting from the leading cell with a very simple set of rules: If a cell has a neighbour in the patch in which the tree is constructed, an edge will be created between this cell and its neighbour at the next time step. If a cell has more than one neighbour fulfilling the conditions, it chooses one according to a predefined order among the direction (e.g. up > left > down > right). Fig 17 shows the ongoing construction of a spanning tree over an example patch. For practical reasons, this tree is oriented toward the root. We now want to browse the tree and provide the leading cell with the next symbol of the tree on demand. This can be trivially done by simulating a finite state 2D-automaton performing a depth-first search on the tree and providing a symbol to the root each time it discovers a new cell. Note that this technique can guarantee a time interval between the reception of two symbols that is linear in the size of the tree. Specifically, the retrieval time is upper bounded by n 2 , where n is the length of the border of the patch.

Detailed signal behaviour

As soon as the patch is healed, the leading cell will send the signal that will trigger fusion between patches. The behaviour of this signal will be detailed in this section. Definition 14. We define the length of the border of a patch as its number of waiting points, as defined previously.

The length of the border of the patch we consider all along this section will be denoted as n. Let us now consider the one-dimensional circular cellular automaton composed by the waiting points of a patch. We will call this particular automaton the border automaton of the patch. Clearly this border automaton can be simulated step-by-step by our real two-dimensional cellular automaton.

Definition 15. We define the leading waiting point of the border automaton as the upper waiting point of the leading cell of its patch.

Once the patch is healed, the leading waiting point will send a merging signal along the border automaton. This signal will cycle around the border automaton at maximum speed, and will sometimes carry a pebble, which we will call the waiting pebble (See Fig 18). At the beginning, the waiting pebble is positioned on the leading waiting point, which stores the symbol a 0 . The signal then obeys the following rules, which are explained on Fig 18: • Cycle around the border automaton at speed 1 until the waiting pebble is encountered (see Fig 18a).

• When the waiting pebble is encountered, move it to the next waiting point and wait for a certain waiting time τ n on that point (see Fig 18b).

• If the signal has just waited on the leading waiting point, the signal will perform some extra cycles around the border automaton. The exact number of those cycles depends on a i . The leading cell will then retrieve the next symbol a i+1 (or a 0 if a i was the last symbol of the word), and the signal will resume normal behaviour (see Fig 18c). Definition 17 (extra cycles). The number of times the signal must cycle over the border automaton is given by val(a i ), where val is any bijection from Σ ∪ Γ into 0; k -1 .

Those extra cycles will only happen when the pebble is dropped on the patch leading cell, thus inducing a time shift of n.val(a i ) in the behaviour of the signal.

Note that the time τ n is constructible2 whatever the value of n is. For more general matter on time constructibility, please refer to [START_REF] Mazoyer | Signals in one-dimensional cellular automata[END_REF].

This behaviour forces the leading cell to store the active symbol of the patch word. This can be done by browsing the border of the patch and its spanning tree, and sending the right symbol back to the leading cell. The cell will store only one symbol at a given time, starting from the first one (always a "→" symbol) and sending a signal when it needs to retrieve the next one. We saw earlier that the time to retrieve a symbol of the patch word is bounded by n 2 . Let us note that this time does not introduce a delay in the algorithm, since the time between which two successive symbols are requested is k.n 3 + O(n 2 ).

In the next sections, we will denote the patch word as a = a 0 a 1 . . . a l , and i will denote the position of the symbol currently held by the leading waiting point.

t 0 t 0 + 1 . . . t 0 + n -1 (a) Cycling phase t 0 + n t 0 + n + 1
. . .

Local fusion and synchronisation

When two merging signals encounter on the common border of two patches, they must merge together, according to the global rule of our meta-algorithm. This can be done locally, following the process depicted on Fig 19: It is sufficient to delete the border portions on which the signals currently are, and "re-wire the border " so that they now form the border of a new, probably non proper patch. We can see that the resulting curve still respects the restrictions for defining a patch. Once this fusion is done, we need to delete both spanning trees, by sending signals that will travel among them and destroy them, and both leading cells of the two former patches. We must now synchronize the whole patch border to get back to the situation of 5.4.1. This can be done by considering the new border as a one-dimensional cyclic cellular automaton of the divided network. We can identify a particular cell of this CA, e.g. a cell in which the merging process occurred. This cell can be used as the general of a firing squad algorithm, whose execution will re-synchronize the whole border, in order to perform a new leading cell election (see 5.4.1) on the merged patch. For general matter on firing squad algorithms, see [START_REF] Mazoyer | A six-state minimal time solution to the firing squad synchronization problem[END_REF]; here we merely note that they perform in linear time.

It may seem a waste to synchronize the whole border to elect a new leading cell, while the leading cell of the merged patch is always one of the two former leading cells. Indeed, it is possible to discriminate between the two cells with a linear time algorithm, but to the extend of our knowledge, such an algorithm has never been extensively studied and published. Detailing an ad hoc efficient method to elect the new leading cell would be out of the scope of this article, which is not focused on the practical implementation of the algorithm.

Notes about Fig 20.

• We have n = 4 for this patch. We suppose that C 3 is the leading waiting point and val(a i ) = 3 for the instant we consider.

• The sum of the unlabelled time spans is n, which corresponds to the n moves of the pebble to the next cell, each one of length 1.

• The border automaton is in the same configuration at the two circled times on the left C 1 line, except that the symbol a i pointed by the automaton has changed to the next one.

"Ending" the computation

Now that we have described our ongoing behaviour, we must talk about the ending of the computation. When all patches are of maximum size, i.e. when their size is N , they cannot grow any larger, because of the very definition of equivalence classes. Indeed, if two such maximal matches would merge, it would mean that two cells of the same equivalence class would have two different "roles" (intuitively, the cell of the patch on the right would be distinguishable from the cell of the patch on the left), which is impossible.

From a practical point of view, the patches will not merge because their patch words will be the same, and their signals will be completely synchronized.

Finally, at the end of the computation the configuration will entirely be decomposed into translations of the same maximal patch, into which a signal will cycle indefinitely. Note that due to the periodical nature of our computation model, we cannot have a particular cell to bear the information of the termination, like it is the case with CA whose input is bounded by persistent symbols.

Justification

In this section, we will prove that our construction satisfies the main result of 4.2, i.e. that if at a certain time there exists two adjacent patches whose patch words are different, then at least one of them must merge in polynomial time.

We will suppose that there exists P 1 and P 2 two patches with different patch words, and we will prove that if neither of them have merged with a third patch (in which case our main property would have been verified), then they must merge together in polynomial time. We will denote n 1 and n 2 as the border sizes and i and j as the symbol position on the patch words of P 1 and P 2 respectively. We study two disjoint cases: whether n 1 = n 2 or n 1 = n 2 .

Different border sizes

We first suppose n 1 = n 2 . We can assume without loss of generality that n 1 < n 2 , namely n 2 ≥ n 1 + 1. Let us now consider an instant when the waiting pebble of P 2 is dropped on a waiting point of the common border with P 1 . The merging signal of P 2 will then wait for a certain time τ n2 on that waiting point. We therefore have: Let us now consider the maximum time during which the merging signal from P 1 can be absent from the corresponding waiting point on P 1 . Clearly this time τ abs is the sum of the waiting time on P 1 , τ n1 and the time for the signal to make a complete revolution around P 1 , which is n 1 -1. We therefore have:

τ n2 = k.n 2 2 τ n2 ≥ k.(n 1 + 1) 2 τ n2 > k.n 1 2 + 2k.n 1 t C1 C4 C3 C2 C1

Cyclic space

τ abs = τ n1 + n 1 -1 τ abs = k.n 2 1 + n 1 -1
We clearly have τ n2 > τ abs , which means that the signal from P 1 will encounter the signal from P 2 before this signal leaves its waiting point. Therefore, a merging will occur between P 1 and P 2 , Q.E.D.

Same border size

Now we consider the case when n 1 = n 2 = n. Let us call S 1 , S 2 , a and b the signals travelling through and the patch words of P 1 and P 2 respectively. Since P 1 and P 2 are different, a and b are also different. We now observe a single waiting point on a common border of P 1 and P 2 .

Let us consider the behaviour of S 1 on this waiting point : it frequently passes through it, and sometimes waits for a time τ n . Let us call (t k ) k≥0 the sequence of instants when S 1 stops on the waiting point and waits during τ n . By construction of the algorithm, there is exactly one instant between every t k and t k+1 when S 1 will wait on the leading waiting point of P 1 , then cycle around the automaton val(a i ) times, for a certain a i .

Because P 1 and P 2 have the same border size n, the behaviour of S 1 and S 2 on the point we consider are the same (because it only depends on n), except when they perform the extra cycles after waiting on the leading waiting point. Therefore, a similar reasoning also holds for S 2 , which will wait on the leading waiting point of P 2 , then cycle an additional val(b j ) times at a single time point between t k and t k+1 . We can therefore associate a couple of symbols (a i k , b j k ) to each t k .

We know that a = b, and by construction a cannot be a shift of b. Therefore there exists a k 0 for which we have a • Let T 0 be the last time S 2 was present on the common waiting point before the time t k0 associated to k 0 .

• Let δ be t k0 -T 0

We note that there are two types of "holes" during which a signal is absent from a particular waiting point: holes of size n and holes of size τ n +n. We know that S 1 is present on the common waiting point for a duration of τ n , starting at time T 0 + δ. If we suppose that it does not encounter S 2 during that time 3 , it means that this presence corresponds to a hole of size τ n + n on S 2 , as we clearly have τ n > n. We therefore know that S 2 will be present on the waiting point at time T 0 + τ n + n.

We note that the pebble performs a complete revolution around the automaton in time n.(τ n + n + 1) + n.val(a i ) on P 1 , and n.(τ n + n + 1) + n.val(b j ) on changes the symbol pointed on its patch word every time the pebble does a complete rotation on the border, which is every O(N 3 ). As the patch word is of size O(N ), we are assured that two adjacent and different patches must merge before time O(N 4 ). We note that the cost of the operations needed to merge patches properly is way less than O(N 4 ).

Finally, as there exist N distinguishable patches at the beginning of the computation, and at least two of them must merge every O(N 4 ), we are assured that the leading equivalence class is elected in time O(N 5 ), which proves that our algorithm is polynomial in N .

Note that this analysis is extremely rough, as it does not take into account the parallel nature of the algorithm, and only consider two patches at a given time. We think that a more refined analysis would at least allow us to gain a N or N 2 factor, but it seems unnecessary regarding the primary goals of this paper.

Final remarks about the algorithm

An attentive reader would have noticed that we do not, in fact, end our computation, just have it cycle over a finite set of configurations. Informally speaking, it is a weak way to end a computation. We would rather want it to reach a fixed point, instead of a fixed cycle. We are convinced that a few tweaks to the algorithm can make it reach such a fixed point. The intuition is that if a patch has waited for a sufficient time without merging with another, it can determine that all of its neighbours are the same as itself, and can freeze its computations.

After the computation freezes, the cellular automaton can start any other algorithm using the patches. It may cancel this new computation and resume the patch merging algorithm later, if one of its neighbours merges (that would mean that it was not the "true end" of the computation). If all the patches have determined that their neighbours are the same as themselves and have frozen their computations, then the fixed point is reached. At the opposite, if it where applied to a non-periodical configuration, our algorithm would never reach such a fixed point.

Moreover, when the computation "ends", we know that all the patches are identical. We do not know, however, if their position respectively to each other is the same. To ensure that fact, it only suffices to enrich the border word, by adding a special symbol that marks the point where the border of another patch has been encountered.

Conclusion and open problems

About tiling

It is important to note that our algorithm does not only compute a leading equivalence class, but also a polyomino that tiles the entire configuration by translation (this polyomino is the final patch). We know, thanks to [START_REF] Beauquier | On translating one polyomino to tile the plane[END_REF], that the shape of this polyomino should be a pseudo-hexagon. In fact we can tweak our tiling patches to be rectangles (See

Figure 1 :

 1 Figure 1: One cannot extract the 2 × 2 square pattern from the configuration, because all cells marked with 1 are indistinguishable from each other. Nevertheless, it is possible to extract the 2 × 1 pattern, with its two tiling vectors.

Figure 2 :

 2 Figure 2: All darkened cells will have the same behaviour during the computation, as they belong to the same equivalence class.

Fig 5

 5 Fig 5 gives examples of simple curves of the subdivided network. We can note that the only curves which properly define a patch are those on Fig 5a and Fig 5b, while Fig 5c presents angles that are forbidden.

Fig 6 .

 6 Note that this definition allows patches whose content may contain holes, but whose border can be travelled through by a single signal (see Fig6b).

Figure 3 :

 3 Figure 3: Dividing the cell network

Figure 4 :

 4 Figure 4: Local recognition of acceptable curves (the coloured area denotes the inside of the curve)

Figure 5 :Figure 6 :Figure 7 :

 567 Figure 5: Examples of simple closed curves that may define patches

  For instance, here follows the patch word of the patch of Fig 8, whose spanning tree is the one on Fig 9a :

Figure 8 :

 8 Figure 8: A proper patch and its content, with its leading cell highlighted

Figure 9 :

 9 Figure 9: Example of spanning trees associated to proper patches, with their root highlighted

Figure 10 :

 10 Figure 10: This patch has 4 adjacent patches, but 8 local neighbourhoods.

Figure 11 :

 11 Figure 11: A possible evolution of a periodic configuration over time. Dark corners represent patch leaders.

Figure 12 :

 12 Figure 12: Two patches merging along a common local neighbourhood

Figure 13 :

 13 Figure 13: Highlighting of the waiting points of a patch

Figure 14 :

 14 Figure 14: Patches of the initial configuration. Red lines are omitted for the sake of clarity.

Figure 15 :

 15 Figure 15: Highlighting the ring-like structure of the border

Figure 16 :

 16 Figure 16: Local transformation turning a raw patch into a proper patch. Blue area denotes the inside of the patch.

Figure 17 :

 17 Figure 17: The construction of a spanning tree

Fig

  Fig 20 sums up the behaviour of the signal and the pebble on a sample border automaton with n = 4. At any point during the existence of this signal, if it encounters a merging signal from another patch (see Fig 19a), then both signals are destroyed and a merging occurs. This merging process will be detailed in the next section.Definition 16 (waiting times). We define the waiting time as τ n = k.n 2 where: k = Σ ∪ Γ = Σ + 4 is the number of different symbols in a patch word; n is the length of the border, as defined previously.

t 0 +

 0 Figure 18: Overview of the behaviour of the signal in an example patch. The circle represents the waiting pebble, while the square represents the signal.

Figure 19 :

 19 Figure 19: Local fusion when two signals face each other

Figure 20 :

 20 Figure 20: Evolution of the position of the signal (thin) and the pebble (thick) through time.

  i k 0 = b j k 0 . Let us introduce a few particular times, shown on Fig 21: Definition 18.

  Fig 22). This is done by starting with only the patch leading cells (Fig 22b), extending each rectangle to the right until another leading cell is encountered (Fig 22c), then extending it down until its bottom line reaches another leading cell (Fig 22d). It is easy to verify that each

V = {(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 0), (0, 1), (1, -1), (1, 0), (1, 1)}

There exists a computation on a 1-dimensional CA which marks a distinguished cell every τ i , i.e. we can "count" up to τn.

If it does encounter S 2 , then P 1 and P 2 will merge and the proof is over.

• T 1 = T 0 + δ + n.(τ n + n) + n.val(a i ) + n is the next time S 1 will wait during τ n on the waiting point. Note that by our previous formalism, we also have T 1 = t k0+1 .

• T 2 = T 0 + n.(τ n + n) + n.val(b j ) + n is a time at which we are assured that S 2 will be back on the waiting point, due to the quasi-periodic behaviour of the signal (see Fig 20). We also know that S 2 will be there on time

• δ = T 1 -T 2 is the difference between those two times.

We will now prove that if S 1 and S 2 have not encountered before, then they will do so at time T 2 or T 2 + τ n + n.

We clearly have 0 < δ < τ n + n by definition. Moreover, we must have δ < n; otherwise it means that S 2 would come back while S 1 is still here, which would happen at T 0 + τ n + n. We finally have 0 < δ < n. It is also clear that

because a i = b j . We will now discuss two sub-cases: whether ∆ < 0 or ∆ > 0.

Case 1: ∆ < 0. Now we have ∆ ∈ -k + 1, -1 and 0 < δ < n. Therefore:

These values for δ ensure that both signals encounter at time T 2 .

Case 2: ∆ > 0.

Now he have ∆ ∈ 1, k -1 and 0 < δ < n. Therefore:

These values for δ ensure that both signals encounter at time

Temporal analysis

Now let us do a rough time analysis of the algorithm. We remember that N is the number of equivalence classes of the initial configuration, which is an upper bound to the size of any patch during the computation. As the length of the border of a patch is at worst linear in its size, we therefore have n ∈ O(N ) for any patch.

The key point of the previous section was to prove that if two different patches are adjacent, then at least one of them must merge before a certain time. We know that this merging must occur before the patches have cycled over their respective border words. We remember that the border automaton rectangle exactly contains one representative of each equivalence class. This is a first step to a definition of a minimal pattern of periodical configurations of dimension 2. Figure 22: From the final patches to a rectangular tiling of the configuration.

Toward picture language recognition

We have established that our algorithm, completed with the modifications of 6.1, can compute rectangular patches, whose size is the number of equivalence classes of the configuration. We can wonder if an extension of it could actually solve decision problems over these rectangular pictures, i.e. perform recognition of bi-dimensional languages (see [START_REF] Giammarresi | Recognizable picture languages[END_REF]). We have studied the problem, and have concluded that it would indeed be possible, as it was the case in one-dimensional periodic configurations (see [START_REF] Bacquey | Complexity classes on spatially periodic cellular automata[END_REF]). The results are not presented in this paper because the mere definition of what kind of languages are actually recognizable on a toric-CA should be discussed on its own, due to its intrinsic technicality.

Other uses of the algorithm

Our algorithm can serve other purposes than computing minimal patterns. Indeed, the patches can simulate cellular automata with bounded input, with the border of patches acting as persistent symbols. Keeping this in mind, we can for instance solve a 2D version of the density classification problem [START_REF] Mark | No two-state CA for density classification exists[END_REF], i.e. determine if an infinite periodical configuration over the alphabet {0, 1} contains more 0's than 1's, with more than two states: we simply have to count the number of 0's and 1's on a separate information layer inside the patches, then display the result, e.g. on the patch leading cells. A similar modification could also lead the algorithm to count the number of equivalence classes, instead of just electing one (as the number of equivalence classes of the original configuration is exactly the number of cells in the final patch).

Leader election in higher dimensions

We are convinced that the techniques presented in this paper could adapt to higher dimensions, and compute a leading equivalence class on periodical configurations of dimension 3, but such an extension is not trivial. For instance, the problem of a signal running through the border of a "3-dimensional patch" adds a new difficulty, such as the definition of a proper patch in dimension 3. However, even if some geometrical issues arise, the mechanism we used to encode patch differences into delay differences is robust. As it weakly depends on the dimension of the object it considers, it will perfectly adapt to periodical configurations of arbitrary dimensions.