KARI , Jarkko

We study the group-valued and semigroup-valued conservation laws in cellular automata (CA). We provide examples to distinguish between semigroup-valued, group-valued and real-valued conservation laws. We prove that, even in one-dimensional case, it is undecidable if a CA has any non-trivial conservation law of each type. For a fixed range, each...

Cellular automata (CA) are formal models for the simulation and the study of many complex systems encountered in natural or even social sciences. The success of this model is essentially due to its three main properties: locality, synchronicity and uniformity. Over the years it became apparent that many phenomena, such as the chemical reactions...

Conservation laws in cellular automata (CA) are studied as an abstraction of the conservation laws observed in nature. In addition to the usual real-valued conservation laws we also consider more general group-valued and semigroup-valued conservation laws. The (algebraic) conservation laws in a CA form a hierarchy, based on the range of the...

Reversible computation allows computation to proceed not only in the standard, forward direction, but also backward, recovering past states. While reversible computation has attracted interest for its multiple applications, covering areas as different as low-power computing , simulation, robotics and debugging, such applications need to be...