Introducing Freezing Cellular Automata

International audienceWe introduce the class of freezing cellular automata (CA): those where the state of a cell can only increase according to some order on states. It contains some well-studied examples like the bootstrap percolation CA or " life without death " , but here we aim at studying the class as a whole and deriving general properties of freezing CA. Our focus is mainly on the complexity of these CA and we show that, if their definition imposes strong constraints on their possible dynamics, they still can produce complex computational behaviors, even in dimension 1. Our main results are that the prediction problem of these CA can be P-complete in dimension 2 or more, but is always NL in dimension 1. Moreover its communication complexity is always at most O(n d−1 log(n)) in dimension d (while it can be Ω(n d) for a CA in general). As another dimension-sensitive property, we show that the nilpotency problem is decidable in dimension 1 but not in higher dimension. Finally, although simpler, we show that one-dimensional freezing CA can still be Turing universal