Characterizations of periods of multi-dimensional shifts
From MaRDI portal
Publication:5245329
DOI10.1017/etds.2013.60zbMath1336.37015arXiv1303.2462OpenAlexW2963223424MaRDI QIDQ5245329
Emmanuel Jeandel, Pascal Vanier
Publication date: 8 April 2015
Published in: Ergodic Theory and Dynamical Systems (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1303.2462
periodic pointsNP-complete\#P-completemulti-dimensional shifts of finite typeeffective shiftsmulti-dimensional sofic shifts
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Combinatorial dynamics (types of periodic orbits) (37E15)
Related Items (12)
Factor maps and embeddings for random \(\mathbb{Z}^d\) shifts of finite type ⋮ Computability in Symbolic Dynamics ⋮ Aperiodic points in $\mathbb Z^2$-subshifts ⋮ On graph induced symbolic systems ⋮ Arithmetical hierarchy of the Besicovitch-stability of noisy tilings ⋮ About the Domino Problem for Subshifts on Groups ⋮ Necessary conditions for tiling finitely generated amenable groups ⋮ Unnamed Item ⋮ The work of Mike Hochman on multidimensional symbolic dynamics and Borel dynamics ⋮ Slopes of multidimensional subshifts ⋮ Characterizing entropy dimensions of minimal mutidimensional subshifts of finite type ⋮ Quantified block gluing for multidimensional subshifts of finite type: aperiodicity and entropy
Cites Work
- Unnamed Item
- Unnamed Item
- A characterization of the entropies of multidimensional shifts of finite type
- A small aperiodic set of Wang tiles
- Reversibility and surjectivity problems of cellular automata
- Undecidability and nonperiodicity for tilings of the plane
- Periodicity in Tilings
- Effective Closed Subshifts in 1D Can Be Implemented in 2D
- Nondeterministic Space is Closed under Complementation
- The Nilpotency Problem of One-Dimensional Cellular Automata
- Turing machines and the spectra of first-order formulas
- An Introduction to Symbolic Dynamics and Coding
- Computational Complexity
- The undecidability of the domino problem
This page was built for publication: Characterizations of periods of multi-dimensional shifts
