The goal of this paper is to design a reversible $d$-dimensional cellular automaton which is capable of simulating the behavior of any given $d$-dimensional cellular automaton over any given configuration (even infinite) with respect to a well suited notion of simulation we introduce. We generalize a problem which was originally addressed in a pape...

A modal reduction principle of the form [i 1 ]. .. [i n ]p ⇒ [j 1 ]. .. [j n ]p can be viewed as a production rule i 1 •. .. • i n → j 1 •. .. • j n in a formal grammar. We study the extensions of the multimodal logic K m with m independent K modal connectives by finite addition of axiom schemes of the above form such that the associated finite set...

In the last decade, research on the star problem in trace monoids (is the iteration of a recognizable language also recognizable?) has pointed out the importance of the finite power property to achieve partial solutions to this problem. We prove that the star problem is decidable in some trace monoid if and only if, in the same monoid, it is decida...

A full construction of the universality of the Billiard ball model, a lattice gas model introduced by Margolus in 84 is provided. The BBM is a reversible two-dimensional block cellular automaton with two states. Fredkin's gate and reversible logic can be emulated inside the Billiard ball model. They are use to embed two-counter automata, a model un...

We present two musical problems which are interesting examples of musical CPs. The first one deals with harp music from Nzakara people of Central African Republic, where canon structures have been discovered. The computation of such structures is a critical problem for constraint solvers in the sense that there are no exact solutions, the only poss...