My main research field is cellular automata (CA). CAs which have been invented in the 50’s by von Neumann and Ulam. CAs are made of finite state machines (the cells) which communicate along a regular interconnection network (mostly a line or a grid). They evolve synchronously and in parallel by the application of a local transition rule. The local transition rule takes into account the nearest neighbors of each cell according to the interconnection network.
Parallel models complexity
I am interested in CAs from the point of view of computability. I have build a universal CA which is capable of simulating the behavior of any other totalistic CA. This result allows to consider CAs as a parallel model of computation (also called acceptable programming system).
I have also designed simulations of CAs by several classical models of parallel computation. Firstly with different kinds of PRAM (CREW-PRAM and XPRAM) and secondly with different types of spatial machines (a computation model which was proposed by Y. Feldman and E. Shapiro)
Cellular automata over Cayley graphs
I also consider CAs over finite Cayley Graphs. I have extended Zs. Róka’s work on the topic. I have published two different simulations of a torus of automata by a ring of automata. One of these simulations allows to reduce the number of copies of the neighbors to the smallest possible number. In addition, for particular values of width and height of the torus, we have proved that the simulation is time-optimal. By combining these results with those of Zs. Róka, it becomes also possible to simulate CAs over an hexagonal grid by a ring of automata.
Pseudo-random sequences generation
I have also a strong interest in the relationship between cryptology and CAs. I have recently shown that there is no non-linear elementary CA rule which is resilient. This result limits the use of elementary CAs for building cryptographic quality pseudo-random sequences. I am currently studying different ways to build pseudo-random generators.
I have also some interest in the use of cryptography to secure network protocols. I have supervised a few internships for designing a secure network time protocol.
