Effective Closed Subshifts in 1D Can Be Implemented in 2D

DOI10.1007/978-3-642-15025-8_12zbMath1287.37012arXiv1003.3103OpenAlexW1864565641WikidataQ57349594 ScholiaQ57349594MaRDI QIDQ3586005

Alexander Shen, Andrei Romashchenko, Bruno Durand

Publication date: 3 September 2010

Published in: Fields of Logic and Computation (Search for Journal in Brave)

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

zbMATH Keywords

fixed pointaperiodic tilingssubshifts

Mathematics Subject Classification ID

Related Items (13)

The Group of Reversible Turing Machines ⋮ Effective S-adic Symbolic Dynamical Systems ⋮ Computability in Symbolic Dynamics ⋮ Turing degree spectra of minimal subshifts ⋮ Quantifier extensions of multidimensional sofic shifts ⋮ About the Domino Problem for Subshifts on Groups ⋮ Subshifts with sparse traces ⋮ A notion of effectiveness for subshifts on finitely generated groups ⋮ Unnamed Item ⋮ The work of Mike Hochman on multidimensional symbolic dynamics and Borel dynamics ⋮ Slopes of multidimensional subshifts ⋮ A generalization of the simulation theorem for semidirect products ⋮ Characterizations of periods of multi-dimensional shifts

Cites Work

• Fixed-point tile sets and their applications
• On the dynamics and recursive properties of multidimensional symbolic systems
• Reliable computation with cellular automata
• Local rules and global order, or aperiodic tilings
• Tilings, substitution systems and dynamical systems generated by them
• Remarks on Berger's paper on the domino problem
• Complex tilings
• Fixed Point and Aperiodic Tilings
• Forbidden Substrings, Kolmogorov Complexity and Almost Periodic Sequences
• The undecidability of the domino problem
• Reliable cellular automata with self-organization
• The classical decision problem.

This page was built for publication: Effective Closed Subshifts in 1D Can Be Implemented in 2D