Andrew Adamatzky
email: andrew.adamatzky@uwe.ac.uk

Jérôme Durand

Jérôme Durand-Lose
email: jerome.durand-lose@univ-orleans.fr

Durand -Lose

Collision-based Computing

Keywords: Belousov-Zhabotinsky, Cellular automata, Collision computing, Cycle tag systems, Geometrical computation, Gliders, Localizations, Turing machines

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

Ideas of a collision-based computing 1 are based on studies dealing with collisions of signals, traveling along discrete chains, one-dimensional cellular automata. The interaction of signals traveling along one-dimensional conductors was amongst famous problems in physics, biology and physiology, for centuries, and the problem of interaction was interpreted in terms of finite state machines in 1960s. First ever computer science related results on signal interaction can be attributed to

• Atrubin [START_REF] Atrubin | A one-dimensional real-time iterative multiplier[END_REF], who designed fist ever multiplier based on a one-dimensional cellular automaton in 1965; • Fisher [START_REF] Fischer | Generation of primes by a one-dimensional real-time iterative array[END_REF], who developed cellular automaton generator of prime numbers in 1965; and • Waksman [START_REF] Waksman | An optimum solution to the firing squad synchronization problem[END_REF], who initiated so much popular firing squad synchronization problem and provided an eight-state solution, in 1966.

In 1971 Banks [START_REF] Banks | Information and transmission in cellular automata[END_REF] showed how to build wires and simple gates in configurations of a two-dimensional binary-state cellular automaton. This was not an architecturefree computing because a wire was represented by a particular stationary configuration of cell states (this was rather a simulation of a "conventional" electrical, or logical, circuit). However, the Banks's design made a huge influence on a theory of computing in cellular automata and beyond.

In 1982 Elwyn Berlekamp, John Conway and Richard Gay proved that Game of Life "can imitate computers" [START_REF] Berlekamp | Winning Ways for your Mathematical Plays, volume 2 Games in particular[END_REF].

They mimicked electric wires by lines "along which gliders travel" and demonstrated how to do a logical gate by crashing gliders one to another. Chapter 25 of their "Winning Ways" [START_REF] Berlekamp | Winning Ways for your Mathematical Plays, volume 2 Games in particular[END_REF] demonstrates computing designs that do not simply look fresh twenty years later but are still re-discovered again and again by Game of Life enthusiasts all over the Net.

Berlekamp, Conway and Gay employed a vanishing reaction of gliderstwo crashing gliders annihilate themselves-to build a NOT gate. They adopted Gosper's eater to collect garbage and to destroy glider streams. They used combinations of glider guns and eaters to implement AND and OR gates, and the shifting of a stationary pattern, or block, by a mobile pattern, or glider, when designing auxiliary storage of information.

"There is even the possibility that space-time itself is granular, composed of discrete units, and that the universe, as Edward Fredkin of M.I.T. and others have suggested, is a cellular automaton run by an enormous computer. If so, what we call motion may be only simulated motion. A moving particle in the ultimate microlevel may be essentially the same as one of our gliders, appearing to move on the macro-level, whereas actually there is only an alteration of states of basic space-time cells in obedience to transition rules that have yet to be discovered." -finishes Berlekamp-Conway-Gay's book [START_REF] Berlekamp | Winning Ways for your Mathematical Plays, volume 2 Games in particular[END_REF].

Meantime, in 1978 Edward Fredkin and Tommaso Toffoli submitted a one-year project proposal to DARPA, which got funding, and thus started unfolding a chain of remarkable events.

Originally, Fredkin and Toffoli aimed to "drastically reduce the fraction of" energy "that is dissipated at each computing step" [START_REF] Fredkin | Design principles for achieving high-performance submicron digital technologies[END_REF]. To design a non-dissipative computer they constructed a new type of a digital logic -conservative logic-that conserves both "the physical quantities in which the digital signals are encoded" and "the information present at any moment in a digital system" [START_REF] Fredkin | Design principles for achieving high-performance submicron digital technologies[END_REF].

Fredkin and Toffoli further developed these ideas in the seminal paper "Conservative Logic", published in 1982 [START_REF] Fredkin | Conservative logic[END_REF]. There a concept of ballistic computers emerged. The Fredkin-Toffoli model of conservative computation -the billiard ball model-explores "elastic collisions involving balls and fixed reflectors". Generally, they proved that "given a container with balls we can do any kind of computation".

The billiard ball model became a masterpiece of cellular automaton theory thanks to Norman Margolus who invented a cellular-automaton (block cellular automata or partitioned cellular automata) implementation of the model. Norman published this result in 1984 [START_REF] Margolus | Physics-like models of computation[END_REF]. "Margolus neighbourhood" and "billiard ball model cellular automata" are exploited widely nowadays.

We do not provide a detailed account of collision-based computing. There are no excuses to avoid reading original sources [START_REF] Berlekamp | Winning Ways for your Mathematical Plays, volume 2 Games in particular[END_REF][START_REF] Fredkin | Conservative logic[END_REF][START_REF] Margolus | Physics-like models of computation[END_REF]. A comprehensive, selfcontained and addressed to a wide auditory report of modern state of collision-based computing is provided in the book [START_REF] Adamatzky | Collision based computing[END_REF]. In present chapter we rather discuss our personal experience on designing collision-based computing schemes in one-and twodimensional cellular automata, and spatially extended non-linear media. We also provide few hands-on examples of recently discovered collision-based computing devices, we hope the examples will help readers to experiment with their own designs.

The chapter is structured as follows. Principles of collision-based computing are outlined in Sect. 2. Section 3 shows how basic logical gates can be implemented by colliding localizations in natural systems -simulated reaction-diffusion medium (Subsect. 3.1) and light-sensitive Belousov-Zhabotinsky medium (Subsect. 3.2). Theoretical foundations of computing with signals in 1D cellular automata are presented in Sect. 4, including collision-based implementation of 1D Turing machine (Subsect. 4.2.1) and cyclic tag systems (Subsect. 4.2.2). We complete our excursion to architectureless computing with abstract geometrical computation, Sect. 5, where time and space are continuous and particles/localizations are dimensionless.

Principles of collision based computing

Here we try to summarize all types of collision-based computers. A collision-based computer is an empty space populated with mobile and stationary localizations. The mobile localizations used for computing so far are • billiard balls [START_REF] Fredkin | Conservative logic[END_REF] • gliders in cellular automata models [START_REF] Adamatzky | Computing in spiral rule reaction-diffusion hexagonal cellular automaton[END_REF][START_REF] Berlekamp | Winning Ways for your Mathematical Plays, volume 2 Games in particular[END_REF][START_REF] Delorme | Signals on cellular automata[END_REF][START_REF] Rendell | Turing universality of the game of life[END_REF][START_REF] Rennard | Implementation of logical functions in the game of life[END_REF],

• solitons in non-linear media [START_REF] Anastassiou | Information transfer via cascaded collisions of vector solitons[END_REF][START_REF] Jakubowski | When can solitons compute?[END_REF][START_REF] Jakubowski | Computing with solitons: A review and prospectus[END_REF][START_REF] Rand | Computing with solitons[END_REF][START_REF] Rand | Signal standardization in collision-based soliton computing[END_REF][START_REF] Steiglitz | Time-gated manakov spatial solitons are computationally universal[END_REF], and • localized wave-fragments in excitable chemical media [START_REF] Adamatzky | Collision-based computing in Belousov-Zhabotinsky medium[END_REF][START_REF] Adamatzky | Binary collisions between wavefragments in sub-excitable Belousov-Zhabotinsky medium[END_REF].

Examples of stationary localizations are

• "still lives", blocks and eaters in Conway's Game of Life [START_REF] Berlekamp | Winning Ways for your Mathematical Plays, volume 2 Games in particular[END_REF][START_REF] Rendell | Turing universality of the game of life[END_REF],

• standing waves in automaton models of reaction-diffusion systems [START_REF] Adamatzky | Computing in spiral rule reaction-diffusion hexagonal cellular automaton[END_REF], and • breathers in computing devices based on polymer chains and oscillons in vibrating granular materials [START_REF] Adamatzky | Novel materials for collision-based computing[END_REF].

Usually mobile localizations represent signals and stationary localizations are used to route the signals in the space; however, by allowing balls and mirrors to change their states, in addition to velocity vectors, we can in principle build multivalued logic circuits. From [START_REF] Fredkin | Conservative logic[END_REF].

Classical examples of collision-based gates are shown in Fig. 1. The interaction gate involves two balls, to represent values of variables x and y (Fig. 1a). If two balls are present at the input trajectories, this corresponds to both variables having TRUTH values they collide and deflect in the result of collision. The deflected trajectories of the balls represent conjunction of the input variables, xy. If only one ball, say the ball corresponding to the variable x, is present initially, then this ball travels along its original trajectories and does not change its velocity vector. The undisturbed trajectories of the balls represent logical functions xy and xy (Fig. 1a).

