Les rencontres Frac sont des rencontres semestrielles francophones autour des thèmes du Projet ANR Sycomore : « Systèmes complexes et modèles de calcul. »

Lieu et dates

Les journées Frac d’automne 2008 auront lieu du lundi 1er décembre 2008 à 14h au mercredi 3 décembre 2008 à 12h à Nice, au Grand Château du campus Valrose de l’Université de Nice - Sophia Antipolis.

Plan du campus
Plan du campus via google maps

Inscription

Afin d’organiser ces journées, les pauses café, etc, il est demandé aux participants de s’inscrire par mail à l’adresse suivante : Nicolas.Ollinger[at]lif.univ-mrs.fr. Il n’y a pas de frais d’inscription et les frais autres que l’organisation stricte des rencontres (matériel, salles, pauses café) sont à la charge des participants (transport, logement, repas, dîner du jeudi soir).

Déroulement des journées

Les participants peuvent proposer des exposés (30 minutes) dans les thèmes du projet Sycomore lors de leur inscription par mail auprès des organisateurs. Il est demandé de fournir un titre ainsi qu’un résumé de quelques lignes. Titres, résumés et transparents sont à réaliser en anglais. Les exposés pouvant au choix de l’orateur être déclamés en français ou en anglais.

Logement

Pour l’hébergement nous pouvons vous proposer les hôtels suivants (triés par prix croissants). Informations indicatives repiquées de l’annonce d’un ancien Frac, les prix ont du augmenter.

Programme

Abstracts

Laurent Boyer, On Local Symmetries and Universality in Cellular Automata

Cellular automata (CA) are dynamical systems defined by a finite local rule but they are studied for their global dynamics. They can exhibit a wide range of complex behaviours and a celebrated result is the existence of (intrinsically) universal CA, that is CA able to fully simulate any other CA. In this paper, we show that the asymptotic density of universal cellular automata is 1 in several families of CA defined by local symmetries. We extend results previously established for captive cellular automata in two significant ways. First, our results apply to well-known families of CA (e.g. the family of outer-totalistic CA containing the Game of Life) and, second, we obtain such density results with both increasing number of states and increasing neighbourhood. Moreover, thanks to universality-preserving encodings, we show that the universality problem remains undecidable in some of those families.

Thomas Fernique, Weak Matching Rules

Matching rules on a set of tiles are finite constraints on the way tiles can be glued together. It is obvious to define matching rules which allow only periodic tilings to be formed. It turns out that it is also possible - although much harder - to enforce aperiodic tilings. Such constructions generally enforce a single aperiodic tiling (more precisely, its orbit under a group action), with the most celebrated example being probably the Penrose or the Robinson tilings. But there is also some "weaker" constructions, in the sense that they enforce not only one but many different aperiodic tilings. This is, for example, the case of the set of 14 Wang tiles discovered by J. Kari (later modified to get one lesser tile by K. Culik). This is also the case of so-called weak matching rules, introduced by L. Levitov for canonical tilings. Moreover, these matching rules also have an additional interesting geometric property. We will detail this construction and discuss some related open questions.

Pierre-Etienne Meunier, Communications in cellular automata

The framework of communication complexity was introduced by A.C. Yao in 1969. We intend to show here why these tools seem suitable for the study of cellular automata, by linking it both to several results and properties of cellular automata ("universalities"), and to other notions of complexity, namely Turing complexity and circuits. The ideas of this talk come from a paper (Cellular automata and communication complexity) by C. Durr, I. Rapaport and G. Theyssier, extended by the work of E. Goles and myself.

Jarkko Kari, Bounds on non-surjective 1D CA : A linear algebra approach

Based on the compactness and the Garden-of-Eden theorem, respectively, every non-surjective one-dimensional CA has an orphan (a finite word without a pre-image) and a diamond (two different words equal at the boundaries, having the same image). Also, there exist non-balanced words : words of equal length having different numbers of pre-images. We find upper bounds on the lengths of such words, using a linear algebra aproach. A similar approach was previously used to obtain a tight upper bound on the size of the inverse neighborhood of one-dimensional reversible CA.

Our bounds are the following. Consider a one-dimensional, non-surjective CA with n states and the radius-1/2 neighborhood. Then there exist words of length n that have different numbers of pre-images, there exists an orphan of length (n-3)n+5, and there exists a diamond of length at most 2n sqrt(n).

