Article ID Journal Published Year Pages File Type
9657745 Theoretical Computer Science 2005 13 Pages PDF
Abstract
In this paper we study number-decreasing cellular automata. They form a super-class of standard number-conserving cellular automata. It is well-known that the property of being number-conserving is decidable in quasi-linear time. In this paper we prove that being number-decreasing is dimension sensitive, i.e. it is decidable for one-dimensional cellular automata and undecidable for dimension 2 or greater. There are only few known examples of dimension sensitive properties for cellular automata and this denotes some rich panel of phenomena in this class.
Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , , ,