The submission process is now closed. The program committee, after a careful reviewing process, has selected the following 14 papers to be
presented at JAC 2008 in the regular papers track. Please note that the provided abstracts are preliminary versions.
- Alexis Ballier and Emmanuel Jeandel. Tilings and model theory
Abstract: In this paper we emphasize the links between model theory and tilings. More precisely, after giving the definitions of what tilings are, we give a natural way to have an interpretation of the tiling rules in first order logics. This opens the way to map some model theoretical properties onto some properties of set of tilings, or tilings themselves.
- Alberto Dennunzio, Pietro Di Lena, Enrico Formenti and Luciano Margara. Classification of directional dynamics for additive cellular automata
Abstract: We continue the study of cellular automata (CA) directional dynamics, \ie the behavior of the joint action of CA and shift maps. This notion has been investigated for general CA in the case of expansive dynamics by Boyle and by Sablik for sensitivity and equicontinuity. In this paper we give a detailed classification for the class of additive CA providing non-trivial examples for some classes of Sablik's classification. Moreover, we extend the directional dynamics studies by considering also factor languages and attractors.
- Anahi Gajardo. Sofic one head machines
Abstract: There are several systems consisting in an object that moves on the plane by following a given rule. It is frequently observed that these systems eventually fall into an unexplained repetitive movement. The general framework of $k$-dimensional Turing machines with only one head is adopted. A subshift is associated to each Turing machine, and its properties are studied. The focus is placed on the machines whose associated subshift is sofic. It is proved that all of these machines eventually fall into a repetitive movement. Nevertheless, it seems that the machines with a sofic subshift are too simple. Many known machines remain out of scope; as an example, pebble automata are developed in detail.
- Jarkko Kari and Siamak Taati. A Particle Displacement Representation for Conservation Laws in Two-Dimensional Cellular Automata
Abstract: The problem of describing the dynamics of a conserved energy in a cellular automaton in terms of local movements of ``particles'' (quanta of that energy) has attracted some people's attention. The one-dimensional case was already solved by Fuks (2000) and Pivato (2002). For the two-dimensional cellular automata, we show that every (context-free) conservation law can be expressed in terms of such particle displacements.
- Gregory Lafitte. Goedel incompleteness revisited
Abstract: We investigate the frontline of Goedel’s incompleteness theorems’ proofs and the links with computability.
- Bruno Martin and Christophe Papazian. Neighborhood transformations on graph automata
Abstract: We consider simulations of graph automata. We introduce two local transformations on the neighborhood: splitting and merging. We explain how to use such transformations, and what are their consequences on the topology of the simulated graph, the speed of the simulation and the memory size of simulating automata in some cases. As an example, we apply these transformations to graph automata embedded on surfaces and we link our results with some simulation results between cellular automata on Cayley graphs.
- Nicolas Ollinger. Universalities in Cellular automata; a (short) survey
Abstract: This reading guide aims to provide the reader with an easy access to the study of universality in the field of cellular automata. To fulfill this goal, the approach taken here is organized in three parts: a detailled chronology of seminal papers, a discussion of the definition and main properties of universal cellular automata, and a broad bibliography.
- Victor Poupet. Translating partitioned cellular automata into classical type cellular automata
Abstract: Partitioned cellular automata are a variant of cellular automata that has been defined in order to make it very simple to create complex automata having strong properties such as number conservation and reversibility (which are often difficult to obtain on cellular automata). In this article we show how a partitioned cellular automaton can be translated into a regular cellular automaton in such a way that these properties are conserved.
- Gaétan Richard. Rule 110 : Universality and catenations
Abstract: Cellular automata are a simple model of parallel computation. Many people wonder about the power of such a model. In this paper, we show that even one of the simplest cellular automata (namely rule 110) can simulate, in a way we properly define, any Turing machine. This proof was originally written by M. Cook from an idea of S. Wolfram. Here, we shall provide a new approach of the proof that emphasise on information manipulation and use a particle catenation scheme introduced by N. Ollinger et al. to provide a full and simple proof of this result.
- Mathieu Sablik. Points of view to study the iterates of a random configuration by a Cellular Automaton
Abstract: We study the dynamic of the action of cellular automata on the set of shift-invariant probability measures according two point of view. First, the robustness of the simulation of a cellular automaton on a random configuration can be view considering the sensitivity on initial condition in the space of shift-invariant probability measures. Secondly we consider the evolution of the quantity of information in the orbit of a random initial state.
- Veronique Terrier. 2D CA recognizers with a path
Abstract: In this paper, two-dimensional cellular automata as one-dimensional language recognizer are considered. Following the approach of M. Delorme and J. Mazoyer to embed one-dimensional words into two-dimensional array, we deal with two-dimensional cellular automata equipped with a path. In this context, we investigate regular language recognition.
- Guillaume Theyssier. Amalgamation of Cellular Automata
Abstract: In this paper, we study amalgamations of cellular automata (CA), i.e. ways of combining two CA by disjoint union. We show that for several families of CA obtained by simple amalgamation operations (including the well-known families of majority and minority CA), the density of a large class of properties follows a zero-one law. Besides, we establish that intrinsic universality in those families is always non-trivial and undecidable for some of them. Therefore we obtain various syntactical means to produce CA which are almost all intrinsically universal. These results extend properties already obtained for captive cellular automata. We additionally prove that there exists some reversible captive CA which are (intrinsically) universal for reversible CA.
- Reem Yassawi and Marcus Pivato. The spatial structure of odometers in cellular automata
Abstract: Recent work has shown that many cellular automata have configurations whose orbit closures are isomorphic to odometers. We investigate the geometry of the spacetime diagrams of these 'odometer configurations'. For boolean linear cellular automata, we exactly determine the positions of the consecutive 'gears' of the odometer mechanism in the configuration. Then we characterise and explain the self similar structure visible in the spacetime diagrams of odometer configurations for two classesof nonlinear cellular automata: ratchet cellular automata and Coven cellular automata.
- Jean-Baptiste Yunès. Goto's construction and Pascal's Triangle: New Insights into Cellular Automata Synchronization
Abstract: Here we present a new non-recursive minimal-time solution to the Firing Squad Synchronization Problem which does not use any recursive process. In 1962, E. Goto designed an iterative algorithm which uses Minsky-McCarthy's solutions to synchronize in minimal-time. Our solution does not use any standard recursion process, only some ``fractal computation'', making it a purely iterative synchronization algorithm.
The program committee decided to consider some of the submitted papers for an exploratory papers track.
This category is devoted to papers dealing with very special new variants of cellular automata, to papers that are scope borderline, and to papers that give preliminary results for new trends of the field.
Papers selected in the exploratory track are to be published in the proceedings and presented by one of their authors at JAC 2008.
- Pablo Arrighi and Vincent Nesme. Quantization of cellular automata
Abstract: Take a cellular automaton, consider that each configuration is a basis vector
in some vector space, and linearize the global evolution function. If lucky, the result could
actually make sense physically, as a valid quantum evolution; but does it make sense as
a quantum cellular automaton? That is the main question we address in this paper. In
every model with discrete time and space, two things are required in order to qualify as
a cellular automaton: invariance by translation and locality. We prove that this locality
condition is so restrictive in the quantum case that every quantum cellular automaton
constructed in this way — i.e., by linearization of a classical one — must be reversible. We
also discuss some subtleties about the extent of nonlocality that can be encountered in the
one-dimensional case; we show that, even when the quantized version is non local, still,
under some conditions, we may be unable to use this nonlocality to transmit information
nonlocally.
- Alberto Dennunzio, Pierre Guillon and Benoît Masson. Topological properties of sand automata as cellular automata
Abstract: In this paper, we exhibit a strong relation between the sand automata configuration space and the cellular automata configuration space. This relation induces a
compact topology for sand automata, and a new context in which sand automata are homeomorphic to cellular automata acting on a specific subshift. We show that the existing
topological results for sand automata, including the Hedlund-like representation theorem,
still hold. In this context, we give a characterization of the cellular automata which are
sand automata.
- Jean-Christophe Dubacq and Jean-Yves Moyen. Study of the NP-completeness of the compact table problem
Abstract: The problem of compact tables is to maximise the overlap when building a
word that is to include permutations of every given words (all the words being the same
length). This problem is shown to be NP-complete in the general case, and some specific
restrictions are studied.
- Jérôme Durand-Lose. The signal point of view: from cellular automata to signal machines
Abstract: After emphasizing on the use of discrete signals in the literature on cellular
automata, we show how these signals have been considered on their own. We then present
their continuous counterpart: abstract geometrical computation and signal machines. Finally we relate them to other models of computation, classical and analog.
- Jean-Baptiste Rouquier. An exhaustive experimental study of synchronization by forcing on elementary cellular automata
Abstract: We study a way of coupling two configurations of the same cellular automaton
rule for all elementary cellular automata (ECA). We experimentally show that there are
only two possible behaviors: either synchronization for all coupling strength, or a phase
transition. This transition is shown to belong to the directed percolation universality class,
even for a non chaotic rule and for rules with particles.