Translation-like actions by Z , the subgroup membership problem, and Medvedev degrees of effective subshifts
The paper studies translation-like actions by \(\mathbb Z\) on graphs and groups and analyzes algorithmic aspects of these actions together with applications to symbolic dynamics. A translation-like action of a group \(H\) on a metric space \((X,d)\) is a free action for which the displacement \(d(x,x\cdot h)\) is uniformly bounded for every \(h\in H\).\N\NOne of the main results proves that every infinite, connected, locally finite graph admits a translation-like action by \(\mathbb Z\). Moreover, the action can be chosen transitive if and only if the graph has either one or two ends and it can be arranged so that \(d(v,v\cdot1)\le3\) for every vertex \(v\). This strengthens a result of \textit{B. Seward} [Geom. Topol. 18, No. 1, 179--210 (2014; Zbl 1338.20041)], where the hypothesis required uniformly bounded vertex degree.\N\NThe paper also studies computability properties of such actions. It is shown that every finitely generated infinite group with decidable word problem admits a computable translation-like action by \(\mathbb Z\) with decidable orbit membership problem. As an application, the author studies Medvedev degrees of effective subshifts. Using computable translation-like actions, it is proved that for every finitely generated infinite group with decidable word problem the class of Medvedev degrees of effective subshifts coincides with the class of all \(\Pi^0_1\) Medvedev degrees, extending a result of \textit{J. S. Miller} [Proc. Am. Math. Soc. 140, No. 5, 1617--1622 (2012; Zbl 1246.37025)] for \(\mathbb Z^d\).
- A characterization of the entropies of multidimensional shifts of finite type
- A course in formal languages, automata and groups
- A notion of effectiveness for subshifts on finitely generated groups
- A survey of Mučnik and Medvedev degrees
- Amenability, bi-Lipschitz equivalence, and the von Neumann conjecture
- Burnside's problem, spanning trees and tilings.
- Cellular Automata and Groups
- Combinatorial group theory.
- Cutting up graphs
- Effective Matchmaking (Recursion Theoretic Aspects of a Theorem of Philip Hall)
- Enden offener Räume und unendliche diskontinuierliche Gruppen
- Graph colorings and recursively bounded \(\Pi ^ 0_ 1\)-classes
- Graph-theoretical versus topological ends of graphs.
- Group-theoretic orbit decidability.
- Hamiltonian paths in infinite graphs
- Handbook of computability and complexity in analysis
- Handbook of recursive mathematics. Vol. 1: Recursive model theory
- scientific article; zbMATH DE number 3706692 (Why is no real title available?)
- scientific article; zbMATH DE number 194088 (Why is no real title available?)
- scientific article; zbMATH DE number 3219506 (Why is no real title available?)
- scientific article; zbMATH DE number 3220420 (Why is no real title available?)
- scientific article; zbMATH DE number 3192675 (Why is no real title available?)
- scientific article; zbMATH DE number 3023865 (Why is no real title available?)
- Medvedev degrees of two-dimensional subshifts of finite type
- On the Cube of a Graph
- On the entropies of subshifts of finite type on countable amenable groups
- Orbit decidability and the conjugacy problem for some extensions of groups.
- Recursive Euler and Hamilton Paths
- Strongly aperiodic subshifts of finite type on hyperbolic groups
- The computable dimension of ordered abelian groups
- The conjugacy problem in extensions of Thompson's group \(F\)
- The cube of every connected graph is 1-hamiltonian
- Two notes on subshifts
- Über die Enden diskreter Räume und Gruppen
- ∏ 0 1 Classes and Degrees of Theories
This page was built for publication: Translation-like actions by \(\mathbb{Z} \), the subgroup membership problem, and Medvedev degrees of effective subshifts
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6851207)
