Bachelor degree (July, 1993)

The first internship was under the direction of those that would later be my PhD advisors, Jacques Mazoyer and Bruno Durand. The topic was "cellular automata" in general and is decomposed in three parts:

  1. First, taking hints from an article of K. Sutner, I designed an algorithm to solve the problem of invertibility or surjectivity of cellular automata of dimension 1 in quadratic time.
  2. In a second part, I took a look at the relation between invertible cellular automata and universality. I designed an invertible cellular automaton capable of simulating non-revertible Turing machines, which showed they were a universal model of computation. K. Morita had proved such a result but simulated only revertible Turing machines. This proof led to a full article in a review a few years later.
  3. I also modified an already-existing program so that it could link dynamically (during the execution) with C-language written functions describing cellular automata to simulate them. A written-from-start version of this program was developped in 1998 in Chile during an academic exchange (then lost for good).

A figure is missing from this article (but was not referenced in the text apparently). It is lost (but in paper versions of this report). The article was recompiled recently to be turned into PDF. The article is written in French language.

Honour bachelar degree (Septembre 1994)

The second internship (three months during the summer of 1994) is in two parts; a small memo (in French) about the internship itself (not given here, see the French translation of this post) and an article in English about computer science. The internship was under the supervision of Kamala Krithivasan.

The mainframe of this work has been the study of cellular automata as very simple SIMD systems. We introduce some variations over the basic definition of cellular automata in order to compare these new models with other models of cellular automata. The neighborhood-varying cellular automata is shown to be as powerful as time-varying cellular automata. The dynamically reconfigurable cellular automata are more interesting because they effectively reduce the running-time for some normal CA computations. Then some possible applications of these works are browsed

Looking back, this is not my best work. Everything looks (now) almost too evident for me. I could have done better, had I slept more (it was a bit too wet and hot for me). The article was recompiled recently to be turned into PDF.

Quoting these publications

Here are the BIB-format entries for these articles, not easy to find (but on this page):

@MastersThesis{dubacq93,
  author = 	 {Jean-Christophe Dubacq},
  title = 	 {\'Etude des automates cellulaires inversibles},
  school = 	 {\'Ecole normale sup\'erieure de Lyon},
  year = 	 {1993},
  type = 	 {Licence / Bachelor degree}},
  month = 	 jul
  note =         {LIP, ENS Lyon}
}

@MastersThesis{dubacq94,
  author = 	 {Jean-Christophe Dubacq},
  title = 	 {Different Kinds of Neighborhood-Varying Cellular Automata},
  school = 	 {\'Ecole normale sup\'erieure de Lyon},
  year = 	 {1994},
  type = 	 {Ma{\^{\i}}trise / Honour Bachelor degree}},
  month = 	 sep,
  note =         {CS dept, IIT Madras}
}