Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9657745 | Theoretical Computer Science | 2005 | 13 Pages |
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
Vincent Bernardi, Bruno Durand, Enrico Formenti, Jarkko Kari,