A notion of effectiveness for subshifts on finitely generated groups

DOI10.1016/J.TCS.2016.11.033zbMATH Open1356.68057arXiv1412.2582OpenAlexW1949102480MaRDI QIDQ501655FDOQ501655

Authors: Nathalie Aubrun, Sebastián Barbieri, Mathieu Sablik 

Publication date: 9 January 2017

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

Abstract: We generalize the classical definition of effectively closed subshift to finitely generated groups. We study classical stability properties of this class and then extend this notion by allowing the usage of an oracle to the word problem of a group. This new class of subshifts forms a conjugacy class that contains all sofic subshifts. Motivated by the question of whether there exists a group where the class of sofic subshifts coincides with that of effective subshifts, we show that the inclusion is strict for several groups, including recursively presented groups with undecidable word problem, amenable groups and groups with more than two ends. We also provide an extended model of Turing machine which uses the group itself as a tape and characterizes our extended notion of effectiveness. As applications of these machines we prove that the origin constrained domino problem is undecidable for any group of the form $GimesmathbbZ$ subject to a technical condition on $G$ and we present a simulation theorem which is valid in any finitely generated group.

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

Recommendations

• On extensions of subshifts by finite groups
• Aperiodic subshifts of finite type on groups which are not finitely generated
• ON SUBSHIFTS AND SEMIGROUPS
• Realization of aperiodic subshifts and uniform densities in groups
• scientific article; zbMATH DE number 5953366
• scientific article; zbMATH DE number 4214929
• Effective subgroup separability of finitely generated nilpotent groups
• On the structure of generic subshifts
• Sous-décalages de Toeplitz sur les groupes moyennables résiduellement finis
• On effective Birkhoff's ergodic theorem for computable actions of amenable groups

zbMATH Keywords

symbolic dynamicsTuring machinesmodels of computationword problems

Mathematics Subject Classification ID

Symbolic dynamics (37B10) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Cites Work

• An Introduction to Symbolic Dynamics and Coding
• Title not available (Why is that?)
• A characterization of the entropies of multidimensional shifts of finite type
• The undecidability of the domino problem
• On the dynamics and recursive properties of multidimensional symbolic systems
• On torsion-free groups with infinitely many ends
• Symbolic dynamics and relatively hyperbolic groups.
• DEGREES OF GROWTH OF FINITELY GENERATED GROUPS, AND THE THEORY OF INVARIANT MEANS
• One head machines from a symbolic approach
• Undecidability and nonperiodicity for tilings of the plane
• Simulation of effective subshifts by two-dimensional subshifts of finite type
• THE WORD PROBLEM
• Undecidable tiling problems in the hyperbolic plane
• The domino problem on groups of polynomial growth
• Turing machines on Cayley graphs
• Title not available (Why is that?)
• Effective closed subshifts in 1D can be implemented in 2D
• Induction and restriction of cellular automata
• Group-walking automata
• Symbolic Dynamics

Cited In (10)

• Realization of aperiodic subshifts and uniform densities in groups
• About the domino problem for subshifts on groups
• Subshifts with sparse traces
• The work of Mike Hochman on multidimensional symbolic dynamics and Borel dynamics
• A geometric simulation theorem on direct products of finitely generated groups
• A generalization of the simulation theorem for semidirect products
• The group of reversible Turing machines
• On the entropies of subshifts of finite type on countable amenable groups
• The large scale geometry of strongly aperiodic subshifts of finite type
• Aperiodic subshifts of finite type on groups which are not finitely generated

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q501655)