A notion of effectiveness for subshifts on finitely generated groups

DOI10.1016/j.tcs.2016.11.033zbMath1356.68057arXiv1412.2582OpenAlexW1949102480MaRDI QIDQ501655

Nathalie Aubrun, Sebastián Barbieri, Mathieu Sablik

Publication date: 9 January 2017

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

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

zbMATH Keywords

Turing machinessymbolic dynamicsmodels of computationword problems

Mathematics Subject Classification ID

Related Items (7)

The Group of Reversible Turing Machines ⋮ About the Domino Problem for Subshifts on Groups ⋮ Subshifts with sparse traces ⋮ Realization of aperiodic subshifts and uniform densities in groups ⋮ On the entropies of subshifts of finite type on countable amenable groups ⋮ The work of Mike Hochman on multidimensional symbolic dynamics and Borel dynamics ⋮ A generalization of the simulation theorem for semidirect products

Cites Work

• Unnamed Item
• Unnamed Item
• Simulation of effective subshifts by two-dimensional subshifts of finite type
• One head machines from a symbolic approach
• Symbolic dynamics and relatively hyperbolic groups.
• A characterization of the entropies of multidimensional shifts of finite type
• On the dynamics and recursive properties of multidimensional symbolic systems
• Undecidable tiling problems in the hyperbolic plane
• The domino problem on groups of polynomial growth
• Undecidability and nonperiodicity for tilings of the plane
• On torsion-free groups with infinitely many ends
• Turing Machines on Cayley Graphs
• THE WORD PROBLEM
• Effective Closed Subshifts in 1D Can Be Implemented in 2D
• Induction and restriction of cellular automata
• DEGREES OF GROWTH OF FINITELY GENERATED GROUPS, AND THE THEORY OF INVARIANT MEANS
• An Introduction to Symbolic Dynamics and Coding
• Group-Walking Automata
• The undecidability of the domino problem
• Symbolic Dynamics

This page was built for publication: A notion of effectiveness for subshifts on finitely generated groups