About the Domino Problem for Subshifts on Groups

DOI10.1007/978-3-319-69152-7_9zbMath1405.20023OpenAlexW2797211915MaRDI QIDQ4613553

Sebastián Barbieri, Nathalie Aubrun, Emmanuel Jeandel

Publication date: 24 January 2019

Published in: Trends in Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-69152-7_9

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Combinatorial aspects of tessellation and tiling problems (05B45) Word problems, etc. in computability and recursion theory (03D40)

Related Items

Resource-bounded Kolmogorov complexity provides an obstacle to soficness of multidimensional shifts ⋮ Aperiodic SFTs on Baumslag-Solitar groups ⋮ Strongly aperiodic subshifts of finite type on hyperbolic groups ⋮ Parametrization by horizontal constraints in the study of algorithmic properties of \(\mathbb{Z}^2\)-subshifts of finite type ⋮ The domino problem is undecidable on every rhombus subshift ⋮ Simulations and the lamplighter group ⋮ On the domino problem of the Baumslag-Solitar groups ⋮ On the entropies of subshifts of finite type on countable amenable groups ⋮ Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A notion of effectiveness for subshifts on finitely generated groups
• The large scale geometry of strongly aperiodic subshifts of finite type
• Logical aspects of Cayley-graphs: the group case
• Graphs and groups with tree-like properties
• On the dynamics and recursive properties of multidimensional symbolic systems
• Graph minors. V. Excluding a planar graph
• The theory of ends, pushdown automata, and second-order logic
• Matching rules and substitution tilings
• Undecidable tiling problems in the hyperbolic plane
• On topological dynamics of Turing machines
• Classical recursion theory. Vol. II
• Computability with low-dimensional dynamical systems
• A short proof of Halin's grid theorem
• Tilings, substitution systems and dynamical systems generated by them
• Amenability, bi-Lipschitz equivalence, and the von Neumann conjecture
• A hierarchical strongly aperiodic set of tiles in the hyperbolic plane
• Undecidability and nonperiodicity for tilings of the plane
• Free subgroups in linear groups
• Turing-machines and the Entscheidungsproblem
• Burnside's problem, spanning trees and tilings.
• PERCOLATION ON GRIGORCHUK GROUPS
• Quantifier extensions of multidimensional sofic shifts
• The Domino Problem for Self-similar Structures
• ENTSCHEIDUNGSPROBLEM REDUCED TO THE AEA CASE
• Computable symbolic dynamics
• Cellular Automata and Groups
• Effective Closed Subshifts in 1D Can Be Implemented in 2D
• Periodicity and Immortality in Reversible Computing
• The Tiling Problem Revisited (Extended Abstract)
• Subgroups of small Cancellation Groups
• Matrix Subshifts for Z ^v Symbolic Dynamics
• Nonrecursive tilings of the plane. II
• Textile systems for endomorphisms and automorphisms of the shift
• An Introduction to Symbolic Dynamics and Coding
• Tiling Problems on Baumslag-Solitar groups
• Weak colored local rules for planar tilings
• Characterizations of periods of multi-dimensional shifts
• Classification of sofic projective subdynamics of multidimensional shifts of finite type
• On the Undecidability of the Tiling Problem
• The undecidability of the Turing machine immortality problem
• The undecidability of the domino problem
• Arithmetical Reducibilities I
• Machines, Computations, and Universality
• On Computable Numbers, with an Application to the Entscheidungsproblem
• Symbolic Dynamics
• Deciding stability and mortality of piecewise affine dynamical systems