A cellular automaton model of brain tumor treatment and resistance.
A cellular automaton on a torus.
A compositional approach to synchronize two dimensional networks of processors
A Compositional Approach to Synchronize Two Dimensional Networks of Processors
The problem of synchronizing a network of identical processors that work synchronously at discrete steps is studied. Processors are arranged as an array of m rows and n columns and can exchange each other only one bit of information. We give algorithms which synchronize square arrays of (n × n) processors and give some general constructions to synchronize arrays of (m × n) processors. Algorithms are given to synchronize in time n2, , and 2n a square array of (n × n) processors. Our approach...
A Six States Minimal Time Solution to the Firing Squad Synchronization Problem
About the domino problem in the hyperbolic plane from an algorithmic point of view
This paper is a contribution to the general tiling problem for the hyperbolic plane. It is an intermediary result between the result obtained by R. Robinson [Invent. Math.44 (1978) 259–264] and the conjecture that the problem is undecidable.
Algorithms for weighted graph problems on the modified cellular graph automaton
Amenable groups and cellular automata
We show that the theorems of Moore and Myhill hold for cellular automata whose universes are Cayley graphs of amenable finitely generated groups. This extends the analogous result of A. Machi and F. Mignosi “Garden of Eden configurations for cellular automata on Cayley graphs of groups” for groups of sub-exponential growth.
An alternative formulation of the factorization conjecture for codes. (Une formulation alternative de la conjecture de factorisation des codes.)
An answer to a question by J. Milnor.
An intrinsically non minimal-time Minsky-like 6-states solution to the Firing Squad synchronization problem
Here is presented a 6-states non minimal-time solution which is intrinsically Minsky-like and solves the three following problems: unrestricted version on a line, with one initiator at each end of a line and the problem on a ring. We also give a complete proof of correctness of our solution, which was never done in a publication for Minsky's solutions.
Arbology: Trees and pushdown automata
We present a unified and systematic approach to basic principles of Arbology, a new algorithmic discipline focusing on algorithms on trees. Stringology, a highly developed algorithmic discipline in the area of string processing, can use finite automata as its basic model of computation. For various kinds of linear notations of ranked and unranked ordered trees it holds that subtrees of a tree in a linear notation are substrings of the tree in the linear notation. Arbology uses pushdown automata...
Asymptotic behavior of excitable cellular automata.
Automaticity of rational functions.