Alex Borello, Real-time Language Recognition on Two-Dimensional Cellular Automata : Influence of the Neighbourhood

A cellular automaton’s capacity to recognize a language in real time (the smallest number of time steps required for the automaton to entirely read the word in input) depends on its neighbourhood : V. Terrier proved that there exist two-dimensional languages which are recognizable in real time by a cellular automaton using von Neumann’s neighbourhood while they are not recognizable in real time by any automaton using Moore’s one. We come back here on this demonstration, with a slight use of Kolmogorov complexity inspired by the work of J. Cervelle.

Martin Delacourt, Consequences of a finite word on cellular automata

We consider one dimensional cellular automata with the standard neighborhood. On a cellular automata and with a finite word u, we look at the set of cells of the space-time diagram that are fixed for any initial configuration containing u (on the origin). This set can draw non-trivial shapes on the plane. We will essentially consider the example of drawing a parabola, which deals with some more general techniques, and with the reversibility of the automaton.

Kenichi Morita, Designing 1d universal reversible cellular automata

We study the problem how we can construct 1d reversible cellular automata (RCA) with computation universality (i.e., Turing universality). So far, several methods for designing such RCAs have been proposed. They are to simulate reversible Turing machines, to simulate cyclic tag systems, and others. As for simple universal RCAs, a 24-state model that works on infinite (ultimately periodic) configurations, and a 98-state model on finite configurations have been shown by Morita. In this talk, we give a survey on these results, as well as several techniques for designing such 1d universal RCAs. We also show a method of constructing 1d universal RCAs with one-bit communication channel.

Alexis Ballier, Structural aspects of tilings

We study the structure of the set of tilings produced by any given tile-set. For better understanding this structure, we address the set of finite patterns that each tiling contains. This set of patterns can be analyzed in two different contexts : the first one is combinatorial and the other topological. These two approaches have independent merits and, once combined, provide somehow surprising results. The particular case where the set of produced tilings is countable is deeply investigated while we prove that the uncountable case may have a completely different structure. We introduce a pattern preorder and also make use of *Cantor-Bendixson rank*. Our first main result is that a tile-set that produces only periodic tilings produces only a finite number of them. Our second main result exhibits a tiling with exactly one vector of periodicity in the countable case.

Enrico Formenti, Non-uniform cellular automata

We study the robusteness of the dynamics of cellular automata when the uniformity condition on the local rule is relaxed.

Pablo Arrighi, Universalité intrinsèque des Automates Cellulaires Quantiques

Co-authors : Renan Fargetton, Zizhu Wang.

Abstract. We give a one-dimensional quantum cellular automaton (QCA) capable of simulating all others. By this we mean that the initial configuration and the local transition rule of any onedimensional QCA can be encoded within the initial configuration of the universal QCA. Several steps of the universal QCA will then correspond to one step of the simulated QCA. The simulation preserves the topology in the sense that each cell of the simulated QCA is encoded as a group of adjacent cells in the universal QCA. The encoding is linear and hence does not carry any of the cost of the computation. We do this in two flavours.

Alberto Dennunzio, Decidable Properties of 2D Cellular Automata

We study some decidable properties of two dimensional cellular automata (2D CA). The notion of closingness is generalized to the 2D case and it is linked to permutivity and openness. We present two deep constructions which have been fundamental in order to prove our new results.

Alexander Shen,Transcendental density tilings

(talk by A.Shen joint with B.Durand, A.Romashchenko)

Penrose tiling is made by two tiles, and in a large region the proportion betwen these two tiles tends to a golden ratio. For other known tilings the fraction of each tile is also an algebraic number (since it is a component of an eigenvector of integer substitution matrix). However, the fixed point construction allows us to get any computable real number in [0,1] as a limit of tiles density (and only computable reals can be obtained in this way). We will explain the fixed point construction of aperiodic tiling with variable zoom factor and explain how to achieve any computable density.

Liste des participants

Organisateurs

Pour toute question, vous pouvez vous adresser à :
  Bruno Durand,
  Enrico Formenti,
  Grégory Lafitte,
  Nicolas Ollinger,
  Gaétan Richard.