Tag « journal »

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.

To show this on a small example (beyond what is in the article), imagine that in a game (like checkers) if blue takes red, on a result of 1, both are eliminated, on 2 or 3, red remains and blue remains in the other cases. If red takes blue, results 1 to 4 make red win and on 5 to 6, blue wins. The compact table in this case would be to keep the table as is in the blue versus red, add +2 if red versus blue, with results 7 and 8 letting red win.

lire la suite

In this article, co-written with Véronique Terrier for the Latin 2002 conference, we investigate how increasing the dimension of the array can help to draw signals on cellular automata. We show the existence of a gap of constructible signals in any dimension. We exhibit two cellular automata in dimension 2 to show that increasing the dimension allows to reduce the number of states required for some constructions.

lire la suite

In this article, written jointly with Enrico Formenti and Bruno Durand, we present a new approach to cellular automata (CA) classification based on algorithmic complexity. We construct a parameter κ which is based only on the transition table of CA and measures the "randomness" of evolutions; κ is better, in a certain sense, than any other parameter recursively definable on CA tables. We investigate the relations between the classical topological approach and ours one. Our parameter is compared with Langton's λ parameter: κ turns out to be theoretically better and also agrees with some practical evidences reported in literature. Finally, we propose a protocol to approximate κ and make experiments on CA dynamical behavior.

lire la suite