Computability of extender sets in multidimensional subshifts: asymptotic growths, dynamical constraints

2024/01/15 by Callard, Antonin, Salomon, Léo Paviet, Vanier, Pascal
#Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #Dynamical Systems (math.DS) #FOS: Computer and information sciences #FOS: Mathematics #Logic in Computer Science (cs.LO)

paper · doi:10.48550/arxiv.2401.07549

Abstract

Subshifts are sets of colorings of ℤ^d defined by families of forbidden patterns. In a given subshift, the extender set of a finite pattern is the set of all its admissible completions. Since soficity of ℤ subshifts is equivalent to having a finite number of extender sets, it had been conjectured that the number of extender sets could provide a way to separate the classes of sofic and effective subshifts in higher dimensions. We investigate some computational characterizations of extender sets in multidimensional subshifts, and in particular their growth, in terms of extender entropies (arXiv:1711.07515) and extender entropy dimensions. We prove here that sofic and effective subshifts have the same possible extender entropies (exactly the Π₃-computable real numbers of [0,+∞)) and extender entropy dimensions, and investigate the computational complexity of these growth-type quantities under various dynamical and combinatorial constraints.

Related

• Finding lower bounds on the growth and entropy of subshifts over countable groups
• On independence and entropy for high-dimensional isotropic subshifts
• A characterization of entropy dimensions of minimal tridimensional subshifts of finite type
• Factoring onto ℤ^d subshifts with the finite extension property
• The structure of low complexity subshifts