Switch gate (Fig. 1b) is another famous example, which also demonstrate a role of mirrors (stationary localizations). In the switch gate the signal x is conditionally routed by a control signal c. If signal is not present the ball x continues along its original trajectory traveling South-East. The ball x is delayed and its trajectory shifter eastward if the signal c is present in the system. After collision balls x and c are reflected but their further propagation is restricted by mirrors: the ball c collides with Northern mirror and the ball x with the Southern mirror (Fig. 1b).

Collision-based computing in natural systems

Those focused on implementation issues may wonder how a scheme of collisionbased computing can be implemented in natural, chemical, physical or biological, materials. In this section we provide two examples of computing with localizations in spatially extended quasi-chemical (reaction-diffusion cellular automata) and excitable chemical (Belousov-Zhabotinsky reaction) systems.

Computing schemes in reaction-diffusion cellular automata: Spiral rule

The reaction-diffusion cellular automaton Spiral Rule [START_REF] Adamatzky | Computing in spiral rule reaction-diffusion hexagonal cellular automaton[END_REF] exhibits wide range of mobile and stationary localizations thus offering a unique opportunities to employ both travelling and still patterns in a computation process. We designed automaton that emulates non-linearity of activator (A) and inhbitor (I) interaction for sub-threshold concentrations of activator. The following quasichemical reaction was used to construct cell-state transition rules [START_REF] Adamatzky | Computing in spiral rule reaction-diffusion hexagonal cellular automaton[END_REF]:

A + 6S → A A + I → I A + 2I → S 3A → A A + 3I → I 2A → I β A → I I → S.
For sub-threshold concentration of the inhibitor and threshold concentrations of activator, the activator is suppressed by the inhibitor. For critical concentrations of the inhibitor both inhibitor and activator dissociate producing the substrate. The quasi-chemical reactions are mapped to cellular automaton rules as follows. Take a totalistic hexagonal cellular automaton (CA), where a cell takes three states -substrate S, activator A and inhibitor Iand the cell updates its state depending on just the numbers of different cell-states in its neighborhoods. The update rule can be written as follows:

x t+1 = f (σ I (x) t , σ A (x) t , σ S (x) t ) ,
where σ p (x) t is the number of cell x's neighbors (in seven cells neighborhood) with cell-state p ∈ {I, A, S} at time step t. The rule is compactly represented a matrix M = (M i j ), where 0 ≤ i ≤ j ≤ 7, 0 ≤ i + j ≤ 7, and M i j ∈ {I, A, S} [START_REF] Adamatzky | Glider-based computation in reaction-diffusion hexagonal cellular automata[END_REF]. The output state of each neighborhood is given by the row-index i (the number of neighbors in cell-state I) and column-index j (the number of neighbors in cell-state A). We do not have to count the number of neighbors in cell-state S, because it is given by 7 -(i + j). A cell with a neighborhood represented by indices i and j will update to cell-state M i j which can be read off the matrix. In terms of the cell-state transition function this can be presented as follows:

x t+1 = M σ 2 (x) t σ 1 (x) t .
The exact structure of the transition matrix is as follows [START_REF] Adamatzky | Computing in spiral rule reaction-diffusion hexagonal cellular automaton[END_REF]:

M =                           

S A I A I I I I S I I A I I I S S I A I I S I I A I S S I A S S I S S S

                          
The entry M 01 = A symbolizes the diffusion of activator A, M 11 = I represents the suppression of activator A by the inhibitor I, M z2 = I (z = 0, • • • , 5) is the selfinhibition of the activator in particular concentrations. M z0 = S (z = 1, • • • , 7) means that the inhibitor is dissociated in absence of the activator, and that the activator does not diffuse in sub-threshold concentrations; M zp = I, p ≥ 4 is an upper-threshold self-inhibition.

Starting in a random initial configuration the automaton will evolve towards a quasi-stationary configuration, with typically two types of stationary localizations, and a spiral generator of mobile localizations, or gliders (Fig. 2). The core of a glider-gun is a discrete analog of a 'classical' spiral wave. However, at some distance from the spiral wave tip the wave front becomes unstable and splits into localized wave-fragments. The wave-fragments continue traveling along their originally determined trajectories and keep their shape and velocity vector unchanged unless disturbed by other localizations. So, the wave-fragments behave as in sub-excitable Belousov-Zhabotinsky systems.

Basic gliders, those with one (activator) head, are found in five types (Fig. 3), which vary by the number of trailing inhibitors. Three types (G 34 , G 24 , G 43 ) alternate between two forms. Two types (G 4 , G 5 ) have just one form. The spiral glidergun in Figs. 2 emits G 34 gliders. An alternative, low frequency, spiral glider-gun [START_REF] Wuensche | On spiral glider-guns in hexagonal cellular automata: activator-inhibitor paradigm[END_REF] (not shown) releases G 4 gliders. These basic gliders, and also a variety of more

p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p bbp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p bp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p rbp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p brp p p p p p p p p p p p p p p p p p p p p p p p p p bbp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p bbp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p bp p p p p p p p bp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p brrbp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p rbrp p p p p p p p p p p p p p p p p p p p p p p p p p bp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p brrbp p p p p p p p p p p p p p p p p p p p p rbp p brrbp p p p p p p p p p p p p p p p p p p p p p p p p p p brp p p p p p p p p p bp p p p p p p p p p p p p p p p

p p p p p p p p p brrbp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p brbp p p p p p p p p p p p p p p p p bp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p bbp p p bbp p p p p p p p p p p p p bbp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p rbp p p p p p p p p p p p brp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p bp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p bbp p p p p p p p p p p p p p p p p p p bbp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p rbp p p p p p p p p p p p p p p p p p brp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p bp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p bbp p p p p p p p p p p p p p p p p p p p p p p p p bbp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p rbp p p p p p p p p p p p p p p p p p p p p p p p brp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p bbbp p p p p p p p p p bp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p bp p p p p p p p p p p p brrbp p p p p p p p brrbp p p p p p p p p p p p p p p p p p p p p p p p p p bbbp p p p p p p p p p p brrbp p p p p p p p p p p brbp p p p p p p p p rbrp p p p p p p p p p p p p p p p p p p p p p p p p p brrbp p p p p p p p p p rbrbp p p p p p p p p p p bbp p p p p p p p p brrbp p p p bp p p p p p p p p p p p p p p p p p p p p brbp p p p p p p p p p p brrbp p p p p p p p p p p p p p p p p p p p p p p p bp p p p p p bbp p p p p p p p p p p p p p p p p p p p bbp p p p p p p p p p p p bp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p brp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p bp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p bbp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p brp bbbp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p brrbp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p brbp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p bbp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p (a)

Fig. 2 A typical quasi-stable configuration of the CA which started its development in a random initial configuration (with 1/3 probability of each cell-state). Cell-state I (inhibitor) is shown by a black disk, cell-state A (activator ) by a circle, and cell-state S (substrate) by a dot. We can see there are two types of stationary localizations (glider eaters) and a spiral glider-gun, which emits six streams of gliders, with frequency a glider per six time steps in each glider stream. From [START_REF] Adamatzky | Computing in spiral rule reaction-diffusion hexagonal cellular automaton[END_REF].

complicated gliders including mobile glider-guns, are also generated by many other interactions. Stationary localizations, or eaters, (Fig. 3ij) is yet one more important feature of the CA. Principle components of any computing device are input interface, memory, routers and logical gates. We refer readers to the paper [START_REF] Adamatzky | Computing in spiral rule reaction-diffusion hexagonal cellular automaton[END_REF] to study possible input functions.

How to implement a memory in the Spiral Rule CA? The eater E 6 can play the role of a 6-bit flip-flop memory device. The substrate-sites (bit-down) between inhibitor-sites (Fig. 3ij) can be switched to an inhibitor-state (bit-up) by a colliding glider.

An example of writing one bit of information in E 6 is shown in Fig. 4. Initially E 6 stores no information. We aim to write one bit in the substrate-site between Fig. 4 Write bit. From [START_REF] Adamatzky | Computing in spiral rule reaction-diffusion hexagonal cellular automaton[END_REF].

the northern and north-western inhibitor-sites (Fig. 4a). We generate a glider G 34 (Fig. 4bc) traveling West. G 34 collides with (or brushes past) the North edge of E 6 resulting in G 34 being transformed to a different type of glider, G 4 (Fig. 4gh).

