Positive expansiveness versus network dimension in symbolic dynamical systems

DOI10.1016/J.TCS.2011.02.021MaRDI QIDQ549698zbMATHOpenAlexFDO

Authors Marcus Pivato

Publication date 18 July 2011

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

cellular automatondimensionexpansivenessautomaton networkCantor dynamical system

Mathematics Subject Classification ID

Symbolic dynamics (37B10) Dynamical aspects of cellular automata (37B15)

Abstract: A `symbolic dynamical system' is a continuous transformation F:X-->X of a closed perfect subset X of A^V, where A is a finite set and V is countable. (Examples include subshifts, odometers, cellular automata, and automaton networks.) The function F induces a directed graph structure on V, whose geometry reveals information about the dynamical system (X,F). The `dimension' dim(V) is an exponent describing the growth rate of balls in the digraph as a function of their radius. We show: if X has positive entropy and dim(V)>1, and the system (A^V,X,F) satisfies minimal symmetry and mixing conditions, then (X,F) cannot be positively expansive; this generalizes a well-known result of Shereshevsky about multidimensional cellular automata. We also construct a counterexample to a version of this result without the symmetry condition. Finally, we show that network dimension is invariant under topological conjugacies which are Holder-continuous.

Cites work

• scientific article; zbMATH DE number 44107 (Why is no real title available?)
• scientific article; zbMATH DE number 139914 (Why is no real title available?)
• scientific article; zbMATH DE number 2042127 (Why is no real title available?)
• A Survey on Spectra of infinite Graphs
• A survey on graphs with polynomial growth
• Dimension theory of graphs and networks
• Endomorphisms of symbolic algebraic varieties
• Expansiveness, entropy and polynomial growth for groups acting on subshifts by automorphisms
• Fractal dimensions and Martin boundary of graphs
• Lyapunov exponent versus expansivity and sensitivity in cellular automata
• On continuous actions commutingwith actions of positive entropy
• On the Period-Two-Property of the Majority Operator in Infinite Graphs
• On the entropy of \(\mathbb{Z}^d\) subshifts of finite type
• Pregeometric concepts on graphs and cellular networks as possible models of space-time at the Planck-scale
• Random walks on graphs, electric networks and fractals
• Spectra of graphs and fractal dimensions. I
• Spectra of graphs and fractal dimensions. II
• The majority action on infinite graphs: Strings and puppets

Cited in

(3)

• Expansive automata networks
• Propagation, diffusion and randomization in cellular automata
• Pre-expansivity in cellular automata

This page was built for publication: Positive expansiveness versus network dimension in symbolic dynamical systems

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