Multidimensional cellular automata and generalization of Fekete's Lemma

zbMATH Open1204.37014arXiv0707.3903MaRDI QIDQ3575433FDOQ3575433

Authors: Silvio Capobianco 

Publication date: 27 July 2010

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/0707.3903

Recommendations

• Fekete's lemma for componentwise subadditive functions of two or more real variables
• On a Hedlund's theorem and place-dependent cellular automata
• On an extension of Fekete's lemma
• scientific article; zbMATH DE number 4100614
• Characterisation of limit measures of higher-dimensional cellular automata

zbMATH Keywords

cellular automatonsubadditive functionproduct ordering

Mathematics Subject Classification ID

Mathematics in general (00A05) Dynamical aspects of cellular automata (37B15) Cellular automata (computational aspects) (68Q80)

Cited In (14)

• Nearly subadditive sequences
• Four-cycle free graphs, height functions, the pivot property and entropy minimality
• Fekete's lemma for componentwise subadditive functions of two or more real variables
• Approximating the hard square entropy constant with probabilistic methods
• Generalized Besicovitch and Weyl spaces: topology, patterns, and sliding block codes
• Effective Projections on Group Shifts to Decide Properties of Group Cellular Automata
• A new dimension sensitive property for cellular automata
• The Wasserstein distance of order 1 for quantum spin systems on infinite lattices
• k-Mixing Properties of Multidimensional Cellular Automata
• Spectral covariance and limit theorems for random fields with infinite variance
• When-and how-can a cellular automaton be rewritten as a lattice gas?
• A variational formula for dimension spectra of linear cellular automata
• Storage codes and recoverable systems on lines and grids
• Independence entropy of \(\mathbb{Z}^{d}\)-shift spaces

This page was built for publication: Multidimensional cellular automata and generalization of Fekete's Lemma

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3575433)