There is now a record of the collision -evidence that writing was successful. The structure of E 6 now has one site (between the northern and north-western inhibitorsites) changed to an inhibitor-state (Fig. 4j To read a bit from the E 6 memory device with one bit-up (Fig. 5a), we collide (or brush past) with glider G 34 (Fig. 5b). Following the collision, the glider G 34 is transformed into a different type of basic glider, G 3 4 (Fig. 5g), and the bit is erased (Fig. 5j).

To route signals we can potentially employ other gliders to act as mobile reflectors. Figure 6 shows how a glider traveling North-West collides with a glider traveling West, and is reflected South-West as a result of the collision. However both gliders are transformed to different types of gliders. This is acceptable on condition that both types of glider represent the same signal, or signal modality.

There are two more gates which are useful in designing practical collisionbased computational schemes. They are the FANOUT gate and the ERASE gate. The FANOUT gate is based on glider multiplication. There are a few scenarios where one glider can be multiplied by another glider (for details see the original beehive rule [START_REF] Wuensche | Glider dynamics in 3-value hexagonal cellular automata: The beehive rule[END_REF]), e.g. one can make a FANOUT gate by colliding glider G 34 with glider G 24 . The gliders almost annihilate as a result of the collision, however recover into a complicated, which splits into three G 5 gliders. To annihilate a glider we can collide it with the central body of an eater, or with another glide, e.g. head-on collisions usually lead to annihilation.

The asynchronous XOR gate can be constructed from the memory device in Figs. 4 and5, employing the eater E 6 and the glider G 34 . The incoming trajectory of gliders is an input x = x, y of the gate, and the state of the cell which is switched to the inhibitor state by gliders, is an output z of the gate (this cell is shown by ⊗ in Fig. 7a). As seen in Fig. 4, when glider G 34 brushes by the eater E 6 it 'adds' one inhibitor state to the eater configuration (Fig. 4 glider G 43 . If glider G 34 brushes by E 6 with an additional inhibitor state (Fig. 5,t) it 'removes' this additional state and transforms itself into glider G 4 (Fig. 5, t + 11).

Assume that the presence of glider G 34 symbolizes input logical TRUE and its absence -input FALSE, inhibitor state I in cell ⊗output TRUE and substrate state S -output FALSE. The result of this logical operation can be read directly from the configuration of E 6 or by sending a control glider to brush by E 6 to detect how the glider is transformed. Then the structure implements exclusive disjunction (Fig. 7b). The gate constructed is asynchronous because the output of the operation does not depend on the time interval between the signals but only on the value of signals: when inhibitor state is added or removed from E 6 the configuration of E 6 remains stable and does not change till another glider collides into it.

The eater E 6 can take four different configurations resulting from the interactions of gliders brushing past, and there are seven types of glider produced in collisions with the eater (including some basic types flipped). We therefore envisaged [START_REF] Adamatzky | Computing in spiral rule reaction-diffusion hexagonal cellular automaton[END_REF] that a finite state machine can be implemented in the eater-glider system. The internal state of such a machine is represented by the configuration of the eater, the type of incoming glider symbolizes the input symbol of the machine, and the type of outgoing glider represents the output state of the machine. To construct the full state transition table of the eater-glider machine we collided seven types of glider into four configurations of the eater and recorded the results of the collisions. For the sake of compact representation we encoded the configurations of the eater as shown in Fig. 8. We denote the gliders as follows: G 34 as a, G 43 as b, G 5 as c, G 4 as d, G 24 as e, G 4 (glider G 4 flipped horizontally) is f , and G 43 (glider G 43 flipped horizontally) is g. The state transition table is shown in Fig. 9. 9 The state transition table of the eater-glider machine. Tuple xy, a pair made up of an eater state x and glider state y, at the intersection of the ith row and jth column, signifies that being in state i while receiving input j the machine takes state x and generates output y.

p
Consider the internal states of the eater-glider machine as unary operators on the set {a, b, c, d, e, f , g}, i.e. the machine's state is reset to its initial state after the collision with the glider. For example, the unary operator α implements the following transformation: a → b, b → c, c → a, d → a, e → d, f → e, g → e. The operators have the following limit sets: operator α has the limit set {a, b, c}, β -set {c}, χ has two limit sets {a, d} and {b, c}, and operator δ -two limit sets {a, b, c, d} and {e, f }. Considering unary operators a, • • • , g operating on set {α, β , χ, δ } we obtain the limit sets shown in Fig. 10. Many of the operators have more then two limits sets, which may indicate significant computational potential of the eater-glider machine. String s, at the intersection of the ith row and jth column, tells us that being initially in state i and receiving a uniform string j, the machine generates string s.

Input string abcde f g evokes the following output strings when fed into the machine. The machine starting in state α generates string begabac, in state β -string dcgabac, in state χ-string deccgae, and in state δ -string bcccgae.

Collision-based computing in excitable chemical media

In this section we give a brief introduction to implementation of collision-based circuits in excitable chemical media, Belousov-Zhabotinsky (BZ) system. Examples discussed here are based on numerical experiments, see Chapter "Reaction Diffusion Computers" of this book on implementation of collision-based circuits in BZ medium in chemical laboratory conditions. Now we discuss computing with localized wave-fragments in the Oregonator [START_REF] Field | Oscillations in chemical systems. iv. limit cycle behavior in a model of a real chemical reaction[END_REF][START_REF] Tyson | Target patterns in a realistic model of the Belousov-Zhabotinsky reaction[END_REF] model adapted to a light-sensitive BZ reaction with applied illumination [START_REF] Beato | Pulse propagation in a model for the photosensitive Belousov-Zhabotinsky reaction with external noise[END_REF][START_REF] Krug | Analysis of the modified complete oregonator (mco) accounting for oxygen-and photosensitivity of Belousov-Zhabotinsky systems[END_REF]:

∂ u ∂t = 1 ε (u -u 2 -( f v + φ ) u -q u + q ) + D u ∇ 2 u , and
∂ v ∂t = u -v . Collision Based Computing 13
where variables u and v represent local concentrations of bromous acid HBrO 2 and the oxidized form of the catalyst ruthenium Ru(III), ε sets up a ratio of time scale of variables u and v, q is a scaling parameter depending on reaction rates, f is a stoichiometric coefficient, φ is a light-induced bromide production rate proportional to intensity of illumination (an excitability parameter -moderate intensity of light will facilitate excitation process, higher intensity will produce excessive quantities of bromide which suppresses the reaction). We assumed that the catalyst is immobilized in a thin-layer of gel, therefore there is no diffusion term for v. To integrate the system we use Euler method with five-node Laplasian operator, time step t = 10 -3 and grid point spacing x = 0.15, with the following parameters: φ = φ 0 + A/2, A = 0.0011109, φ 0 = 0.0766, ε = 0.03, f = 1.4, q = 0.002. Chosen parameters correspond to a region of "higher excitability of the subexcitability regime" outlined in [START_REF] Sendiña-Nadal | Wave propagation in subexcitable media with periodically modulated excitability[END_REF] that supports propagation of sustained wave fragments (Fig. 12a). These wave fragments are used as quanta of information in our design of CB logical circuits. The waves were initiated by locally disturbing initial concentrations of species, e.g. ten grid sites in a chain are given value u = 1.0 each, this generated two or more localized wave fragments, similarly to counterpropagating waves induced by temporary illumination in experiments. The traveling wave fragments keep their shape for around 4•10 3 -10 4 steps of simulation (4-10 time units), then decrease in size and vanish. The wave's life-time is sufficient however to implement logical gates; this also allows us not to worry about 'garbage collection' in the computational medium.

We model signals by traveling wave fragments [START_REF] Beato | Pulse propagation in a model for the photosensitive Belousov-Zhabotinsky reaction with external noise[END_REF][START_REF] Sendiña-Nadal | Wave propagation in subexcitable media with periodically modulated excitability[END_REF]: a sustainly propagating wave fragment (Fig. 12a) represents TRUE value of a logical variable corresponding to the wave's trajectory (momentarily wire). To demonstrate that a physical systems is logically universal it is enough to implement negation and conjunction or disjunction in spatio-temporal dynamics of the system. To realize a fully functional logical circuit we must also know how to operate input and output signals in the system's dynamics, namely to implement signal branching and routing; delay can be realised via appropriate routing.

We can branch a signal using two techniques. Firstly, we can collide a smaller auxiliary wave to a wave fragment representing the signal, the signal-wave will split then into two signals (these daughter waves shrink slightly down to stable size and then travel with constant shape further 4 • 10 3 time steps of the simulation) and the auxiliary wave will annihilate (Fig. 12b). Secondly, we can temporarily and locally apply illumination impurities on a signal's way to change properties of the medium and thus cause the signal to split (Fig. 12c).

A control impurity, or reflector, consists of a few segments of sites which illumination level is slightly above or below overall illumination level of the medium. Combining excitatory and inhibitory segments we can precisely control wave's trajectory, e.g. realize U-turn of a signal (Fig. 12d).

A typical billiard-ball model interaction gate [START_REF] Fredkin | Conservative logic[END_REF][START_REF] Margolus | Physics-like models of computation[END_REF] has two inputs -x and y, and four outputs -xy (ball x moves undisturbed in absence of ball y), xy (ball y moves undisturbed in absence of ball x), and twice xy (balls x and y change their trajectories when collide to each other). We were unable to make wave fragments implement exact billiard-ball gate, because the interacting waves either fuse or one of the waves annihilates in result of the collision to another wave.

However, we have implemented a BZ (non-conservative) version of billiard-ball gate with two inputs and three outputs, i.e. just one xy output instead of two. This BZ collision gate is shown in Fig. 13.

Rich dynamic of BZ medium allows us also to implement complicated logical operations just in a single interaction event. An example of a composite gate with three inputs and six outputs is shown in Fig. 14. As we see in Fig. 14, some outputs, e.g. xyz, are represented by gradually vanishing wave fragments. The situation can be dealt with by either using very compact architecture of the logical gates or by installing temporary amplifiers made from excitatory fragments of illumination impurities.

As know from results of computer simulations and experimental studies, classical excitation waves merge or annihilate when collide one with another. This may complicated implementation of non-trivial logical circuits in classical excitable media. Wave-fragments however behave a bit differently, more like quasi-particles.

In computational experiments with exhaustive analysis of all possible collisions between localized wave-fragments [START_REF] Adamatzky | Binary collisions between wavefragments in sub-excitable Belousov-Zhabotinsky medium[END_REF] we classified all the collisions as (Fig. 15): quasi-elastic reflection of wave-fragments (Fig. 15a), pulling and pushing of a wavefragment by another wave-fragment (Fig. 15bc), sliding of one wave-fragment along refractory trail of another fragment (Fig. 15d), and translation of wave-fragment along one axis by another wave-fragment (Fig. 15e). Examples of two types of collision are shown in Fig. 16.

One-Dimensional Cellular Automata

This section deals with cellular automata in general and discrete signals in particular. It is shown both how they compute in the classical understanding and how they can be used to implement some phenomena relevant to massively distributed computing but without any sequential counterpart.

Cellular automata (CA) were introduced as a discrete model for parallel, local and uniform phenomena, whether of engineering, physical or biological nature. They often provide a medium where signals naturally appear and are thoroughly used to understand the global dynamics. The other way round, a correct handling of such signals is the key to compute and to design special purpose CA.

A cellular automaton works in the following way. The space is regularly partitioned in cells. All the cells are identical and are regularly displayed as an infinite array (having as many dimensions as the modeled space). Each cell can be in finitely many states and evolves according to its state and the states of the surrounding cells -locality. All the cells are identical and behave similarly -uniformity. The cells are all updated synchronously, like a massive parallel process sharing a single clock. By essence, CA form a discrete model: discrete time, discrete space and discrete values. Generally, the array is considered to extend infinitely in all directions so that there is no boundaries to deal with. However, borders can be encoded by special states which are never changed and make the two sides independent. Another way to simulate a CA on a computer is to consider that outside of a finite range, all cells are in the same stable state (called a quiescent state). Finite/periodic configuration can also be generated by displaying the cells to be on a ring (or torus): the last and first are then neighbors.

Previous collision based systems are CA, or better say are simulated by CA, some of them working on hexagonal lattices. Computation in dimension two and above can be done strait-forwardly as already presented by bit encoding and implementation of logic gates. From now on, only one dimensional space is considered because on the one hand, in higher dimension can -up to some point-be treated alike or correspond to what has been exemplified in previous sections and because on the other hand, dimension one is particularly restrictive and needs special focus.

The reader interested in CA might consult [START_REF] Ilachinski | Cellular automata -a discrete universe[END_REF][START_REF] Kari | Theory of cellular automata: a survey[END_REF][START_REF] Sarkar | A brief history of cellular automata[END_REF] for various topics not covered here.

Signals in CA

In space-time diagrams, or orbits, configurations are concatenated as iterations go. They are very important in oder to comprehend the dynamics. Since the temporal coordinate is added, this leads to an array with one more dimension than the underlying space.

A signal is anything periodic in the space-time diagram. If the periodicity is in two directions, then can fill the whole space-time and is referred as a background, the substrata upon which signals move. The frontier between two backgrounds is a signal as long as it is periodic. Figure 17 provides an example with a complex background (alternatively 0111, 1000, 1101 and 0010 repeating) on the left. On the right, signals are revealed by an ad hoc filtering. This example illustrates the variety in width and pattern of signals. As it can be seen, collisions between signals can be pretty complicated.

Computing in one dimensional systems

In dimension two and above, as soon as it is possible to carry information around (with signal), to make information crossing and duplication and to process it (with collision) in the proper way to yield a sufficiently large set of logical gates then computation is straightforwardly possible.

In dimension one, this is not so easy because there is no way for a signal to go around another one or some static artifact. This means that signal propagation is really an issue and, for example, handling garbage signals can be cumbersome. One way to cope with it is to have various kinds of signals not identically affected by artifacts (some would pass unaffected while others interact).

This means that to use the bits and gates scheme, one has to be very careful with available signals and have a very clever positioning of the logic circuitry which is always thought of as two dimensional (time often provides the extra dimension for displaying it). For example, the construction of Ollinger [START_REF] Ollinger | The quest for small universal cellular automata[END_REF] provides a small CA that is able to compute with circuit implementation where displaying the circuit is not straightforward.

Another way to tackle computation is to use other formalisms. One classical way is to go back to Turing machines, another one is to implement minimal rewriting systems like cyclic tag systems.

Turing machine

A Turing machine is a finite automaton acting on a potentially infinite array of symbols. The computation starts with the automaton in its initial state and the input written on the tape. The tape is accessed through a read/write head. Each iteration, the automaton reads the symbol under the head, rewrites a symbol, changes its state and moves the head left or right. A Turing machine is basically one-dimensional as its tape, so that it naturally fits on a one dimensional CA.

The simulation is rather simple: signals encoding the symbols are motionless and one signal amounting for the state of the automaton is moving round updating the symbols. Collisions are as follows: a moving state meet a stationary symbol, this leaves a new stationary symbol and a moving new state. (Fig. 24 in the next section provides a clear illustration of this in a continuous setting.) This was implemented by, for example, Lindgren and Nordahl [START_REF] Lindgren | Universal computation in simple onedimensional cellular automata[END_REF].

Cyclic tag systems

Another way to define computation is to rely on a word which is rewritten until the system halts. The input is given as the starting word and the output is the final word. Connexion with Turing machine is straightforward when considering the tape as a finite word and the state of the automaton as an extra symbol where is the head.

Cyclic tag systems (CTS) is a particular case of many Turing-universal rewriting systems. A CTS considers a binary word together with a circular list of binary words (appendants). Each iteration the first bit is removed from the word and if it is 1 then the first appendant of the list is added at the end of the word, then the list is rotated. The computation stops when the word is empty or a special halting word (denoted h in the example) is activated. An example is provided on Fig. 18. Cyclic tag systems were proven able to perform any computation [START_REF] Cook | Universality in elementary cellular automata[END_REF] and even to do so in polynomial time [START_REF] Woods | On the time complexity of 2-tag systems and small universal Turing machines[END_REF] and were used to built very small universal Turing machines [START_REF] Neary | Four fast universal Turing machines[END_REF]. They have been implemented in one dimensional CA with collision/signal based computing by Cook [START_REF] Cook | Universality in elementary cellular automata[END_REF] to produce computation universal CA with only two states (it is impossible to compute with less). The construction relies on signals moving and colliding that are seek and classified in order to work on a more abstract level.

As far as minimal CA are concerned, it is worth mentioning that 4 states are enough to get a one dimensional CA able to simulate any other one dimensional CA [START_REF] Richard | A particular universal cellular automaton[END_REF]. This is not Turing universality since the simulation encompasses infinite configurations.

Signal specific issues

Since CA form a model for physical phenomena and also for parallel computing architectures, other issues arise. One is to understand the underlying dynamics when used as a discrete model. The other is to design CA for special purposes.

Signals to understand dynamics

Once a simulation is running as a CA, one common way to understand the dynamics is to try to find regularities in the space-time diagram and observe them. They are often the key to the underlying dynamics and then to predict. (Although it might happen that what is observed is nothing but an artifact of the model and has no counterpart in reality.) This is made clear by considering two examples.

The first one models sand dripping in a one dimensional space. The dynamics is quite simple: there is nothing in the initial configuration and each iteration, one grain is added to the first pile/cell. Each time a pile has at least two more grains than the nest one, a grain falls.

If only grains dropping at odd time are colored in black, then their position is as on Fig. 19(a) after 10000 iterations and only the top grains will ever move. This strange disposal as well the two different slopes and precise long term behavior are explained by signals [START_REF] Durand-Lose | Grain sorting in the one dimensional sand pile model[END_REF][START_REF] Durand-Lose | Parallel transient time of one-dimensional sand pile[END_REF]. These signals can be identified on Fig. 19(b) where the successive configurations (iteration 100 to 150) are set one after the other to form a volume. On this volume, triangles can be seen on the lower (as well as the upper parts), their frontiers are signals (which can be revealed with an appropriate filtering). Another example is provided by [START_REF] Das | Evolving globally synchronized cellular automata[END_REF]. The aim is to generate a CA with 2 states and 5 closest cells neighborhood, such that, on a ring of any size whatever configuration it is started on, it always ends up blinking: all cells are 0 then all cells are 1, alternatively, forever. Instead of trying to built it straightaway, evolutionary programming is used: random CA are generated; they are ranked according to their "blinking capability"; then the best are kept, recombined and mutated to form the next generation. It then cycles through ranking and next generation until one "fully blinking" CA emerges.

The obtained CA is analyzed in term of signal (again with some filtering) as illustrated on Fig. 20. (The apparent non-connectivity of some signals comes from the filtering and also because cells can influence one another up to distance two.) The evolutionary process goes in steps where various intermediate levels of "blinking" appear. Analyzing typical members of each level reveals the progressive apparition of signals and collision rules.

It is very important to notice how, in a context where signals were not asked for by the evolutionary process they indeed appear and are the key both to the desire dynamics and to the evolutionary process. in a chromosome. This de nes one generation of the GA; it is repeated G times for one GA run. FI( ) is a random variable since its value depends on the particular set of I ICs selected to evaluate . Thus, a CA's tness varies stochastically from generation to generation. For this reason, we choose a new set of ICs at each generation For our experiments we set P = 100, E = 20; I = 100, m = 2; and G = 50. M was chosen from a Poisson distribution with mean 320 (slightly greater than 2N). Varying M prevents selecting CAs that are adapted to a particular M. A justi cation of these parameter settings is given in 9].

We performed a total of 65 GA runs. Since F100( ) is only a rough estimate of performance, we more stringently measured the quality of the GA's solutions by calculating P N 10 4( ) with N 2 f149; 599; 999g for the best CAs in the nal generation of each run. In 20% of the runs the GA discovered successful CAs (P N 10 4 = 1:0). More detailed analysis of these successful CAs showed that although they were distinct in detail, they used similar strategies for performing the synchronization task. Interestingly, when the GA was restricted to evolve CAs with r = 1 and r = 2, all the evolved CAs had P N Figure 1a gives a space-time diagram for one of the GA-discovered CAs with 100% performance, here called sync. This diagram plots 75 successive con gurations on a lattice of size N = 75 (with time going down the page) starting from a randomly chosen IC, with 1-sites colored black and 0-sites colored white. In this example, global synchronization occurs at time step 58.

How are we to understand the strategy employed by sync to reach global synchronization? Notice that, under the GA, while crossover and mutation act on the local mappings comprising a 4 The previous example does not compute in the classical understanding, nevertheless, it provides a relevant dynamical global property.

Signals to generate a particular behavior

Computing in the usual understanding is a special behavior. But CA can also be thought of as a computing model on its own. Then primitives can be specially defined to take advantage of the huge parallelism. Signals are the key to manage it.

As already cited, the pioneer work of Fischer [START_REF] Fischer | Generation of primes by a one-dimensional real-time iterative array[END_REF] generates prime numbers by a parallel implementation of the Sieve of Eratosthenes where they are indicated as no signal on the first cell at the corresponding times. Prime numbers can then be read on the space-time diagram by observing the state of the first cell.

Another complex behavior is the famous Firing Squad Synchronization problem (FSS). Starting from all but one cell in a quiescent state, one wants all the cells to enter simultaneously the same state -which has not been used before. Like if they would all blink for the very first time synchronously.

Each example of Fig. 21 shows the Euclidean conception and then the discrete implementation of a FSS solution. Both construction relies on a recursive cut in halves. In the discrete implementation, at some point, the granularity of space -a cell cannot be divided-is reached. Since CA are synchronous, this point is reached simultaneously everywhere, ensuring the global synchronization of the entire array of cells. ) and even iteration are graphically achieved. The programming system is achieved by using trellis of adaptable size that can be dynamically generated. The computation is carried out over the trellis. Composition is then achieved by having the next computation displayed on a new trellis. Recursion is provided by a scheme that dynamically starts another iteration providing each time an adapted trellis.

Abstract Geometrical Computation

Abstract Geometrical Computation (AGC) is an idealization of collision based computing where particles/signals are dimensionless (time and space are continuous).

Although the number of signals in a bounded space is expected to be finite, it is unbounded. Another way to consider AGC is as a continuous counterpart of CA as

Computing

Computing in the classical understanding is pretty easy. In fact, many constructions for CA directly translate to ACG and are even easier since discreteness does not have to be taken into account. Two ways to achieve computability are presented: Turing machines and Cyclic Tag Systems. For Turing machines (as presented in Subsubsec. 4.2.1), the implementation is quite straightforward: static signals encode the tape -one signal per symbol-and one signal encodes the state of the automaton and the position of the head. The later moves forth and back from symbol to symbol as the read/write head. This is depicted on an example on Fig. 24. The construction is detailed in [START_REF] Durand-Lose | Abstract geometrical computation 3: Black holes for classical and analog computing[END_REF]. Cyclic Tag Systems are presented in Subsubsec. 4.2.2. The simulation is done by encoding, left to right, the word and then the circular list of appendants by parallel signals encoding the bits as shown on Fig. 25(a). Each iteration, the list is rotated to the right, but before that, if the erased bit of the word is 1 a copy is left. The copy is directly added at the right of the word as on Fig. 25(b) which present one full iteration. The full simulation of the example of Fig. 18 is given on Fig. 25(c). The rightward drifting corresponds to the erasure of the word from the left and to the rightward rotation of the list. Each group of oblique lines corresponds to one rotation of the list.

-→ q i -→ q i -→ q i ← - q 1 -→ q 1 -→ q 1 -→ q 2 ← - # -→ # ← - q f ← - # -→ # ← - q f ← - # -→ # -→ # # ← - q f ← - q f ← - q f (b) TM simulation
This simulation is detailed in [START_REF] Durand-Lose | Abstract geometrical computation: small Turing universal signal machines[END_REF]. The signal machine obtained is able to simulate any CTS, and in thus Turing universal. It is the smallest such one known (it has only 13 meta-signals).

Geometric primitives

As for CA, AGC can also be considered as a model on its own with particular operators that might not have any classical computation counterpart (like FSS) nor discrete counterpart.

All the following constructions involve to add meta-signals and rules to a given SM so that the desire capability exists. Signals have to be added to the initial configuration in order to fire the effect. Rules can also be modified in order to dynamically fire it.

Space and time are continuous and scale-less so that since signals have no dimension, there is no limit on the scalability. If all signals are scaled spatially by a given coefficient, the whole computation is also scaled temporally. So that the duration of a computation is meaningless and complexity measures such as the maximal number of collisions with a causal link has to be used.

Spatial rescaling of the initial configuration is a static operation. It is also possible to do it during the computation. The construction relies on the ability to freeze a configuration.

Freezing a computation is quite simple. One signal is added on one side and it crosses the entire configuration. Doing so, each time it meets a signal (or enters in a previously existing collision), it replaces it by another signal encoding the metasignal. All the encoding signals have the same speed: they are parallel and do not interact and moreover the distance between them is preserved. The configuration is frozen and shifts. To unfreeze it, a signal comes from the side, crosses the configuration, and replaces each encoding signal by the encoded one (or the result of the collision). Freezing and unfreezing signals must have the same speed so that the configuration is restored exactly as it was, up to a translation. (And indeed they correspond to the same meta-signal toggle.) This is depicted on Fig. 26 where the scheme is presented as well as an example on the right. Meanwhile a configuration is frozen into parallel signals it is possible to act on these signals. One simple trick is to change their direction. On Fig. 27(a), this is done twice so as to restore the original direction. (An extra signal is used on the right to delete the structure.) As a result, since different slopes are used to change direction, the distances between signals are scaled (here by one half). Adding freezing and unfreezing signals (automatically fired in due time) an artifact to scale down a whole configuration is generated as it can be seen on the Fig. 27(c). The initial configuration has been modified in order to start straightaway the effect. It is also possible to fire it dynamically during the computation when some special collision happens. This is used to iterate it.

Infinite acceleration and non recursive function

Scaling can be automatically restarted ad infinitum, since both space and time are continuous, this is not a problem -at least before the singularity. In the example of Fig. 28, a computation producing an infinite trellis extending indefinitely in both space and time in folded into the structure. The right signal and the middle one are very important since the folded computations should be bounded in order to ensure that is fully scaled.

A singularity refers to an accumulation of infinitely many collisions and signals to a given location. Figure 28(a) shows that the structure alone already create a singularity. This illustrates the Zeno paradox. The leftmost signals of Fig. 28(a) form an infinite sequence with infinitely (yet countably) many collisions although the time elapsed as well as the total distance crossed by signals is finite.

All the signals and collisions that would have existed if there would have been no folding indeed exist, but in a bounded portion of the space and time diagram. (The equivalence of the plane and a bounded part is somehow implemented.) So that up to the presence of the structure and of the frozen parts, and the different scales the computation is the same. Any computation starting with finitely many signals can be folded. Inside the structure, the rescaling provide speedup (the closer the faster they collide). This speedup is unbounded and goes to infinity. Inside the structure there is a space-time where time-lines are infinitely accelerated compared to the outside. This is the first step to emulate the Black-hole model of computation [START_REF] Etesi | Non-Turing computations via Malament-Hogarth space-times[END_REF][START_REF] Hogarth | Non-Turing computers and non-Turing computability[END_REF][START_REF] Lloyd | Black hole computers[END_REF].

The second step it to find a way for an atomic piece of information to leave the black hole, here the singularity. One meta-signal can be added and rules changed so that the new meta-signal is not affected by the structure but can be generated by the initial computation.

The final step is to add bounding signals on both side of the folding (called here horizonLe and horizonRi). At their collision point, the folded computation is entirely in the casual past as displayed on Fig. 29. Any signal leaving the folding would have been collected. This way the black hole model is emulated: there are two time-lines, one for the machine and one for the observer. The machine one is infinite. On the observer one, after a finite duration, the whole machine one is entirely in the casual past. A single piece of information can be sent by the machine to the observer and it has to be sent after a finite (machine) duration. The ultimate date for the observer to receive anything from the machine is finite and known. To understand the power of this model just imagine that the machine only send a signal if its computation ends. So that the observer received a signal only if the it stops and after a duration the observer is aware of, any signal sent would have been received. So that just by checking its clock, the observer knows that the computation did not halt when it is the case. Altogether, the halting problem (whose undecidability is the cornerstone of Turing computability theory) is decidable! This model, as well as AGC, clearly computes beyond Turing. In formal term it can decide Σ 1 0 formulae in the arithmetical hierarchy, i.e. a recursive/computable predicate prefixed by an existential quantifier. This includes, for example, the consistency of Peano arithmetic and Set theory, many conjectures such as the Collatz conjecture and Goldbach's conjecture.

Defining what happens at the singularity point is not easy especially since the accumulating set can be a line segment, a fractal curve or even a Cantor! (To understand this, take a continuous look at the FSS: what would happen at the bottom of Fig. 21?) For singularity on a single point, a careful continuation has been proposed in [START_REF] Durand-Lose | Abstract geometrical computation 3: Black holes for classical and analog computing[END_REF] that allows to climb the arithmetical hierarchy. There is also another use of isolated singularity as a way to provide limits for analog computation.

Analog computation

Unlike collision based computing and CA, with dimensionless signals in a continuous space, it is possible to encode reals as the distance between signals. In the AGC context, this distance is exact, i.e. it is a real number in exact precision. As long as signals are parallel, this distance is preserved. This allows to encode reals and to make some computations over them.

Since any real can be encoded exactly, the model ipso facto falls out of classical computability (because of cardinalities, there is no way to encode all the reals with natural numbers or finite strings). So that an analog model of computation has to be searched for.

With this encoding of real numbers, AGC is equivalent to linear Blum, Shub and Smale model (BSS) [START_REF] Blum | Complexity and real computation[END_REF]. In the linear BSS model, variables holds (exact) real numbers and the operations available are addition, multiplication by a constant and branch according to the sign of a variable. This equivalence is true as long as the BSS machine has an unbounded number of variables (accessed through a context shift like moving a window over an infinite array of variables), there are finitely signals and there is no singularity [START_REF] Durand-Lose | Abstract geometrical computation and the linear Blum[END_REF].

If singularities are used in a proper way, it becomes possible to multiply two variables. Then the classical BSS model can be implemented in AGC [START_REF] Durand-Lose | Abstract geometrical computation with accumulations: beyond the Blum, Shub and Smale model[END_REF]. The simulation is not possible in the other way round anymore since, for example, the exact square rooting can also be computed by AGC.

Fig. 1

 1 Fig. 1 Basics of billiard ball model: Fredkin-Toffoli interaction gate (a) and switch gate (b).From[START_REF] Fredkin | Conservative logic[END_REF].

Fig. 5

 5 Fig.5Read and erase bit. From[START_REF] Adamatzky | Computing in spiral rule reaction-diffusion hexagonal cellular automaton[END_REF].

Fig. 7

 7 Fig. 7 Asynchronous XOR gate. (a) position of output cell is shown by ⊗. (b) operation implemented by the gate, input state G 34 is logical TRUE, output state S is FALSE, output state I is TRUE. From [5].

Fig. 8

 8 Fig.8Encoding the internal states of the glider-eater machine in the configuration of eater E 6 .

  Fig.9The state transition table of the eater-glider machine. Tuple xy, a pair made up of an eater state x and glider state y, at the intersection of the ith row and jth column, signifies that being in state i while receiving input j the machine takes state x and generates output y.

Fig. 10

 10 Fig. 10 Limit sets of unary operators a, • • • , g.

Fig. 11

 11 Fig. 11 Input string to output string transformations implemented by the eater-glider machine.String s, at the intersection of the ith row and jth column, tells us that being initially in state i and receiving a uniform string j, the machine generates string s.

Fig. 12

 12 Fig. 12 Basic operations with signals. Overlay of images taken every 0.5 time units. Exciting domains of impurities are shown in black, inhibiting domains of impurities are shown in gray. (a) Wave fragment traveling north. (b) Signal branching without impurities: a wave fragment traveling east splits into two wave fragments (traveling south-east and north-east) when collides to a smaller wave fragment traveling west. (c) Signal branching with impurity: wave fragment traveling west is split by impurity (shown on the right) into two waves traveling north-west and south-west. (d) Signal routing (U-turn) with impurities: wave fragment traveling east is routed north and then west by two impurities (shown on the right). An impurity-reflector consists of inhibitory (gray) and excitatory (black) chains of grid sites. From [2].

Fig. 13

 13 Fig. 13 Two wave fragments undergo angle collision and implement interaction gate x, y → xy, xy, xy . (a) In this example x = 1 and y = 1, both wave fragments are present initially. Overlay of images taken every 0.5 time units. (b) Scheme of the gate. In upper left and bottom left corners of (a) we see domains of wave generation, two echo wave fragments are also generated, they travel outwards gate area and thus do not interfere with computation. From [2].

Fig. 14

 14 Fig. 14 Implementation of x, y, z → xy, yz, xyz, xyz, xyz, xyz interaction gate. Overlay of images of wave fragments taken every 0.5 time units. The following combinations of input configuration are shown: (a) x = 1, y = 1 z = 0, north-south wave collides to east-west wave. (b) x = 1, y = 1, z = 1, north-south wave collides to east-west wave, and to west-east wave. (c) x = 1, y = 0, z = 1, west-east and east-west wave fragments pass near each other without interaction. (d) x = 0, y = 1, z = 1, north-south wave collides to east-west wave. (e) Scheme of the gate. From [2].

Fig. 15

 15 Fig. 15 Schematic representation of interaction between wave-fragments. (a) reflection, (b) attraction, (c) repulsion, (d) sliding, (e) shifting-sliding. From [4].

Fig. 16 (

 16 Fig. 16 (a)-(d) Sliding: snapshots of wave-fragment moving South-West colliding to wavefragment traveling South-East. Center of the initial excitation of South-West wave-fragment is shifted southwards by 22 sites. From [4]. (e)-(h) Slide-shift: snapshots of wave-fragment moving South-East colliding to wave-fragment traveling West.

Fig. 17

 17 Fig. 17Filtering to exhibit signals and backgrounds on rule 54 (inspired from [13, Fig. 7]). Time is increasing upwards.

  Fig. 17Filtering to exhibit signals and backgrounds on rule 54 (inspired from [13, Fig. 7]). Time is increasing upwards.

Fig. 18

 18 Fig. 18 Example of computation of a CTS (given on the first line).

Fig. 19

 19 Fig. 19 One dimensional sand dripping.

10 4 0

 104 for N 2 f149; 599; 999g. (Better performing CAs with r = 2 can be designed by hand.) Thus r = 3 appears to be the minimal radius for which the GA can successfully solve this problem.

Figure 1 :

 1 Figure 1: (a) Space-time diagram of sync starting with a random initial condition. (b) The same spacetime diagram after ltering with a spatial transducer that maps all domains to white and all defects to black. Greek letters label particles described in the text.

Fig. 20

 20 Fig. 20 Figure and filtering to highlight signals and analyze (from [15, Fig. 1]). Time is increasing downwards.

  Fig. 20 Figure and filtering to highlight signals and analyze (from [15, Fig. 1]). Time is increasing downwards.

  Fig. 21 FSS implementations.

4. 3 . 3

 33 Signals as a computational model on its own Mazoyer et al. developed a computing model where multiplication (an on Fig. 22(a)), composition (an on Fig. 22(b)

Fig. 23

 23 Fig. 23 Example of a space-time diagram.

Fig. 24

 24 Fig. 24 Simulating a Turing machine.

Fig. 25

 25 Fig.25Simulating a cyclic tag system.

Fig. 26

 26 Fig. 26 Freezing and unfreezing.

Fig. 27

 27 Fig. 27 Scaling.

Fig. 28

 28 Fig. 28 Folding or infinite rescaling.

Fig. 29

 29 Fig.29Framing the folding to collect all signals exiting the folding.

  ) -a bit was saved.

	p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p ddp p p p p p p p dttdp p p p p p tdtp p p p p p p dttdp p p p p p p dp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p	p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p dp p p p p p p p tddp p p p p p p p dp p p p p ddp p p p p p p p dttdp p p p p p tdtp p p p p p p dttdp p p p p p p dp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p	p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p dp p p p p p p p tdp p p p p p p p p dp p p p p p ddp p p p p p p p dttdp p p p p p tdtp p p p p p p dttdp p p p p p p dp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p	p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p dp p p p p p p p tddp p p p p p p p p p p p p p p p dddp p p p p p p dttdp p p p p p tdtp p p p p p p dttdp p p p p p p dp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p	p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p dp p p p p p p p tp dp p p p p p p p p dp p p p p p p dddp p p p p p p dttdp p p p p p tdtp p p p p p p dttdp p p p p p p dp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p
	(a) t	(b) t + 5	(c) t + 7	(d) t + 8	(e) t + 9
	p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p ddp p p p p p p tddp p p p p p p p ddp p p p p p p p ddp p p p p p p p dttdp p p p p p tdtp p p p p p p dttdp p p p p p p dp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p	p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p ddp p p p p p p tdp p p p p p p p p dp p p p p p p p p p p dp p p p p p p p dttdp p p p p p tdtp p p p p p p dttdp p p p p p p dp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p	p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p ddp p p p p p p tdp p p p p p p p p dp p p p p p p p p p p p dp p p p p p p p dttdp p p p p p tdtp p p p p p p dttdp p p p p p p dp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p	p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p dp p p p p p p p dp p p p p p p p p p p p p p p p p p p p p p p dp p p p p p p p dttdp p p p p p tdtp p p p p p p dttdp p p p p p p dp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p	p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p dp p p p p p p p dttdp p p p p p tdtp p p p p p p dttdp p p p p p p dp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p
	(f) t + 10	(g) t + 11	(h) t + 12	(i) t + 13

(j) t + 14

  , t + 7), and transforms itself in

	p p p p p p p p p p p p p p p p p p p p p p p p p p p dp p p p p p p p p p p p p p tdp p p p p p p p p p p p p dp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p tdp p p p p p p p p p p p ddp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p	p p p p p p p p p p p p p p p p p p p p p p p p p p dp p p p p p p p p p p p p p tddp p p p p p p p p p p p dp p p p p p p p p p p p p p p p p p p p p p p p p p p p tdp p p p p p p p p p p p p ddp p p p p p p p p p p p p p dp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p	p p p p p p p p p p p p p p p p p p p p p p p p p dp p p p p p p p p p p p p p tdp p p p p p p p p p p p p dp p p p p p p p p p p p p p tp p p p p p p p p p p p p ddp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p	p p p p p p p p p p p p p p p p p p p p p p p p dp p p p p p p p p p p p p p tddp p p p p p p p p p p p ddp p p p p p p p p p p p p ddp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p
	(a) t	(b) t + 1	(c) t + 2	(d) t + 3
	p p p p p p p p p p p p p p p p p p p p p p p dp p p p p p p p p p p p p p tdp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p	p p p p p p p p p p p p p p p p p p p p p p dp p p p p p p p p p p p p p tp p p p p p p p p p p p p p tdp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p	p p p p p p p p p p p p p p p p p p p p p ddp p p p p p p p p p p p p tddp p p p p p p p p p p p dddp p p p p p p p p p p p p tdp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p	p p p p p p p p p p p p p p p p p p p p ddp p p p p p p p p p p p p tdp p p p p p p p p p p p p ddp p p p p p p p p p p p p p dddp p p p p p p p p p p p tdp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p
	(e) t + 4	(f) t + 5	(g) t + 6	(h) t + 7
		p p p p p p p p p p p p p p p p p p p ddp p p p p p p p p p p p p tdp p p p p p p p p p p p p dp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p dddp p p p p p p p p p p p p tdp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p	p p p p p p p p p p p p p p p p p p ddp p p p p p p p p p p p p tdp p p p p p p p p p p p p dp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p dddp p p p p p p p p p p p tdp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p
		(i) t + 8	(j) t + 9
	Fig. 6 Glider reflection. From [5].
		p p p p p p p i × ip p p iyyip p yiyp p iyyip p p ip p p p p p p p p p p p p

Edward Fredkin, Tommaso Toffoli, Norman Margolus and Elwyn Berlekamp and John Conway are fully recognized founders of the field of the collision-based computing. The term 'collisionbased computing' was first used in[START_REF] Adamatzky | Collision based computing[END_REF], there are however several equivalent but less used now terms as 'signal computing', 'ballistic computing', 'free space computing', and 'billiard ball computing'.

Adamatzky and Durand-Lose

Like in the discrete case, a proper handling of isolated singularities of any order can be used to decide quantified (over natural but not real numbers) predicates in the BSS model and climb the BSS-arithmetical hierarchy [20].

In abstract geometrical computation, dimensionless signals moves at constant speed. When they meet, they are replaced by others according to some rewriting rules. A signal machine (SM) gathers the definition of the nature of available signals (called meta-signals), their speeds and the collisions rules. There are finitely many meta-signals and each one is assigned a constant speed (velocity and direction). The constant speed may seem surprising, but each discrete CA signal has indeed a constant speed.

The space-time diagrams generated are continuous in both space and time and the traces of signals form line segments. For a given meta-signal, all these segments are parallel. In this section, only 1 dimensional AGC are considered so that the spacetime diagram is always two dimensional with time increasing upwards as illustrated by Fig. 23.

Space-time diagrams can be much more complicated and, as presented below, use continuity up to implement the Zeno paradox and emulate the Black hole model of computation.


Philippe Blache

Grégoire Montcheuil

Laurent Prevot

Stéphane Rauzy

Laurent Prévot

4-Couv: A New Treebank for French

Keywords: Treebank, French, Constituency, Treebanking Tools, Experimental Linguistic

teaching and research institutions in France or abroad, or from public or private research centers.

Introduction

Several treebanks already exist for French. The most popular one is the French Treebank (Abeillé et al., 2003, FTB) and its different evolutions or enrichments [START_REF] Schluter | Modified French Treebank. National Centre for Language Technology[END_REF][START_REF] Candito | French Converted Dependency Treebank[END_REF]. Other French dependency treebanks are also available, for example through the Sequoia project [START_REF] Candito | Sequoia Treebank. INRIA -Alpage[END_REF][START_REF] Candito | Deep-Sequoia. INRIA -Alpage -LORIA[END_REF] or the Universal Dependencies project [START_REF] Nivre | Universal Dependencies 1.0. LINDAT/CLARIN digital library at Institute of Formal and Applied Linguistics[END_REF]. However, and this constitutes the first motivation for developing a new treebank, it still remains necessary to develop other resources in order to increase the size and the variety of available material. A second and even more important reason to build specific treebanks is the type of application it can be used for. More precisely, classical treebanks are usually made of newspaper articles, rather long, and which interest when reading can be poor. This can constitute a drawback (or even a bias) when using such texts in human experimentation (in particular reading). In such cases, short, semantically coherent and self-contained texts are preferable for the acquisition of physiological responses from reading subjects. The solution we propose in this perspective consists in building a corpus of book backcovers1 , that are short texts, easily available and frequently used. We present in this paper the corpus2 , its annotation and first results.

Corpus description

Backcovers are short texts of different genres: extract, synopsis, genesis of the book, comment about the work, or a combination of them. Each text is semantically selfcontained, and interesting (minimizing attention and comprehension drops). A text contains between 4-10 sentences and 80-200 tokens (80% having at most 30 tokens).

We have build such a corpus, which is still under evolution. At this stage, it consists in 8,000 texts from different publishers (from Pocket and Gallimard publishers, with their agreement). These texts have been selected manually by three experts, according to a set of criteria among which interest when reading and semantic coherence. A subset of 500 texts, representing 3,500 sentences, has been annotated at morpho-syntactic, syntactic and to some extent discourse levels.

Annotations

4-Couv is a long-term project, that will be enriched progressively. The annotation process has then to be carefully documented. We present in this section the main features of the annotation guide and its application. We have decided to use a constituency-based representation first because we already have developed a parser in this format, second because we already did several experiment with the FTB, using different complexity indexes based on such format. An hybrid version of our treebank, integrating a dependency version, is planned.

Annotation guide

Most of the works in French parsing being done starting from the FTB, we decided to stay as close as possible with the FTB format. So the treebank is constituency-based and syntactic relations are represented by means of trees. However, the FTB contains several specific annotations, aiming at reducing the embedding of the trees (limitation of the projections, suppression of the VP level, affixation of clitics, etc.). In order to be compatible with more standard formats used in other treebanking projects, we slightly modified the initial FTB annotation guide. More generally, we apply the following formal constraints:

• no empty category is inserted in the trees (e.g. in the case of an elliptical construction), each node is instantiated by a lexical or a phrase-level unit.

• distinction between lexical and phrase level: we keep unary phrases, e.g. in (1) il or question are the unique constituent of a NP, as ici is of a AdP and éphémère is of a AP.

(1) "il est ici question d'amours éphémères" (it is here an issue of ephemeral loves) • no discontinuous constituent or unbounded dependencies directly encoded, such as in ( 2).

( • the phrase-level tagset (see figure 1) is reduced to classical phrases, at the exclusion of other constructions such as coordination (at the difference with the FTB and its derivatives).

• coordinations are represented by a succession of binary trees, as in (3).

(3) "il a connu la chute, le dénuement, la torture" (he known the fall, the deprivation, the torture) • the same types of syntactic functions than those introduced for the FTB (see figure 1) are used. This annotation is less precise then other annotation frameworks, such as [START_REF] Gendner | Les annotation syntaxiques de référence PEAS[END_REF] where structural and functional informations were given independently.

Morphosyntax

At the lexical level, the first step has concerned tokenization. It is based on the MarsaLex French lexicon 3 , containing 595.000 entries with their frequencies. Tokenization is maximal in that even highly constrained forms are split into distinct lexical units provided they follow syntactic composition rules. For example, constituents of semi-fixed expressions such as "il était une fois" (once upon a time) or "mettre à nu" (lay bare) are decomposed, at the difference with other multiwords expressions as "d'autant plus" (all the more) or "tant mieux" (great) as they do not follow any syntactic composition.

Each lexical category has a specific features set (see figure 2), although many features are common to different categories (typically the gender, number, person). The part-ofspeech and feature sets are relatively standard and compatible with most of automatically tagged corpus, and enable to indicate a combination of lexical, morphologic, syntactic and occasionally semantic informations that will have effect on the syntactic construction of upper levels, e.g. the number of a determiner, the subcategorization or the case of a clitic pronoun. We do not have discontinuous lexical constituent, and the tagging is disambiguated (i.e. each element have one part-of-speech, whose sub-categories features could be underspecified when necessary). We do not modify the category of units that change their paradigm ("une tarte maison" (an home[made] pie), "il est très zen" (he is very zen)).

The second step, POS-tagging, is done with the MarsaTag 4 tagger (0.975 F-Measure on written texts), trained on the LPL-Grace corpus (700,000 tag manually corrected). It associates each token with a list of possible tags with their probability, as described in figure 3. The automatic POS tagging has been manually corrected thanks to a specific editing tool, making it possible to correct labels as well as features (see section 4.2.). Among recurrent errors, several concern the agreement features, in particular determiner and adjective genders. Only few errors concern categorization itself, which confirms the F-

Syntax

The generation of the treebank has been done automatically thanks to the MarsaTag parser, trained on a subset of 100,000 words of the FTB, manually corrected and labelled following the 4-Couv annotation format (as shown in figure 4). Finally, several errors concern function labels (clitics and subordinates, in particular).

Discourse

Back covers naturally host interesting discourse structures.

We consider them as a good starting point for applying eyetracking methodology to discourse structure studies.

As a pilot study [START_REF] Prévot | Discourse structure of back covers: A pilot study[END_REF], we annotated 7 back covers selected for their interest following Annodis guidelines [START_REF] Muller | Manuel d'annotation en relations de discours du projet annodis[END_REF]. These guidelines provide instruction to segment a text into discourse units as well as to relate the units through discourse relations such as Narration, Explanation, etc.. The annotation framework is grounded in Segmented Discourse Representation Theory [START_REF] Asher | Logics of conversation[END_REF]. From the structures annotated we are able to extract a set of predictors for reading time corresponding to the main characteristics of the discourse structures. The predictors extracted were, for each discourse unit: # relations involving the unit, # potential attachment points, distance to attachment point, length of furthest anaphoric, New topic , Position in the discourse.

The pilot study involving only 16 subjects reading these 7 texts have not provided enough data to establish clear discourse structure impact on reading time. The results however validated our overall set-up since known effects about proper names, numbers and word size (at token level) taking longer to read were replicated. The amount of data needed to establish subtle discourse constraints is too large5 given the costly discourse annotation process. However a solution of manipulating control 'original' texts annotated to form hypotheses-driven modified text from an intermediate size corpora seems to be a very promising option. It will allow to preserve all the good properties of back covers dataset while allow discourse experiements by direct comparison of parallel texts.

Treebanking tools

The 4-Couv treebank required the development of two different types of tools, adapted to this project: corpus building (selection, checking and ranking of the texts) and tree edition for manual correction.

Text Selector

The Text Selector is a tool helping in the selection of the texts, on the form of HTML files each containing 10 texts to evaluate. Each unit presents the book description and the text, segmented into sentences. It also proposes an evaluation form (containing check boxes and drop-down lists), and the list of unknown words, to be manually tagged. This interface (see figure 6) makes it possible to easily correct different types of errors, including sentence segmentation as well as metadata.

Using autonomous HTML files makes easier the distribution of the revision work between several annotators. It does not require any particular environment (files being edited directly in a browser), neither a connection to a server. The revision tool relies on an adaptation of a Tid-dlyWiki 6 enriched with scripts for adding extra information to the texts.

POS-tagging corrector

The morphosyntactic correction tool (see figure 7) presents one token per line, each line containing the form and the list of possible tags associated to the form, starting with the chosen one. All possible labels anf features are then proposed. Correcting a tag simply consists in chosing a new one in the list or manually editing it.

Tree editor

The syntactic correction tool is a tree editor. Only few of them already exist such as WordFreak [START_REF] Morton | Wordfreak: An open tool for linguistic annotation[END_REF] or TrED 2.0 [START_REF] Pajas | Recent advances in a feature-rich framework for treebank annotation[END_REF].

More recently, some web-based annotation platforms have also been developed, offering an intuitive and fast annotation (brat [START_REF] Stenetorp | brat: a web-based tool for nlpassisted text annotation[END_REF], as well as project management facilities for example by specifying the roles such as annotator, curator or project manager (GATE Teamware [START_REF] Bontcheva | Gate teamware: a web-based, collaborative text annotation framework[END_REF], WebAnno [START_REF] Yimam | Webanno: A flexible,web-based and visually supported system for distributed annotations[END_REF]). However, if some of these platforms have been developed or adapted for dependency-based treebanks (see figure 8), none is suited for constituency-based treebanks (requiring therefore to deal with a potentially large number of levels, see figure 9). To take advantage of web-based platforms, we developed a specific editor javascript library, that could run in a single HTML or to be integrated into an annotation platform such as brat (see figure 10) or WebAnno. The library shows each tree in a resizable and zoomable vectorial image (SVG), whose colors are customizable with CSS style sheets. Subtrees could be moved by a simple drag and drop. A doubleclick on nodes allows to edit its tag, and buttons or contextual menu offers other edition functionalities (insertion, deletion, etc., see figure 11).

Perspectives

The 4-Couv treebank constitutes a new kind of resources, answering at the same time to the classical needs of linguistic description as well as experimental linguistics. This treebank, because being made of short texts, can propose a complete annotation at both syntactic and discourse levels. Moreover, this characteristics also makes it possible to acquire physiological data such as eye movement or brain activity by controlling easily different parameters. A first eye-tracking experiment have been done, studying different effects of word categories. 4-Couv is an ongoing long term project. The first release (200 texts, 1,500 trees) will be distributed through the SLDR data warehouse (http://www.sldr.org). 4-Couv is also becoming multilingual: a comparable treebank is under construction for Mandarin Chinese thanks to a collaboration with Hong Kong Polytechnic University.

  ) "Ce film, Paul et moi on a adoré." (This movie, Paul and I we really do like.)

Figure 1 :

 1 Figure 1: Syntactic tagset

Figure 2 :

 2 Figure 2: Lexical categories and features

Figure 4 :

 4 Figure 4: Output of the parser

Figure 5 :

 5 Figure 5: Annotation layers and tools

Figure 6 :

 6 Figure 6: Selection tool: global view

Figure 7 :

 7 Figure 7: POS-tagging corrector

Figure 8 :

 8 Figure 8: a dependency tree with brat

Figure 10 :

 10 Figure 10: the syntactic tree editor in brat

The French appellation of a backcover is "4ème de couverture", leading to the treebank acronym: 4-Couv.

[START_REF] Morton | Wordfreak: An open tool for linguistic annotation[END_REF] Available on the ORTOLANG platform, hdl:11403/4-couv

Our previous study on morpho-syntax effects (Blache and Rauzy, 2012) included 10000 tokens).