Context-free languages, groups, the theory of ends, second-order logic, tiling problems, cellular automata, and vector addition systems

It turns out that there exists a surprising connection between certain ideas from the areas listed in the title. In this announcement we try to briefly outline the connection and to state our principal results. Very roughly, we use concepts from formal language theory, group theory, and the theory of ends to investigate a class of graphs which we call context-free graphs. Using the results obtained and Rabin's theorem on the decidability of the monadic second-order theory of the infinite binary tree, we show that the monadic theory of any context-free graph is decidable. There are several classes of extensively investigated decision problems which are essentially problems on the grid of integer lattice points in n dimensions. We here have in mind various questions concerning tiling problems, cellular automata, and vector addition systems. Most of these problems are known to be unsolvable in the classical case. We show that these problems all make sense on a very general class of graphs and are all solvable on any context-free graph.