Context-free languages, groups, the theory of ends, second-order logic, tiling problems, cellular automata, and vector addition systems
David E. Muller, Paul E. Schupp · Bulletin of the American Mathematical Society · 1981
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.A finitely generated group can be described by a presentation G = (X; R) in terms of generators and defining relators.(All groups and presentations which we mention are assumed to be finitely generated.)The word problem of G is the set W(G) of all words on the generators and their inverses which represent the identity element of G. Anisimov [1] raised the question: "If W(G) is a context-free language in the sense of formal language theory, what can one say about the algebraic structure of GV 9 We were led to conjecture that G has context-free word problem if and only if G has a free subgroup of finite index, and we have essentially proven the conjecture.Our main tool is the theory of ends.Let T be the Cayley graph of a finitely-generated group G -<X;R).Let T^ denote the subgraph of T consisting of all vertices and edges connected to the identity by a path of length less than n.The number of ends of G is the limit as n goes to infinity of the number of infinite components of rV^.Stallings [4] proved that a group with more than one end has a particular structure in terms of certain group-theoretic constructions.We prove that an infinite group with context-free word problem has