A notion of effectiveness for subshifts on finitely generated groups

DOI10.1016/J.TCS.2016.11.033MaRDI QIDQ501655zbMATH OpenOpenAlexFDO

Authors 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

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)

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.

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

Cites work

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

Cited in

(10)

• 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 geometric simulation theorem on direct products of finitely generated groups
• Realization of aperiodic subshifts and uniform densities in groups
• Aperiodic subshifts of finite type on groups which are not finitely generated
• The large scale geometry of strongly aperiodic subshifts of finite type
• About the domino problem for subshifts on groups
• Subshifts with sparse traces
• A generalization of the simulation theorem for semidirect products
• The group of reversible Turing machines

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)