Multidimensional cellular automata and generalization of Fekete's lemma
| dc.creator | Capobianco, Silvio | |
| dc.date | 2007-07-26 | |
| dc.date | 2008-06-17 | |
| dc.date.accessioned | 2026-07-07T09:44:36Z | |
| dc.date.available | 2026-07-07T09:44:36Z | |
| dc.description | Fekete's lemma is a well known combinatorial result on number sequences: we extend it to functions defined on $d$-tuples of integers. As an application of the new variant, we show that nonsurjective $d$-dimensional cellular automata are characterized by loss of arbitrarily much information on finite supports, at a growth rate greater than that of the support's boundary determined by the automaton's neighbourhood index. | |
| dc.description | 6 pages, no figures, LaTeX. Improved some explanations; revised structure; added examples; renamed "hypercubes" into "right polytopes"; added references to Arratia's paper on EJC, Calude's book, Cook's proof of Rule 110 universality, and arXiv paper 0709.1173 | |
| dc.identifier | https://arxiv.org/abs/0707.3903 | |
| dc.identifier | http://arxiv.org/abs/0707.3903 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/162933 | |
| dc.subject | General Mathematics | |
| dc.subject | Dynamical Systems | |
| dc.subject | 00A05, 37B15 | |
| dc.title | Multidimensional cellular automata and generalization of Fekete's lemma | |
| dc.type | text |