The domino problem on groups of polynomial growth
Preprint
Abstract
We characterize the virtually nilpotent finitely generated groups (or, equivalently by Gromov's theorem, groups of polynomial growth) for which the Domino Problem is decidable: These are the virtually free groups, i.e. finite groups, and those having $\Z$ as a subgroup of finite index.
Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- The domino problem of the hyperbolic plane is undecidableTheoretical Computer Science, 2008
- Logical aspects of Cayley-graphs: the group caseAnnals of Pure and Applied Logic, 2005
- Random Walks on Infinite Graphs and Groups2000
- Vertex-Transitive Graphs and AccessibilityJournal of Combinatorial Theory, Series B, 1993
- Graphs and groups with tree-like propertiesJournal of Combinatorial Theory, Series B, 1989
- The theory of ends, pushdown automata, and second-order logicTheoretical Computer Science, 1985
- Groups, the Theory of ends, and context-free languagesJournal of Computer and System Sciences, 1983
- The undecidability of the domino problemMemoirs of the American Mathematical Society, 1966
- ber unendliche Wege in GraphenMathematische Annalen, 1964